第 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）

性质：左子树所有值 < 根 < 右子树所有值。中序遍历即有序输出。demo binary_tree.cpp 的 BinaryTree 类用私有递归函数插入（重复值直接忽略）：

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* insertRecursive(TreeNode* node, int val) {
    if (node == nullptr) 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
5
int getBalance(AVLNode* node) {
    if (node == nullptr) return 0;
    return getHeight(node->left) - getHeight(node->right);
}
// insertRecursive 回溯时：更新 height → 检查 balance → 按 LL/RR/LR/RL 调用 rightRotate / leftRotate

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
7
8
9
enum Color { RED, BLACK };
struct RBNode {
    int val;
    Color color;
    RBNode* left;
    RBNode* right;
    RBNode* parent;
    RBNode(int x) : val(x), color(RED), left(nullptr), right(nullptr), parent(nullptr) {}
};

demo 的 RedBlackTree 用一个黑色哨兵 NIL 充当所有空叶子，新节点默认红色，插入后调用 fixInsert；只实现了插入与中序遍历，没有删除。

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]
  • 所有叶子同层
  • 节点满（2t−1 个 key）时分裂（splitChild）；demo 采用自顶向下预分裂：下降途中遇到满子节点先分裂，根满时新建根再分裂，树因此只会从根部长高
1
2
3
插入导致分裂：
  [10|20|30]  →  分裂  →  [20]  +  [10] [30]
  (3个key=2t−1 已满, t=2)    中间上推    两个子节点

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

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

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

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

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

1
parent(i) = (i-1)/2    left(i) = 2*i+1    right(i) = 2*i+2

demo heap.cpp 的 Heap 类用 isMaxHeap 同时支持最大堆/最小堆，下面只节选最大堆分支：

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

每个 .cpp 编译为同名可执行文件（CMake 中按 C++11 构建）：

1
2
3
cd ref/cpp_demo/algorithms/tree
./build.sh --run                 # 依次运行 5 个程序
./build.sh --run binary_tree     # 只运行一个（avl_tree / red_black_tree / b_tree / heap 同理）
demo 预期输出要点
binary_tree 插入 5,3,7,1,9,4,6 后四种遍历：中序 1 3 4 5 6 7 9，前序 5 3 1 4 7 6 9，后序 1 4 3 6 9 7 5，层序 5 3 7 1 4 6 9
avl_tree 插入 10,20,30,40,50,25 后中序 10 20 25 30 40 50
red_black_tree 插入 11 个数后中序有序，每个节点标注（红）/（黑）
b_tree 最小度数 t=3，插入 10,20,5,6,12,30,7,17 后遍历 5 6 7 10 12 17 20 30
heap 同一组数据分别建最大堆 / 最小堆，extractTop 依次取出 40 与 5

九、小结

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

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