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

源码

来自半年后的说明：我把源码转放到 GitHub Gists 里了，当时的代码风格还是受 Python 影响较大，由于东西太多了，就不统一改代码风格了，毕竟就算复制也能在本地用自己的格式化工具来重新规范一下。

点击这里获取本文源码。

介绍

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

普通的BST

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

极端情况下的BST

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

实现

逐个函数来分析。

创建节点

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

1
2
3

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
}

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

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

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

判断当前节点是否为空，如果是的话就返回一个新的节点。
如果要插入的值比当前节点的值小，就去左子树插入；如果大，就去右子树插入。
无论有没有进入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
}