第 20 篇 的链表是「一对一」串联；树则是一对多的分支结构。从二叉搜索树到 AVL、红黑树、B 树、堆——五种经典树形结构，覆盖了内存索引、STL 容器、优先队列和磁盘存储的核心场景。

demo：ref/cpp_demo/algorithms/tree/（binary_tree、avl_tree、red_black_tree、b_tree、heap）。

这是「现代 C++ 实战」系列的第 21 篇。建议先读 第 20 篇：栈、队列与链表。

一、五种树，一张选型地图

结构 平衡策略 查找 插入 典型场景
BST 无保证 O(h) O(h) 教学、小规模有序数据
AVL 严格平衡 O(log n) O(log n) 查找密集、更新较少
红黑树 近似平衡 O(log n) O(log n) std::map / std::set
B 树 多路平衡 O(log n) O(log n) 数据库索引、文件系统
堆 堆序性质 O(n) 查任意 O(log n) 优先队列、Top-K 
1
2
3
4
5
6
7
8
9
10
11
12
13
BST（可能退化成链）     AVL（高度差 ≤ 1）     红黑树（黑高平衡）
       5                      30                    20(B)
      / \                    /  \                   /    \
     3   7                  20   40               10(R)  30(R)
    /                         /                      \
   1                          25                      40(B)

B 树（多子节点，磁盘友好）          堆（完全二叉树，数组存储）
    [10 | 20]                          [40]
   /    |    \                        /  \
[5,6] [12] [30]                     [20]  [30]
                                    /  \   /  \
                                  [10][15][25][5]

二、二叉搜索树（BST）

性质：左子树所有值 < 根 < 右子树所有值。中序遍历即有序输出。

1
2
3
4
5
6
7
8
9
10
11
12
struct TreeNode {
    int val;
    TreeNode* left, *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* insert(TreeNode* node, int val) {
    if (!node) return new TreeNode(val);
    if (val < node->val)      node->left  = insert(node->left, val);
    else if (val > node->val) node->right = insert(node->right, val);
    return node;
}

遍历四种方式：

遍历 顺序 用途
前序 根 → 左 → 右 复制树、序列化
中序 左 → 根 → 右 有序输出
后序 左 → 右 → 根 释放内存
层序 逐层 BFS 最短路径、打印层级

层序遍历用 std::queue<TreeNode*>，与 第 20 篇 的队列实现一脉相承。

隐患：按升序插入 1,2,3,...,n 会退化成链表，高度 h = n，查找退化为 O(n)。

三、AVL 树：严格平衡

平衡因子 = 左子树高度 − 右子树高度，绝对值 ≤ 1。插入后若失衡，通过旋转恢复：

1
2
3
4
5
6
右旋（LL）：          左旋（RR）：
    y                    x
   / \                  / \
  x   T3    →         T1  y
 / \                      / \
T1 T2                   T2 T3

四种失衡与修复：

类型 形态 操作
LL 左子树的左边过高 右旋
RR 右子树的右边过高 左旋
LR 左子树的右边过高 先左旋左子，再右旋
RL 右子树的左边过高 先右旋右子，再左旋 
1
2
3
4
int getBalance(AVLNode* node) {
    return node ? getHeight(node->left) - getHeight(node->right) : 0;
}
// 插入后：更新 height → 检查 balance → 按需旋转

AVL 保证高度 O(log n)，查找最优；但每次插入可能触发多次旋转，写入开销高于红黑树。

四、红黑树：STL 的底层

std::map、std::set 在 libstdc++ / libc++ 中通常基于红黑树实现。五条规则（简化记忆）：

