Py算法与数据结构
课程目录/第三部：搜索/第 9 节

09　二叉搜索树

按键搜索、插入、删除与中序有序

如果数据不仅要被查找，还要保留大小关系，那么单纯的哈希表就不一定合适。

二叉搜索树把数据组织成一棵有序的二叉树：

  • 左子树中的所有元素小于当前节点；
  • 右子树中的所有元素大于当前节点。

因此，每次比较一个节点，就可以决定下一步向左走还是向右走。

二叉搜索树的搜索速度取决于树高 h。树越矮，搜索越接近 O(log n)；树退化成链表后，搜索会退化为 O(n)。

1. 从有序数组搜索开始

如果数据已经放在有序数组中，可以使用二分搜索：

def binary_search(data, target):
    left = 0
    right = len(data) - 1

    while left <= right:
        middle = (left + right) // 2

        if data[middle] == target:
            return middle
        if data[middle] < target:
            left = middle + 1
        else:
            right = middle - 1

    return -1

二分搜索的复杂度是 O(log n)，但插入新元素时，为了保持数组有序，可能需要移动 O(n) 个元素。

二叉搜索树把“二分的方向选择”变成了节点之间的链接：

        8
       / \
      3   12
     / \  / \
    1  5 10 15

查找 10 时：

  1. 10 小于 8，向左还是向右？10 大于 8，向右；
  2. 10 小于 12，向左；
  3. 找到 10。

2. Python 中的节点

先定义二叉搜索树节点：

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

创建一棵树：

root = TreeNode(
    8,
    left=TreeNode(3, TreeNode(1), TreeNode(5)),
    right=TreeNode(12, TreeNode(10), TreeNode(15)),
)

这里的 root 保存根节点。每个节点最多有 left 和 right 两个子节点。

二叉搜索树的关键不是“有两个指针”，而是必须满足有序性。只要某个节点的左子树中出现比它大的值，或者右子树中出现比它小的值，就不再是一棵合法的二叉搜索树。

3. 搜索

可以从根节点开始，不断缩小搜索范围：

def bst_search(root, target):
    current = root

    while current is not None:
        if target == current.value:
            return current

        if target < current.value:
            current = current.left
        else:
            current = current.right

    return None


node = bst_search(root, 10)
print(node.value if node else None)  # 10
print(bst_search(root, 7))           # None

每比较一次，就排除当前节点另一侧的一整棵子树。

如果树高为 h，搜索需要沿着一条从根到叶节点的路径前进，因此复杂度是：

O(h)

只有在树高能够保证为 O(log n) 时，才能把它写成 O(log n)。

4. 插入

插入新值时，也要沿着搜索路径寻找合适的位置：

def bst_insert(root, value):
    if root is None:
        return TreeNode(value)

    if value < root.value:
        root.left = bst_insert(root.left, value)
    elif value > root.value:
        root.right = bst_insert(root.right, value)
    else:
        # 本实现忽略重复值
        return root

    return root

使用这个函数构造二叉搜索树：

root = None

for value in [8, 3, 12, 1, 5, 10, 15]:
    root = bst_insert(root, value)

print(bst_search(root, 5).value)  # 5

这里使用递归是因为“插入到左子树”或“插入到右子树”本身就是同一个问题的缩小版。

也可以写成迭代版本。迭代版本不依赖 Python 的递归栈：

def bst_insert_iterative(root, value):
    new_node = TreeNode(value)

    if root is None:
        return new_node

    current = root

    while True:
        if value == current.value:
            return root

        if value < current.value:
            if current.left is None:
                current.left = new_node
                return root
            current = current.left
        else:
            if current.right is None:
                current.right = new_node
                return root
            current = current.right

5. 中序遍历为什么能得到有序序列？

二叉搜索树的中序遍历顺序是：

  1. 遍历左子树；
  2. 访问当前节点；
  3. 遍历右子树。
def inorder(root):
    result = []

    def visit(node):
        if node is None:
            return

        visit(node.left)
        result.append(node.value)
        visit(node.right)

    visit(root)
    return result


print(inorder(root))  # [1, 3, 5, 8, 10, 12, 15]

因为每个节点都满足左小右大的规则，所以中序遍历会按升序输出元素。

这提供了一个很有用的性质：

验证二叉搜索树是否保持有序，通常可以检查中序遍历结果是否严格递增。

也可以直接使用上下界验证，而不必先创建完整列表：

def is_bst(node, low=None, high=None):
    if node is None:
        return True

    if low is not None and node.value <= low:
        return False
    if high is not None and node.value >= high:
        return False

    return (
        is_bst(node.left, low, node.value)
        and is_bst(node.right, node.value, high)
    )


print(is_bst(root))  # True

6. 删除节点

删除是二叉搜索树中最需要理解的操作，因为删除节点后，剩余节点仍然必须满足有序规则。

6.1 删除叶节点

叶节点没有子树，直接删除即可：

删除前：      5
             / \
            3   7

删除 3：      5
               \
                7

6.2 删除只有一个子节点的节点

如果目标节点只有一个子节点，就让它的父节点直接连接这个子节点：

删除前：      5
             /
            3
           /
          1

删除 3：      5
             /
            1

