二叉搜索树详解：原理、代码与时间复杂度

二叉搜索树解决什么问题

有序数组可以快速二分查找，但插入新元素时要移动其后的所有元素。哈希表查找和插入都很快，但不保持顺序，因此无法回答“比 42 大的最小键是什么？”或“列出 10 到 20 之间的所有键”。二叉搜索树既保持键有序，又支持快速插入和删除。它是有序映射和有序集合的基础，例如 Java 的 TreeMap 和 C++ 的 std::map，它们使用的是自平衡的变体。

用大白话理解这条规则

每个节点有一个键、一个可选的左孩子和一个可选的右孩子。对每个节点来说：左子树中的所有键都更小，右子树中的所有键都更大。要查找一个键，从根开始比较：键更小就往左走，更大就往右走，相等或走出树外就停止。

示例演练：构建并查找一棵树

按 8、3、10、1、6、14、4 的顺序插入。每个新键从根开始向下走，在走出树外的位置成为叶子。

查找 4 依次与 8、3、6、4 比较：在有七个键的树中比较了四次。查找 7 时依次与 8、3、6 比较，然后发现 6 没有右孩子，所以 7 不在树中。

Python 实现

插入和查找都是简短的循环。删除有三种情况：节点没有孩子（直接移除）、有一个孩子（用这个孩子替换它）、有两个孩子（复制它的中序后继，即右子树中最小的键，然后删除那个后继）。

class Node:
    def __init__(self, key):
        self.key, self.left, self.right = key, None, None
def insert(root, key):
    if root is None:
        return Node(key)
    if key < root.key:
        root.left = insert(root.left, key)
    elif key > root.key:
        root.right = insert(root.right, key)
    return root                      # duplicates are ignored
def contains(root, key):
    while root and root.key != key:
        root = root.left if key < root.key else root.right
    return root is not None
def delete(root, key):
    if root is None:
        return None
    if key < root.key:
        root.left = delete(root.left, key)
    elif key > root.key:
        root.right = delete(root.right, key)
    else:
        if root.left is None:
            return root.right
        if root.right is None:
            return root.left
        succ = root.right
        while succ.left:
            succ = succ.left
        root.key = succ.key
        root.right = delete(root.right, succ.key)
    return root
def inorder(root):
    return inorder(root.left) + [root.key] + inorder(root.right) if root else []

root = None
for k in [8, 3, 10, 1, 6, 14, 4]:
    root = insert(root, k)
print(inorder(root))                 # [1, 3, 4, 6, 8, 10, 14]
print(contains(root, 4), contains(root, 7))  # True False
root = delete(root, 3)               # node with two children
print(inorder(root), root.left.key)  # [1, 4, 6, 8, 10, 14] 4

时间与空间复杂度

最坏情况是真实存在的，而不是理论上的：把已排好序的键（1, 2, 3, ……）插入普通 BST，每个节点都只有右孩子，树就变成了链表。随机的插入顺序则给出期望高度 O(log n)。

平衡变体与常见错误

自平衡树在插入和删除之后通过旋转重新调整结构，使高度保持在 O(log n)。

• 只检查父子节点就验证 BST。应改为向下传递一个有效的 (low, high) 范围。
• 忘记从递归的插入和删除中返回（可能是新的）根节点，导致修改丢失。
• 在退化的树上深度递归：Python 默认递归限制约为 1000，所以 5000 个节点的链会让递归代码崩溃。请使用循环，或保持树平衡。
• 没有明确重复键的策略：要决定重复键是忽略、计数，还是总放在某一侧。

何时使用 BST，以及典型面试题

当你需要有序数据并且频繁插入和删除时，请使用平衡 BST：范围查询、向下取整和向上取整查找、排名统计，或按顺序遍历。如果只需要精确键查找，请使用哈希表。在 Python 中，标准库没有树形映射；常见选择是用 bisect 模块配合有序列表处理小规模或基本不变的数据，或者使用第三方包 sortedcontainers。

典型面试题：验证 BST、找第 k 小的元素（中序遍历）、最近公共祖先、把有序数组转换为平衡 BST（选中间元素作根），以及找出某个节点的中序后继。