JS数据结构之二叉查找树（BST）

源码

点击这里前往Github获取本文源码。

介绍

二叉查找树（Binary Search Tree, BST）也叫做有序二叉树。对于树中的每个节点，都要满足左子树的所有项比它小，右子树所有项比它大。由于这个要求，每次操作最优情况的时间复杂度都可以达到 O(log n)，因为一次比较可以过滤掉一半。

但是，在极端情况下，它会退化为一个普通的链表，此时再进行操作的时间复杂度就会是 O(n) 了。

这个问题需要平衡二叉树来解决，本文只讨论普通的二叉查找树。

实现

逐个函数来分析。

创建节点

定义一个用来生成节点的函数node：

function createNode(val) {
    return { val, left: undefined, right: undefined }
}

这个函数就是返回一个对象，没什么好说的。

查找

考虑BST的性质：对于任意一个节点，左子树的所有项都比它小，右子树的所有项都比它大。所以，我们可以写出下列代码：

function contains(node, val) {
    if (!node) {
        return false
    }

    if (val < node.val) {
        return contains(node.left, val)
    } else if (val > node.val) {
        return contains(node.right, val)
    }
    
    return true
}

尽管比较简单，这里也说一下执行过程

1. 如果node为空，直接返回false。考虑到有null和undefined两种可能性，这里就直接用取反运算符来判断是否为空了。
2. 如果要查找的值比当前节点的值小，就去左子树查找；如果大，就去右子树查找。
3. 既不大于也不小于，那就是相等，返回true。

后续的算法与这些步骤都是类似的。

插入

同样是考虑BST的性质，步骤会在下方解析，先展示代码：

function insert(node, val) {
    if (!node) {
        return createNode(val)
    }
    if (val < node.val) {
        node.left = insert(node.left, val)
    } else if (val > node.val) {
        node.right = insert(node.right, val)
    }

    return node
}

因为这些都是递归实现，所以比如第一行的逻辑实际上要到最后一步才执行，确实阅读起来是有点反人类的。

1. 判断当前节点是否为空，如果是的话就返回一个新的节点。
2. 如果要插入的值比当前节点的值小，就去左子树插入；如果大，就去右子树插入。
3. 无论有没有进入if块，都返回当前节点

看到这里，我一开始不是很理解为什么诸如第6行要写成node.left = insert(node.left, val)的形式，这里分析一下

• 如果node.left为空，那么insert(node.left, val)就会返回一个新的节点，成功执行了插入的操作。
• 如果node.left不为空，那么insert(node.left, val)返回的还是node.left，此时插入已经在更深的层次完成。

读者可以在纸上演算一遍插入的过程，我当时就是根据代码自己演算这个过程之后就能大概理解了。

删除

删除操作的难度系数更大一些，但是核心思想上和上面的插入并无不同之处，代码如下：

function remove(node, val) {
    if (!node) {
        return node
    }
    if (val < node.val) {
        node.left = remove(node.left, val)
    } else if (val > node.val) {
        node.right = remove(node.right, val)
    } else if (node.left && node.right) {
        // Find minimum value
        let min = node.right
        while (min.left) {
            min = min.left
        }
        node.val = min.val
        node.right = remove(node.right, node.val)
    } else {
        node = node.left || node.right
    }
    return node
}

我们根据图片来分析，我们要在下面这个BST中删除值为2的节点：

BST

下面步骤中的node会被标黄，表示当前节点；val表示要删除的值。

1. 比较val与node.val的大小

和根节点比较

1. val比node.val的值小，执行从左子树删除的操作。

从左子树删除

1. val与当前节点的值相等，并且左右子树都不为空。

比较val与当前节点，并且左右子树都是非空

1. 从右子树找到最小值，就是这里标绿的节点，并且把它赋值给当前节点。

最小值是3，并且把它赋值给当前节点

1. 从右子树把刚才获得的最小值3删掉。

删掉最小值3

1. 此时进入了新的递归调用，val为3，它小于当前节点值。

比较val与当前节点

1. 从左子树删除val值。

从左子树删除3

1. 此时的节点与val相同，但是左右子树是空。

找到要删除的节点，并且它的左右子树是空

1. 将它赋值为node.left || node.right，这里就是undefined。

就是将它赋值为undefined

1. 最深层的递归函数执行结束，返回上一层函数，是node.left = remove(node.left, val)。

执行上一层函数

1. 执行结束，再把这个节点本身返回给上一层函数。

再执行上一层函数

1. 执行结束，把这个节点本身返回到最外层函数。

返回到最外层

执行完毕，成功删除了指定的节点。看起来多，那是因为我把每一层递归调用都放出来了，包括递归函数调用结束后返回上一层的时候我也列出来了。实际上，关键步骤是，把当前节点的值赋值为右子树里的最小值，和删除右子树里的最小值。

参考

数据结构与算法分析