  1. 节点红或黑
  2. 根是黑色
  3. 叶子（NIL）是黑色
  4. 红节点的子节点必须是黑
  5. 任意路径黑节点数相同（黑高）

近似平衡：最长路径 ≤ 2 × 最短路径 → 高度 O(log n)。

插入后通过变色 + 旋转修复（fixInsert）。相比 AVL，旋转次数更少，插入/删除更快，查找略慢——工程上更均衡。

1
2
3
4
5
6
enum Color { RED, BLACK };
struct RBNode {
    int val;
    Color color;
    RBNode *left, *right, *parent;
};

C++ 日常开发直接用 STL 即可：

1
2
3
4
#include <map>
#include <set>
std::map<int, std::string> m;   // 有序，O(log n)
std::set<int> s;                // 去重 + 有序

五、B 树：为磁盘而生

内存中指针跳转成本低；磁盘 I/O 昂贵——一次读一个扇区（4 KB），不如一次多读几个 key。B 树的节点可以容纳多个 key 和多个子指针：

  • 阶数为 t：非根节点 key 数 ∈ [t−1, 2t−1]
  • 所有叶子同层
  • 节点满时分裂（splitChild），向上传播
1
2
3
插入导致分裂：
  [10|20|30]  →  分裂  →  [20]  +  [10] [30]
  (4个key, t=2)              中间上推    两个子节点

应用：MySQL InnoDB 索引、文件系统目录。B+ 树是变体（数据只在叶子，叶子链表串联），更适合范围扫描。

六、堆：完全二叉树 + 数组

堆不是 BST——只保证堆序性质：

  • 最大堆：父 ≥ 子，根是最大值
  • 最小堆：父 ≤ 子，根是最小值

用 std::vector 存储，下标关系：

1
parent(i) = (i-1)/2    left(i) = 2*i+1    right(i) = 2*i+2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
void heapifyUp(int i) {
    if (i == 0) return;
    if (heap[parent(i)] < heap[i]) {
        std::swap(heap[parent(i)], heap[i]);
        heapifyUp(parent(i));
    }
}

void heapifyDown(int i) {
    int largest = i, l = left(i), r = right(i);
    if (l < heap.size() && heap[l] > heap[largest]) largest = l;
    if (r < heap.size() && heap[r] > heap[largest]) largest = r;
    if (largest != i) { std::swap(heap[i], heap[largest]); heapifyDown(largest); }
}

STL 优先队列：

1
2
3
4
#include <queue>
std::priority_queue<int> maxHeap;                    // 默认最大堆
std::priority_queue<int, std::vector<int>,
    std::greater<int>> minHeap;                        // 最小堆

应用：堆排序 O(n log n)、Dijkstra 的优先队列、Top-K 问题、任务调度。

七、选型指南

你的需求 推荐
有序 map/set，通用场景 std::map / std::set（红黑树）
只需最大/最小，不需全序 std::priority_queue（堆）
查找远多于写入 AVL 或跳表
大量磁盘数据索引 B 树 / B+ 树
算法题、理解原理 手写 BST + 遍历
需要 O(1) 均摊插入均摊查找 哈希表（第 19 篇）

不要过度设计：90% 的场景 std::map + std::priority_queue 足够。

八、运行 5 个 demo

1
2
3
4
5
6
cd ref/cpp_demo/algorithms/tree
g++ -std=c++17 -o binary_tree binary_tree.cpp && ./binary_tree
g++ -std=c++17 -o avl_tree avl_tree.cpp && ./avl_tree
g++ -std=c++17 -o red_black_tree red_black_tree.cpp && ./red_black_tree
g++ -std=c++17 -o b_tree b_tree.cpp && ./b_tree
g++ -std=c++17 -o heap heap.cpp && ./heap
demo 预期输出要点
binary_tree 四种遍历：中序 1 3 4 5 6 7 9
avl_tree 插入 10,20,30,40,50,25 后仍有序
red_black_tree 中序有序，节点标注红/黑
b_tree 多 key 节点，中序遍历有序
heap 最大堆 pop 40，最小堆 pop 5

九、小结

要点 内容
BST 左 < 根 < 右，中序有序，可能退化
AVL 严格平衡，旋转修复，查找优
红黑树 近似平衡，STL map/set 底层
B 树 多路节点，磁盘友好，数据库索引
堆 完全二叉树 + 数组，优先队列

下一篇进入图：BFS 找最短、DFS 找路径、Dijkstra 算权重——见 第 22 篇：图算法（计划）。