二叉搜索树与平衡树

哈希表给出 $O(1)$ 查找，但不支持有序。需要范围查询、按序遍历、前驱后继时，平衡二叉搜索树是标准答案。本章讲 BST 的性质、失衡问题，以及红黑树与 B 树两种工程主流。

二叉搜索树（BST）

BST 性质：左子树所有节点 < 根 < 右子树所有节点。查找、插入、删除都是沿树下降：

T(n) = O(h), \qquad h \text{ 为树高}.

平衡时 $h = O(\log n)$ ，退化成链时 $h = O(n)$ ——按序插入 1..n 就得到一条链。平衡树的全部内容就是：在修改时用少量旋转保持 $h = O(\log n)$ 。

删除操作要处理三种情况：叶子直接删、单孩子接上、双孩子用**后继（右子树最小值）**替换后转成删除后继。

平衡的两种哲学

AVL 树：严格平衡

每个节点维护左右子树高度差 $\le 1$ ，插入删除时用旋转恢复。树高更严格（ $\approx 1.44 \log n$ ），查找更快；但修改时旋转更多。适合读多写少。

红黑树：近似平衡

用"红/黑"着色约束保证树高 $\le 2\log(n+1)$ ：从根到叶子的最长路径不超过最短路径的两倍。修改时旋转更少（插入至多 2 次、删除至多 3 次旋转），写更快。红黑树是工程主流：Linux 内核（CFS 调度器、内存区域）、C++ std::map、Java TreeMap（→ CPU 调度）。

class Node:
    def __init__(self, key, val):
        self.key, self.val = key, val
        self.left = self.right = None

def search(node, key):
    while node and node.key != key:
        node = node.left if key < node.key else node.right
    return node

def insert(node, key, val):
    if node is None:
        return Node(key, val)
    if key < node.key:
        node.left = insert(node.left, key, val)
    elif key > node.key:
        node.right = insert(node.right, key, val)
    else:
        node.val = val
    return node

B 树与 B+ 树：为磁盘而生

BST 的每个节点存一个键、一次比较一次缓存行。磁盘时代的问题是树高 = 磁盘 I/O 次数（→ 索引与 B+ 树）。B 树让每个节点存几十上百个键（一个节点一个磁盘页），树高从几十降到三四层——100 万条数据只需 3 次页访问。B+ 树进一步把数据全放叶子、内部节点只放路标、叶子串成链表——范围查询变成顺序扫描，成为数据库索引的事实标准。

平衡树谱系的选择逻辑：

结构	每节点键数	树高	适用
AVL / 红黑树	1	$O(\log n)$	内存、读多（AVL）或读写均衡（红黑）
B / B+ 树	$O(B)$ （块大小）	$O(\log_B n)$	磁盘、数据库索引
跳表	概率多级	$O(\log n)$ 期望	无旋转实现、并发友好（Redis、LevelDB）

本章要点

BST 的操作代价是 $O(h)$ ：平衡 $O(\log n)$ ，退化 $O(n)$
平衡树 = 修改时用旋转保持树高：AVL 严格平衡读快，红黑近似平衡写快
红黑树是内存有序结构的工程主流（内核、std::map）
B+ 树以大节点把树高降到磁盘 I/O 可承受的三四层，叶子链表支持范围扫描
跳表用概率实现无旋转的 $O(\log n)$ ，并发友好