背景

去年下半年，我在微信书架里加入了许多技术书籍，各种类别的都有，断断续续的读了一部分。

没有计划的阅读，收效甚微。

新年伊始，我准备尝试一下其他方式，比如阅读周。每月抽出1~2个非连续周，完整阅读一本书籍。

这个“玩法”虽然常见且板正，但是有效，已经坚持阅读七个月。

已读完书籍：《架构简洁之道》、《深入浅出的Node.js》、《你不知道的JavaScript（上卷）》、《你不知道的JavaScript（中卷）》、《你不知道的JavaScript（下卷）》、《数据结构与算法JavaScript描述》、《WebKit技术内幕》、《前端架构：从入门到微前端》。

当前阅读周书籍：《秒懂算法：用常识解读数据结构与算法》。

用二叉查找树加速万物

虽然可以用快速排序等排序算法将数据按升序排列，但这需要一些代价。最快的排序算法也需要O(N log N)时间。因此，如果经常要保证数据的顺序，则最好让数据一开始就按一定顺序排列，这样就不用重新排序了。

有序数组可以简单而有效地保证数据顺序。它的某些操作也很迅速：读取需要O(1)时间，而在使用二分查找的情况下查找只需要O(log N)时间。

但是，有序数组也有缺点。

有序数组的插入和删除都相对较慢。要向有序数组插入一个值，首先需要把比这个值更大的项向右移动一个格子。而在删除值的时候，也需要把比被删除值更大的项向左移动一个格子。在最坏情况（也就是在数组开头插入或者删除）下需要N步，而平均也需要N / 2步。不过无论如何，都是O(N)步，对简单的插入或者删除操作来说相对比较慢。

树

树也是基于节点的数据结构，但树的节点可以指向多个节点。

树有着一套独特的术语。

• 最上面的节点（在这个例子中就是"j"）叫作根节点。没错，在上图中，根位于树顶，树通常都是这样表示的。
• 在这个例子中，我们会说"j"是"m"和"b"的父节点。相对地，"m"和"b"就是"j"的子节点。同样，"m"是"q"和"z"的父节点，"q"和"z"是"m"的子节点。
• 和家谱一样，节点也有后代和祖先。节点的后代就是起源于该节点的全部节点，而祖先就是所有可以派生出该节点的节点。在上面的例子中，"j"是其他所有节点的祖先，而其他所有节点都是"j"的后代。
• 树具有层级。每一层都是树的一行。
• 树的一个属性是它是否平衡。如果节点的子树中节点数量相同，那么这棵树就是平衡的。

二叉查找树

二叉树的每个节点的子节点数量都是0、1或2。

二叉查找树是一种遵循以下规则的二叉树。

• 每个节点最多有一个“左”子节点和一个“右”子节点。
• 一个节点的“左”子树中的值都小于节点本身，“右”子树中的值都大于节点本身。

树的节点的Python实现如下所示：

class TreeNode:
    def __init__(self,val,left=None,right=None):
        self.value = val
        self.leftChild = left
        self.rightChild = right

可以用下面的代码构建一棵简单的树。

node1 = TreeNode(25)
node2 = TreeNode(75)
root = TreeNode(50, node1, node2)

因为二叉查找树具有独特的结构，所以可以很快地查找其中的值。

查找

二叉查找树的查找算法步骤如下。

(1) 让一个节点作为“当前节点”。（算法开始时，根节点就是第一个“当前节点”。）

(2) 检查当前节点的值。

(3) 如果这个值就是要找的值，则再好不过了。

(4) 如果要找的值小于当前节点的值，那么就在其左子树中继续查找。

(5) 如果要找的值大于当前节点的值，那么就在其右子树中继续查找。

(6) 重复步骤(1)~(5)，直到找到要找的值，或者到达了树的底端，而这种情况意味着要找的值不在树中。

二叉查找树的查找效率

二叉查找树的查找需要O(log N)时间。任何每一步排除一半错误选项的算法都需要这个时间。

logN层

二叉查找树的查找需要O(log N)时间还有另一种解释方法，而这也会解释二叉树的另一个通用特性：如果一棵平衡的二叉树中有N个节点，那么就会有大约log N层（或者称为行）。

假设树的每一行都填满了节点，没有空余位置。每次向树添加一行时，都差不多要加倍节点数量。（其实是加倍再加1）。

这表明，每个新的层级都会使树的大小加倍。因此，包含N个节点的树需要log N层来容纳所有节点。

二分查找的每一步都能排除一半数据，我们发现这是log N的特征，而二叉树需要的层数也符合这个特征。

代码实现：二叉查找树查找

下面是查找使用递归的Python实现：

def search(searchValue, node):
    # 基准情形：如果节点不存在或者已经找到了要找的值
    if node is None or node.value == searchValue:
        return node
    # 如果值小于当前节点，那么就继续搜索左子节点：
    elif searchValue < node.value:
        return search(searchValue, node.leftChild)
    # 如果值大于当前节点，那么就继续搜索右子节点：
    else: # searchValue > node.value
        return search(searchValue, node.rightChild)

这个search函数有两个参数：一个是要寻找的值searchValue，另一个是作为查找基础的节点node。第一次调用search时，node就是树的根节点。不过，在后续的递归调用中，node会是树中的其他节点。

函数一共处理了4种可能情形，其中2种是基准情形。

if node is None or node.value == searchValue:
    return node

一种基准情形是node就是要找的searchValue，这样只需要返回该节点，无须递归调用。

另一种基准情形是node为None。在看过其他情形后你就能理解了，所以稍后再对其进行介绍。

下一种情形是searchValue小于当前节点的值。

elif searchValue < node.value:
    return search(searchValue, node.leftChild)

在这种情况下，如果searchValue存在于树中，则肯定在节点的左子树中。因此，对节点的左子节点递归调用search函数。

下一种情形正相反，也就是searchValue大于当前节点。

else: # searchValue > node.value
    return search(searchValue, node.rightChild)

在这种情况下，对节点的右子节点递归调用search。

因为对当前节点的子节点递归调用时并不检查当前节点有没有子节点，所以才需要第一种基准情形。

if node is None

换言之，如果调用search的子节点并不存在，则会返回None。（这是因为node实际上就是None。）如果searchValue并不存在于树中，那么就会发生这种情况。这是因为我们在访问一个本来能找到searchValue的节点，但结果又没找到。在这种情况下，需要返回None，以表示searchValue不在树中。

总结

如果要找一个各方面速度都很不错的数据结构，那么哈希表是非常好的选择。哈希表的查找、插入和删除都只需要O(1)时间。美中不足的是，哈希表不支持排序，而排序又正是我们需要的。

二叉查找树能在保证顺序的同时，又能快速完成查找、插入和删除，而有序数组和哈希表都做不到这一点。

作者介绍
非职业「传道授业解惑」的开发者叶一一。
《趣学前端》、《CSS畅想》等系列作者。华夏美食、国漫、古风重度爱好者，刑侦、无限流小说初级玩家。
如果看完文章有所收获，欢迎点赞👍 | 收藏⭐️ | 留言📝。