平衡树与高级树
00:00
二叉搜索树、AVL树、红黑树、B树与B+树的原理、旋转操作与工程应用，涵盖数据库索引核心数据结构。
1. 二叉搜索树（BST）
1.1 BST 的定义
二叉搜索树（Binary Search Tree）满足以下性质：
- 左子树所有节点的值 小于 根节点的值
- 右子树所有节点的值 大于 根节点的值
- 左右子树也分别是二叉搜索树
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 131.2 BST 的基本操作
// Java：BST 节点定义与基本操作
public class BST<E extends Comparable<E>> {
private static class Node<E> {
E value;
Node<E> left, right;
Node(E value) { this.value = value; }
}
private Node<E> root;
// 查找
public boolean contains(E target) {
return search(root, target) != null;
}
private Node<E> search(Node<E> node, E target) {
if (node == null) return null;
int cmp = target.compareTo(node.value);
if (cmp < 0) return search(node.left, target);
else if (cmp > 0) return search(node.right, target);
else return node;
}
// 插入
public void insert(E value) {
root = insert(root, value);
}
private Node<E> insert(Node<E> node, E value) {
if (node == null) return new Node<>(value);
int cmp = value.compareTo(node.value);
if (cmp < 0) node.left = insert(node.left, value);
else if (cmp > 0) node.right = insert(node.right, value);
return node;
}
// 删除
public void delete(E value) {
root = delete(root, value);
}
private Node<E> delete(Node<E> node, E value) {
if (node == null) return null;
int cmp = value.compareTo(node.value);
if (cmp < 0) node.left = delete(node.left, value);
else if (cmp > 0) node.right = delete(node.right, value);
else {
// 找到目标节点
if (node.left == null) return node.right;
if (node.right == null) return node.left;
// 有两个子节点：用后继节点替换
Node<E> successor = findMin(node.right);
node.value = successor.value;
node.right = delete(node.right, successor.value);
}
return node;
}
private Node<E> findMin(Node<E> node) {
while (node.left != null) node = node.left;
return node;
}
}1.3 BST 的退化问题
BST 的性能高度依赖于树的形状：
| 情况 | 树高 | 查找复杂度 |
|---|---|---|
| 平衡 | O(log n) | O(log n) |
| 退化成链 | O(n) | O(n) |
平衡 BST: 退化 BST (链表):
5 1
/ \ \
2 8 2
/ \ \ \
1 3 9 3
\
4
\
5平衡树的出现正是为了解决这个问题。
2. AVL 树
2.1 AVL 树的定义
AVL 树是最早被发明的自平衡二叉搜索树，由 Adelson-Velsky 和 Landis 于 1962 年提出。它要求：
任意节点的平衡因子（左子树高度 - 右子树高度）的绝对值不超过 1。
平衡因子 = height(left) - height(right)
合法范围: -1, 0, 12.2 四种失衡情况与旋转
插入或删除后，如果某节点的平衡因子超出 [-1, 1]，需要通过旋转恢复平衡：
| 失衡类型 | 条件 | 修复操作 |
|---|---|---|
| LL | 左子树的左子树过深 | 右旋（单旋） |
| RR | 右子树的右子树过深 | 左旋（单旋） |
| LR | 左子树的右子树过深 | 先左旋再右旋（双旋） |
| RL | 右子树的左子树过深 | 先右旋再左旋（双旋） |
右旋（LL 型）
y x
/ \ / \
x T3 → T1 y
/ \ / \
T1 T2 T2 T3左旋（RR 型）
x y
/ \ / \
T1 y → x T3
/ \ / \
T2 T3 T1 T22.3 AVL 树的完整实现
// Java：AVL 树
public class AVLTree<E extends Comparable<E>> {
private static class Node<E> {
E value;
Node<E> left, right;
int height;
Node(E value) { this.value = value; this.height = 1; }
}
private Node<E> root;
private int height(Node<E> node) {
return node == null ? 0 : node.height;
}
private int balanceFactor(Node<E> node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
private void updateHeight(Node<E> node) {
node.height = 1 + Math.max(height(node.left), height(node.right));
}
// 右旋
private Node<E> rotateRight(Node<E> y) {
Node<E> x = y.left;
Node<E> T2 = x.right;
x.right = y;
y.left = T2;
updateHeight(y);
updateHeight(x);
return x;
}
// 左旋
private Node<E> rotateLeft(Node<E> x) {
Node<E> y = x.right;
Node<E> T2 = y.left;
y.left = x;
x.right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
// 平衡操作
private Node<E> balance(Node<E> node) {
updateHeight(node);
int bf = balanceFactor(node);
// LL 型
if (bf > 1 && balanceFactor(node.left) >= 0) {
return rotateRight(node);
}
// LR 型
if (bf > 1 && balanceFactor(node.left) < 0) {
node.left = rotateLeft(node.left);
return rotateRight(node);
}
// RR 型
if (bf < -1 && balanceFactor(node.right) <= 0) {
return rotateLeft(node);
}
// RL 型
if (bf < -1 && balanceFactor(node.right) > 0) {
node.right = rotateRight(node.right);
return rotateLeft(node);
}
return node;
}
public void insert(E value) {
root = insert(root, value);
}
private Node<E> insert(Node<E> node, E value) {
if (node == null) return new Node<>(value);
int cmp = value.compareTo(node.value);
if (cmp < 0) node.left = insert(node.left, value);
else if (cmp > 0) node.right = insert(node.right, value);
else return node; // 不允许重复
return balance(node);
}
}2.4 AVL 树复杂度
| 操作 | 平均 | 最坏 |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
AVL 树的查找效率极高，但插入和删除时可能需要多次旋转（最多 O(log n) 次），因此在频繁修改的场景中性能不如红黑树。
3. 红黑树
3.1 红黑树的五条性质
红黑树是一种近似平衡的二叉搜索树，通过着色规则和旋转来维持平衡：
- 每个节点是红色或黑色
- 根节点是黑色
- 每个叶子节点（NIL）是黑色
- 红色节点的两个子节点都是黑色（不能有连续的红节点）
- 从任意节点到其每个叶子的所有路径都包含相同数目的黑色节点（黑高相同）
B(13)
/ \
R(8) B(17)
/ \ / \
B(1) B(11) B(15) R(25)
/ \ / \ / \ / \
N N N N N N N N
B = 黑色节点, R = 红色节点, N = NIL（黑色哨兵）3.2 红黑树 vs AVL 树
| 维度 | AVL 树 | 红黑树 |
|---|---|---|
| 平衡标准 | 严格（高度差 ≤ 1） | 近似（黑高相同） |
| 查找效率 | 更高（更矮） | 略低 |
| 插入旋转次数 | 最多 O(log n) | 最多 2 次 |
| 删除旋转次数 | 最多 O(log n) | 最多 3 次 |
| 适用场景 | 查找密集 | 修改密集 |
| 工程应用 | Windows 进程地址空间 | Java TreeMap、C++ map、Linux CFS |
3.3 红黑树插入修复
新插入的节点默认为红色。插入后可能违反性质 4（红色节点不能连续），需要修复：
# Python：红黑树插入修复伪代码
def insert_fixup(tree, z):
while z.parent.color == RED:
if z.parent == z.parent.parent.left:
y = z.parent.parent.right # 叔叔节点
if y.color == RED:
# Case 1：叔叔是红色 → 变色
z.parent.color = BLACK
y.color = BLACK
z.parent.parent.color = RED
z = z.parent.parent
else:
if z == z.parent.right:
# Case 2：叔叔是黑色，z 是右孩子 → 左旋
z = z.parent
left_rotate(tree, z)
# Case 3：叔叔是黑色，z 是左孩子 → 变色 + 右旋
z.parent.color = BLACK
z.parent.parent.color = RED
right_rotate(tree, z.parent.parent)
else:
# 对称情况
pass
tree.root.color = BLACK3.4 红黑树删除修复
删除节点后可能违反性质 5（黑高相同），修复更复杂，涉及 4 种情况：
# Python：红黑树删除修复伪代码
def delete_fixup(tree, x):
while x != tree.root and x.color == BLACK:
if x == x.parent.left:
w = x.parent.right # 兄弟节点
if w.color == RED:
# Case 1：兄弟是红色 → 变色 + 左旋
w.color = BLACK
x.parent.color = RED
left_rotate(tree, x.parent)
w = x.parent.right
if w.left.color == BLACK and w.right.color == BLACK:
# Case 2：兄弟的两个子节点都是黑色 → 兄弟变红
w.color = RED
x = x.parent
else:
if w.right.color == BLACK:
# Case 3：兄弟的右子节点是黑色 → 变色 + 右旋
w.left.color = BLACK
w.color = RED
right_rotate(tree, w)
w = x.parent.right
# Case 4：兄弟的右子节点是红色 → 变色 + 左旋
w.color = x.parent.color
x.parent.color = BLACK
w.right.color = BLACK
left_rotate(tree, x.parent)
x = tree.root
else:
# 对称情况
pass
x.color = BLACK3.5 红黑树复杂度
| 操作 | 平均 | 最坏 |
|---|---|---|
| 查找 | O(log n) | O(log n) |
| 插入 | O(log n) | O(log n) |
| 删除 | O(log n) | O(log n) |
红黑树的高度最多为 2·log₂(n+1)，虽然比 AVL 树略高，但修改操作的旋转次数有上界，是工程实践中的首选。
4. B 树
4.1 B 树的定义
B 树是一种多路平衡搜索树，专为磁盘等外存设备设计。一棵 m 阶 B 树满足：
- 每个节点最多有 m 个子节点（m-1 个关键字）
- 每个非根节点至少有 ⌈m/2⌉ 个子节点
- 根节点至少有 2 个子节点（若非叶）
- 所有叶子节点位于同一层
- 节点内的关键字有序排列
3 阶 B 树（2-3 树）：
[30 | 70]
/ | \
[10|20] [40|50|60] [80|90]4.2 B 树的查找
# Python：B 树查找
def b_tree_search(node, key):
i = 0
# 在当前节点中找到第一个 >= key 的位置
while i < len(node.keys) and key > node.keys[i]:
i += 1
if i < len(node.keys) and key == node.keys[i]:
return (node, i) # 找到
if node.is_leaf:
return None # 未找到
# 递归搜索子节点（需要从磁盘读取）
return b_tree_search(node.children[i], key)4.3 B 树的插入
插入可能导致节点分裂：
插入 25 到 3 阶 B 树：
分裂前: [10 | 20 | 25] ← 超出容量(m-1=2)
↓
分裂后: [20]
/ \
[10] [25]4.4 B 树的删除
删除可能导致节点合并或借用：
- 若节点关键字足够，直接删除
- 若不足，向兄弟借用或与兄弟合并
4.5 B 树为什么适合磁盘
| 特性 | 说明 |
|---|---|
| 多路分支 | 减少树高，减少磁盘 I/O 次数 |
| 节点大小匹配块 | 一个节点对应一个磁盘块（4KB） |
| 高扇出低树高 | 百万数据只需 3-4 层 |
假设 m=200，4 层 B 树可存储:
200^4 = 1,600,000,000（16亿条记录）
仅需 4 次磁盘 I/O5. B+ 树
5.1 B+ 树与 B 树的区别
B+ 树是 B 树的变体，在数据库索引中被广泛使用：
| 维度 | B 树 | B+ 树 |
|---|---|---|
| 数据存储位置 | 所有节点都存数据 | 仅叶子节点存数据 |
| 内部节点 | 存关键字和数据 | 仅存关键字（索引） |
| 叶子节点链接 | 无 | 链表连接（范围查询高效） |
| 查找路径 | 可能在中间节点命中 | 必须到叶子节点 |
| 关键字重复 | 不重复 | 内部节点关键字在叶子中重复出现 |
B+ 树结构：
[30 | 70] ← 内部节点：仅存关键字
/ | \
[10|20|30] [40|50|60|70] [80|90] ← 叶子节点：存完整数据
↔ ↔ ↔ ← 叶子节点链表连接5.2 B+ 树的优势
# B+ 树范围查询：查找 [30, 70] 之间的所有记录
def range_query(bplus_tree, low, high):
# 1. 从根到叶找到 low（O(log n)）
leaf = find_leaf(bplus_tree.root, low)
# 2. 沿叶子链表顺序扫描（O(k)，k 为结果数）
results = []
while leaf is not None:
for key, value in leaf.records:
if key > high:
return results
if key >= low:
results.append(value)
leaf = leaf.next # 沿链表前进
return results关键优势：
- 范围查询高效：叶子链表使范围扫描无需回溯上层
- 内部节点更紧凑：不存数据，同样磁盘块可存更多关键字，树更矮
- 查询性能稳定：每次查询都走到叶子，路径长度相同
5.3 B+ 树在数据库中的应用
| 数据库 | B+ 树索引实现 |
|---|---|
| MySQL(InnoDB) | 聚簇索引 + 二级索引 |
| PostgreSQL | B-tree 索引 |
| SQLite | B+ 树变体 |
| MongoDB | WiredTiger B+ 树索引 |
-- MySQL InnoDB 的 B+ 树索引
-- 聚簇索引：叶子节点存储完整行数据
-- 二级索引：叶子节点存储主键值（回表查询）
CREATE TABLE users (
id INT PRIMARY KEY, -- 聚簇索引（B+ 树）
name VARCHAR(50),
age INT,
INDEX idx_age (age) -- 二级索引（B+ 树）
);
-- 查询走二级索引 → 回表到聚簇索引获取完整数据
SELECT * FROM users WHERE age = 25;6. 各类平衡树对比总结
| 树类型 | 平衡标准 | 树高 | 插入旋转 | 删除旋转 | 主要应用 |
|---|---|---|---|---|---|
| BST | 无 | O(n) 最坏 | 0 | 0 | 教学 |
| AVL | 高度差 ≤ 1 | ≤ 1.44log₂n | O(log n) | O(log n) | 查找密集场景 |
| 红黑树 | 黑高相同 | ≤ 2log₂(n+1) | ≤ 2 | ≤ 3 | 通用平衡搜索树 |
| B 树 | 叶子同层 | O(log_m n) | 分裂 | 合并/借用 | 文件系统 |
| B+ 树 | 叶子同层 + 链表 | O(log_m n) | 分裂 | 合并/借用 | 数据库索引 |
6.1 选择指南
需要平衡搜索树？
│
├─ 数据在内存中？
│ ├─ 查找远多于修改 → AVL 树
│ └─ 修改频繁 → 红黑树
│
└─ 数据在磁盘上？
├─ 需要范围查询 → B+ 树
└─ 只需点查询 → B 树7. 工程实践中的红黑树
7.1 Java TreeMap
// Java TreeMap 底层是红黑树
TreeMap<Integer, String> map = new TreeMap<>();
map.put(3, "three");
map.put(1, "one");
map.put(2, "two");
// 有序遍历（中序）
for (Map.Entry<Integer, String> e : map.entrySet()) {
System.out.println(e.getKey() + "=" + e.getValue());
}
// 输出: 1=one, 2=two, 3=three
// 范围查询
Map<Integer, String> sub = map.subMap(1, 3); // [1, 3)7.2 C++ std::map
// C++ std::map/set 底层是红黑树
std::map<int, std::string> m;
m[3] = "three";
m[1] = "one";
m[2] = "two";
// 有序遍历
for (auto& [k, v] : m) {
std::cout << k << "=" << v << std::endl;
}
// 范围查询
auto it = m.lower_bound(2);
auto end = m.upper_bound(3);7.3 Linux CFS 调度器
Linux 完全公平调度器（Completely Fair Scheduler）使用红黑树管理进程：
- 节点键值：进程的虚拟运行时间（vruntime）
- 最左节点：vruntime 最小的进程（最该被调度）
- 插入/删除：O(log n)
8. 总结
平衡树是保证二叉搜索树性能的关键技术。AVL 树通过严格的平衡条件提供最优查找性能，红黑树通过宽松的平衡条件换取更高效的修改操作，B 树和 B+ 树则通过多路分支适配磁盘 I/O 特性。理解这些数据结构的设计权衡，是深入理解数据库索引、文件系统和语言标准库的基础。