6.3 删除有两个子节点的节点

如果目标节点有两个子节点，可以使用右子树中的最小节点替代它，也可以使用左子树中的最大节点替代它。

右子树中的最小节点叫作后继。它一定大于左子树中的所有元素，又不会大于右子树中的其他元素。

def find_min(node):
    current = node

    while current.left is not None:
        current = current.left

    return current


def bst_delete(root, target):
    if root is None:
        return None

    if target < root.value:
        root.left = bst_delete(root.left, target)
    elif target > root.value:
        root.right = bst_delete(root.right, target)
    else:
        # 情况一：没有左子树
        if root.left is None:
            return root.right

        # 情况二：没有右子树
        if root.right is None:
            return root.left

        # 情况三：同时有左右子树
        successor = find_min(root.right)
        root.value = successor.value
        root.right = bst_delete(root.right, successor.value)

    return root

测试删除：

root = None
for value in [8, 3, 12, 1, 5, 10, 15]:
    root = bst_insert(root, value)

root = bst_delete(root, 3)
print(inorder(root))  # [1, 5, 8, 10, 12, 15]

root = bst_delete(root, 8)
print(inorder(root))  # [1, 5, 10, 12, 15]

删除操作也只沿着一条根到叶节点的路径工作，所以复杂度仍然是 O(h)。

7. 树高决定性能

下面定义一个计算树高的函数。这里使用“节点数量”作为高度：空树高度为 0，只有根节点的树高度为 1。

def height(node):
    if node is None:
        return 0

    return 1 + max(height(node.left), height(node.right))

如果按比较均匀的顺序插入：

root = None
for value in [8, 3, 12, 1, 5, 10, 15]:
    root = bst_insert(root, value)

print(height(root))  # 3

如果按照升序插入：

root = None
for value in [1, 2, 3, 4, 5]:
    root = bst_insert(root, value)

print(height(root))  # 5

升序插入会产生类似链表的结构：

1
 \
  2
   \
    3
     \
      4
       \
        5

因此：

树形 树高 搜索、插入、删除
接近平衡 O(log n) O(log n)
退化成链表 O(n) O(n)

普通二叉搜索树只保证顺序，不保证平衡。

8. 重复值如何处理？

二叉搜索树必须提前规定重复值的策略。常见方案有：

  1. 忽略重复值；
  2. 相同值统一放到左子树；
  3. 相同值统一放到右子树；
  4. 节点中保存 value 和 count；
  5. 把相同值保存为一个列表。

如果只是实现集合，忽略重复值比较自然。如果实现多重集合或统计频次，可以保存计数：

class CountNode:
    def __init__(self, value):
        self.value = value
        self.count = 1
        self.left = None
        self.right = None

重复值策略会影响插入、删除、验证和遍历，不能只在某一个函数中临时决定。

9. 二叉搜索树和哈希表的比较

特性 二叉搜索树 哈希表
平均查找 平衡时 O(log n) O(1)
最坏查找 O(n) O(n)
是否保持顺序 是 通常不依赖大小顺序
范围查询 适合 不方便
找最小值、最大值 适合 需要额外处理
根据键精确查找 可以 非常适合
实现难度 中等 需要处理冲突和扩容

如果只关心“某个键是否存在”或“键对应的值是什么”，哈希表通常更简单。如果需要按顺序遍历、范围查询或找到相邻键，有序树更合适。

10. 二叉搜索树适合什么时候？

二叉搜索树适合：

  • 需要保持数据的大小顺序；
  • 需要按范围查找元素；
  • 需要快速找到最小值、最大值和相邻值；
  • 数据会持续插入和删除；
  • 需要一种可以扩展为平衡树的结构；
  • 想理解 AVL 树、红黑树等更复杂的数据结构。

如果数据不会频繁变化，也可以先排序，再使用列表和二分搜索。排序数组的实现更简单，而且连续内存通常有很好的缓存局部性。

11. 常见错误

把任意二叉树当成二叉搜索树

二叉树只要求每个节点最多有两个孩子；二叉搜索树还要求左小右大的全局顺序。

只检查直接孩子

某个节点的左孩子小于它，并不代表整个左子树都小于它。验证时必须传递上下界。

忘记返回新的根节点

删除根节点或插入到空树时，根节点可能发生变化，调用处必须接收返回值：

def update_root(root, target, value):
    root = bst_delete(root, target)
    root = bst_insert(root, value)
    return root

误以为搜索一定是 O(log n)

普通二叉搜索树可能退化成链表。只有平衡树或明确的高度约束，才能保证 O(log n)。

忽略重复值规则

重复值如何放置会影响所有操作。实现前应先确定策略。

12. 小结

  • 二叉搜索树通过左小右大的规则组织数据；
  • 搜索、插入和删除的复杂度都是 O(h)；
  • 中序遍历可以按升序输出所有节点；
  • 删除节点要分别处理叶节点、单子节点和双子节点；
  • 普通二叉搜索树不保证平衡，可能退化为链表；
  • 平衡时操作接近 O(log n)，退化时会变成 O(n)；
  • 需要精确查找时哈希表很方便，需要顺序和范围查询时有序树更合适；
  • 重复值策略和根节点更新是实现时最容易遗漏的细节。