二叉搜索树

二叉搜索树（Binary Search Tree，BST）是带有序性的二叉树：任意节点都满足「左子树所有节点 < 根 < 右子树所有节点」。它让查找像二分一样每次砍掉一半，平均复杂度 O(log n)，是理解 AVL、红黑树等平衡树以及有序集合实现的基础。

基本性质

BST 的关键性质是中序遍历得到递增序列，常用它来验证一棵树是否为 BST，也可以直接当作排序工具。

        8
       / \
      3   10
     / \    \
    1   6    14
       / \
      4   7

对上面这棵树做中序遍历：1 3 4 6 7 8 10 14，正好从小到大。

查找与插入

查找从根开始：目标比当前节点小就走左子树，大就走右子树，相等即命中。插入按同样的比较规则一路找空位，新节点总是挂在叶子位置，插入后仍是 BST。

def search(root, val):
    if root is None or root.val == val:
        return root            # 找到或到底未找到
    if val < root.val:
        return search(root.left, val)   # 去左子树
    return search(root.right, val)      # 去右子树

def insert(root, val):
    if root is None:
        return Node(val)       # 找到空位，生成新节点
    if val < root.val:
        root.left = insert(root.left, val)
    elif val > root.val:
        root.right = insert(root.right, val)
    return root                # 相等时不做任何事（去重）

删除节点

删除分三种情况：

• 叶子节点：直接删除即可。
• 只有一个孩子：让孩子顶替被删节点。
• 有两个孩子：用「右子树的最小节点」或「左子树的最大节点」替换被删节点，再删掉那个替身（它最多只有一个孩子）。

删除值为 3 的节点（有两个孩子）：
        8                        8
       / \                      / \
      3   10    用右子树最小    4   10
     / \    \   值 4 替换     / \    \
    1   6    14  再删替身    1   6    14
       / \
      4   7

退化与自平衡

若按升序依次插入（1、2、3、4…），BST 会退化成一条链，查找复杂度退化为 O(n)。解决办法是让树保持平衡：AVL 树要求左右子树高度差不超过 1，红黑树用颜色规则保证近似平衡，使树高始终约为 log n。Java 的 TreeMap、C++ 的 map 内部正是红黑树，都是「BST + 自平衡」的工程实现。

复杂度与面试要点

操作	平均	最坏（退化成链）
查找	O(log n)	O(n)
插入	O(log n)	O(n)
删除	O(log n)	O(n)

• 高频题：验证二叉搜索树（中序递增）、BST 第 K 小元素、把有序数组转成平衡 BST。
• 答 BST 删除时先分「叶子 / 单孩子 / 双孩子」三情况，双孩子用替身节点，思路就清晰。
• 能说出「有序插入会导致退化，因此工程上用平衡树」是重要的加分点。

小结：BST 用「左小右大」换来二分式的查找效率，前提是不退化；中序有序、插入即叶子、平衡化这三个关键词足以串起全部考点。