你有没有想过一个尴尬的局面：有序数组查找快（二分 O(log n)），可一旦插入新元素，得把后面一半整体后挪，O(n)；链表插入是 O(1)，可查找又退化成 O(n)。有没有一种结构，能既要查找快、又要插入/删除也快？

答案就是本篇的主角——树，更准确地说是**二叉搜索树（BST）**以及它的「打补丁」版本：平衡树（AVL / 红黑树）和多路平衡树（B 树）。它们把「有序」从「数组的连续内存」里解放出来，变成「节点之间的偏序关系」，于是插入、删除不再需要搬移整段数据。我们先从最朴素的 BST 讲起，再看它哪里会翻车，以及三个补丁分别怎么修。

一、二叉搜索树（BST）：定义与不变式

BST = 一棵二叉树，且满足「左小右大」的递归不变式：

对树上任意一个节点 x：其左子树中所有 key 都 < x.key，其右子树中所有 key 都 > x.key。

注意是「严格」的偏序，通常不允许重复 key（要支持重复就改成「≤ 放左 / ≥ 放右」，本篇按不允许重复讲，逻辑最干净）。这条不变式是 BST 一切能力的根基——因为它意味着中序遍历（左→根→右）必然得到升序序列。

50 30 70 20 40 60 80

中序遍历这棵树：20 → 30 → 40 → 50 → 60 → 70 → 80，完美升序。这就是 BST 的「免费排序」特性。

二、BST 的核心操作（Java 实现）

下面是一份可直接编译运行的 BST 骨架：插入、查找、中序遍历、删除。注意删除有两子节点的情况——我们找**右子树的最小节点（中序后继）**来顶替被删节点，从而保住不变式。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
public class BST {
    static class Node {
        int key;
        Node left, right;
        Node(int k) { key = k; }
    }
    Node root;

    // 插入（忽略重复 key）
    void insert(int key) { root = insert(root, key); }
    private Node insert(Node n, int key) {
        if (n == null) return new Node(key);
        if (key < n.key)      n.left  = insert(n.left, key);
        else if (key > n.key) n.right = insert(n.right, key);
        return n;                       // 相等：什么都不做
    }

    // 查找
    boolean contains(int key) { return contains(root, key); }
    private boolean contains(Node n, int key) {
        if (n == null) return false;
        if (key == n.key) return true;
        return key < n.key ? contains(n.left, key) : contains(n.right, key);
    }

    // 中序遍历（左-根-右）
    void inorder() { inorder(root); System.out.println(); }
    private void inorder(Node n) {
        if (n == null) return;
        inorder(n.left);
        System.out.print(n.key + " ");
        inorder(n.right);
    }

    // 删除
    void delete(int key) { root = delete(root, key); }
    private Node delete(Node n, int key) {
        if (n == null) return null;
        if (key < n.key)      n.left  = delete(n.left, key);
        else if (key > n.key) n.right = delete(n.right, key);
        else {
            if (n.left == null)  return n.right;   // 无左子
            if (n.right == null) return n.left;    // 无右子
            n.key = minKey(n.right);               // 两子皆有：用后继顶替
            n.right = delete(n.right, n.key);
        }
        return n;
    }
    private int minKey(Node n) { while (n.left != null) n = n.left; return n.key; }

    public static void main(String[] a) {
        BST t = new BST();
        int[] ks = {50, 30, 70, 20, 40, 60, 80};
        for (int k : ks) t.insert(k);

        System.out.print("插入后中序: "); t.inorder();
        System.out.println("contains(40) = " + t.contains(40));
        System.out.println("contains(99) = " + t.contains(99));

        t.delete(50);                              // 删根（两子皆有）
        System.out.print("删除 50 后中序: "); t.inorder();
        t.delete(20);                              // 删叶子
        System.out.print("再删 20 后中序: "); t.inorder();
    }
}

编译运行后输出：

1
2
3
4
5
插入后中序: 20 30 40 50 60 70 80
contains(40) = true
contains(99) = false
删除 50 后中序: 20 30 40 60 70 80
再删 20 后中序: 30 40 60 70 80

小观察：删掉根 50 后，顶替它的是右子树最小者 60，于是新根变成 60，中序序列依旧有序。这条「用后继顶替」的规则，是 BST 删除不出错的关键。

三、BST 的软肋：退化成链表

BST 的查询复杂度不是固定的 O(log n)，而是等于树高。如果插入顺序恰好是升序（或降序），树会退化成一条链：

10 20 30 40 只剩右链 h = n

此时树高 = 节点数，所有操作退化到 O(n)——和普通链表没两样。问题的本质是：BST 没有约束「左右子树要差不多高」。于是引出第一个补丁：平衡树，它的全部努力就是「别让树歪了」。

四、平衡树：用「旋转」把树拉直

**旋转（rotation）**是平衡树的核心原子操作：它在不破坏 BST 不变式（中序序列不变）的前提下，重新组织局部结构，降低树高。最常见的是右旋（right rotation）和左旋（left rotation），互为镜像。

右旋前（LL 型） y x c a b → 右旋后 x a y c b

右旋前后，中序序列都是 a → x → b → y → c，顺序丝毫没变，但原本以 y 为根、左子树过深的结构被「掰直」了。下面给出 AVL 里最基础的两种旋转（带高度维护）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
static class AVLNode {
    int key, height;
    AVLNode left, right;
    AVLNode(int k) { key = k; height = 1; }
}
static int h(AVLNode n) { return n == null ? 0 : n.height; }

// 右旋：y 的左子 x 上位
static AVLNode rightRotate(AVLNode y) {
    AVLNode x = y.left, t = x.right;
    x.right = y;
    y.left  = t;
    y.height = 1 + Math.max(h(y.left), h(y.right));
    x.height = 1 + Math.max(h(x.left), h(x.right));
    return x;                       // 新子树根
}
// 左旋是右旋的镜像：y 的右子 x 上位，x.left 接到 y.right

AVL 树：严格平衡

AVL 给每个节点加一个平衡因子 bf = h(left) − h(right)，并强制 |bf| ≤ 1。一旦插入/删除破坏了这个条件，就按四种情形之一做旋转：LL（右旋）、RR（左旋）、LR（先左后右）、RL（先右后左）。代价是每次操作都要维护高度和做可能的旋转，插入/删除略慢，但查询极快（O(log n) 且常数很小），适合查询远多于写入的场景。

红黑树：近似平衡

红黑树放宽了要求，改用「颜色」约束——这正是下一节的主角，也是 BST 家族里工程最常用的一种。

本质一句话（提前剧透）：平衡树 = BST + 「用旋转维持树高 ≈ log n」。AVL 偏「严」（查询快），红黑树偏「松」（增删快），殊途同归都是 O(log n)。

五、红黑树：近似平衡的精髓

红黑树和 AVL 干的是同一件事——给 BST 上一把「平衡锁」，防止退化成链表。区别只在锁的松紧：

  • AVL：锁得死，|平衡因子| ≤ 1，查询极快，但每次插入删除可能触发多次旋转。
  • 红黑树：锁得松，只要求「近似平衡」，旋转次数更少、增删更快，查询只比 AVL 略慢。

工程里红黑树更常见：TreeMap、std::map、很多语言的有序容器底层都是它。取舍很清晰：用一点点查询速度，换大量增删速度。

下面这棵树是合法的红黑树，先让它把五条性质变具体：

Red-black tree example 一个合法红黑树：黑根 13，黑子 8 与 17，红叶 1、11、15、25。每条根到叶路径含 2 个黑节点（黑高相等），且无相邻红节点。 13 8 17 1 11 15 25 黑高=2（各路径黑节点数相等）；无连续红节点 → 树高 ≤ 2·log₂n

5 条性质，以及每条「为什么存在」

# 性质 为什么需要它
1 节点非红即黑 定义
2 根必须是黑 让边界统一，少一种特例
3 红节点的子节点必为黑（无连续红） 高度界的关键之一
4 任一节点到所有叶子（NIL）的路径，黑节点数相等（黑高相等） 高度界的关键之二
5 叶子（NIL）为黑 和 2 一起让边界好处理

注意：(3) 和 (4) 才是真正起作用的两条，其余几条主要是让算法实现少分情况。

高度界推导：把「≈ log n」从直觉变成不等式

这是红黑树最该想通的一点，分两步。

第一步：由 (3)+(4) 得到 h ≤ 2·bh。

  • 因为 (3)「无连续红」：任意一条路径上，红节点不能挨着红节点，所以黑节点至少占一半（最密也就是红黑红黑交替，1:1）。
  • 因为 (4)「黑高相等」：设黑高为 bh，那么最短路径就是一路全黑 = bh 个节点；最长路径就是红黑交替 = 2·bh 个节点。
  • 于是 最长路径 ≤ 2 × 最短路径，整棵树高度 h ≤ 2·bh。

第二步：用「二叉树的逻辑」把 bh 和 n 连起来。

黑高为 bh 的树，节点数至少有 2^bh − 1 个。为什么？把红节点全部隐去，剩下的黑骨架本身是一棵二叉树：

Black skeleton gives the binary-tree lower bound 左：完整红黑树；右：隐去红节点后的黑骨架，是一棵 bh=2 的二叉树，至少 2^2-1=3 个黑节点。 13 8 17 1 11 15 25 → 13 8 17 隐去红节点 → 黑骨架是一棵 bh=2 的二叉树，至少 2^2-1 = 3 个黑节点（13·8·17）
  • 黑骨架要从根到每个叶子都恰好走过 bh 个黑节点（性质 4）；
  • 一棵高度为 bh 的二叉树，最少也有 2^bh − 1 个节点（满二叉树才达到这个下界，缺一个枝就到不了 bh 层）；
  • 我们隐去红节点只是「拿走」了一部分，黑骨架节点数只会比总节点数少、不会多；红节点本来就是额外加在黑骨架上的。

所以：黑节点数 ≥ 2^bh − 1，进而总节点数 n ≥ 2^bh − 1 → bh ≤ log₂(n+1)。

联立两步：

1
2
3
4
h ≤ 2·bh           （来自 无红红 + 黑高相等）
bh ≤ log₂(n+1)     （来自 二叉树下界 2^bh − 1 ≤ n）
──────────────────
h ≤ 2·log₂(n+1) = O(log n)    常数因子 ≤ 2

这正是普通二叉树的底层事实——「高为 H 的二叉树至少 2^H − 1 个节点」——只不过这里把「高」换成了「黑高」。二分查找的 log n 也是同一个不等式倒过来，所以红黑树的高度天然落在 log n 量级。(3)+(4) 两条性质，通过这串不等式硬推出来「高度 ≈ log n」；二叉树的 2^H − 1 下界，就是连接 bh 与 n 的那座桥。

内拐 / 外拐：插入修复看形状

插入红节点 z 后，它和父 y（红）冲突（红红）。此时祖父 x（黑）必然是黑（否则插入前就不合法）。看 x、y、z 三个点的形状，决定转几次：

Red-black insert: outer vs inner cases 左：外拐 LL，祖-父-子同向成直线；右：内拐 LR，父与子反向成之字。 外拐（LL） x y z y左、z左（都偏左） 内拐（LR） x y z y左、z右（反向） 外拐→在祖父 x 上单旋；内拐→先转父 y 再转祖 x（双旋）
  • 外拐（outer / 直线 / LL·RR）：z 在「外侧」——y 和 z 相对 x 偏向同一侧（y 左孩子、z 也左孩子，或都右）。三点成一条线 → 在祖父 x 上单旋即可，再重新染色。
  • 内拐（inner / 之字 / LR·RL）：z 在「内侧」——y 和 z 反向（y 左孩子、z 右孩子，或反过来）。三点成之字形 → 先转父 y 把自己掰直成外拐，再转祖 x（双旋）。

这和 AVL 完全同构：AVL 里 LL/RR 单旋、LR/RL 双旋；红黑「外拐单旋、内拐双旋」是同一个几何直觉，只是红黑还额外伴随重新染色。

插入修复的 before / after

外拐（LL）：左边是插入 1 后出现的红红冲突，右边是修完的样子。

Outer LL case: before and after fix 左：3黑-2红-1红 成直线且红红冲突；右：右旋+染色后得到 2黑 挂 1红、3红 的合法树。 3 2 1 → 2 1 3 改前：红红冲突 改后：合法平衡

内拐（LR）：它多了一步——先「转父」把自己掰直成外拐，再「转祖」得到同样结果。

Inner LR case: three steps to fix 左：3黑-1红-2红 之字冲突；中：左转父1后变成直线外拐；右：右转祖3后收敛为合法小三角。 3 1 2 → 3 2 1 → 2 1 3 改前：之字 转父后：直线 改后：合法

插入算法总览

  1. 先按 BST 规则插入，新节点一律染红（染红不会破坏性质 (4) 黑高，最多只破坏 (3) 无红红 或 (2) 根黑——把风险缩到最小）。
  2. 若破坏，只在局部动手：
    • 叔节点是红 → 重新染色，把「红红冲突」往上推一层（像把麻烦甩给老爸）；
    • 叔节点是黑、且是「内拐」 → 先转一下变成「外拐」；
    • 叔节点是黑、且是「外拐」 → 旋转 + 染色，一次性修好。
  3. 最后算法强制根必为黑。

无论内拐外拐，修复完都收敛成「黑根 + 两个红孩子」的合法小三角，树高被压平。这就是红黑树插入的全部武器：recolor（叔红时） + rotate（叔黑时），外拐单旋、内拐双旋。

删除比插入难：删掉黑节点会破坏 (4) 黑高，得靠「借黑 / 转移黑」来补，情况更多（会出现「红-黑-黑」叠加态）。本篇聚焦插入修复，删除留作后续专题。

六、B 树：为磁盘 / 数据库而生的多路平衡树

前面这些树都假设整棵树在内存里、比较一次代价极低。可数据库要把数据放在磁盘上，磁盘 IO 一次就读一「页」（几 KB），而树高每多一层就多一次随机 IO。普通 BST/AVL 每个节点只存一个 key、分两叉，树高 log₂n——一亿条数据就得 log₂(10⁸) ≈ 27 层，也就是 27 次磁盘 IO，太慢。

B 树的解法是：让一个节点存多个 key、分多叉，把「矮胖」做到极致。

10 20 30 一个磁盘页（节点） <10 10-20 20-30 >30

B 树要求：所有叶子在同一层（真正外存友好的关键），每个内部节点有 m 个 key、m+1 个分叉（m 即「阶」）。同样是 1 亿条数据，若每页存 100 个 key，树高降到 log₁₀₀(10⁸) ≈ 4 层——4 次 IO 就能定位，比 27 次快了一个数量级。这也是为什么 MySQL（InnoDB）、PostgreSQL 的索引几乎都建立在 B 树（及其变体 B+ 树）之上。

三种树的适用场景对比

结构 平衡方式 树高 典型用途
AVL 高度严格平衡（` bf ≤1`）
红黑树 颜色近似平衡（≤2×） 低 内存中、增删频繁（如 TreeMap）
B / B+ 树 多路、叶子同层 极矮（按页） 磁盘 / 数据库索引

七、C++ 对照速览

在 C++ 标准库里，树的影子无处不在，只是被封装成了容器：

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <map>
#include <unordered_map>
#include <iostream>

int main() {
    std::map<int, std::string> m;      // 红黑树，key 有序，O(log n)
    m[50] = "a"; m[30] = "b"; m[70] = "c";
    for (auto& kv : m) std::cout << kv.first << " "; // 升序：30 50 70

    std::unordered_map<int, std::string> u; // 哈希表，平均 O(1)，无序
    u[50] = "a"; u[30] = "b";
    // 遍历顺序不确定
}

要点对照：

  • std::map / std::set 底层是红黑树，遍历有序、单次操作 O(log n)——和 Java 的 TreeMap 是同一个思路。
  • std::unordered_map 底层是哈希表，平均 O(1) 但无序——当你不需要有序、只求快时用它。
  • Java 侧对应物：TreeMap（红黑树，有序）vs HashMap（哈希，无序）。选型逻辑在两种语言里完全一致。

如果手写 BST 插入，C++ 与 Java 几乎同构，只是内存管理从「GC」换成「new / 裸指针（或 unique_ptr）」：

1
2
3
4
5
6
7
struct Node { int key; Node* left = nullptr; Node* right = nullptr; };
Node* insert(Node* n, int k) {
    if (!n) return new Node{k};
    if (k < n->key) n->left  = insert(n->left, k);
    else if (k > n->key) n->right = insert(n->right, k);
    return n;
}

八、收尾：一句话带走

本质一句话：树把「有序」从数组的连续内存搬到了节点间的偏序关系上，于是插入/删除不再搬运整段数据。BST 是地基，平衡树（AVL / 红黑）用旋转把树高压在 log n，B 树用「多路 + 同层叶子」把树高压到能塞进几次磁盘 IO——从内存到数据库，一以贯之。

本篇从 BST 的「免费排序」讲到它的退化软肋，再用旋转引出平衡树；重点拆透了红黑树：五条性质为什么存在、(3)+(4) 如何借二叉树的 2^H−1 下界推出高度 ≤ 2·log n、内/外拐如何决定单旋还是双旋，最后用 B 树把视角从内存拉到磁盘。

本篇对应 CS61B 第 5 讲：树。代码均可在本地 JDK / 支持 C++17 的编译器直接编译运行。