FHCY-Study06-AVL / 红黑树
type
status
date
slug
summary
tags
category
icon
password
AVL树 和 红黑树（Red-Black Tree）都是为了解决二叉搜索树在插入/删除时可能失衡的问题所设计的自平衡二叉搜索树（Self-Balancing BST），但它们的设计哲学、性能折中和实现细节不同。
1️⃣ AVL树（Adelson-Velsky and Landis Tree）
✅ 特点
- 每个节点记录平衡因子（左右子树高度差）
- 任意节点的左右子树高度差不超过1
- 插入/删除后可能需要多次旋转来恢复平衡
🧮 平衡因子
balanceFactor = height(left) - height(right)
- 平衡因子 ∈ {-1, 0, 1}
🔄 旋转操作
- LL：右旋
- RR：左旋
- LR：先左旋后右旋
- RL：先右旋后左旋
🕹️ 适用场景
- 频繁查询（AVL 树更“严格平衡”）
- 数据变化不频繁的查找密集型场景
2️⃣ 红黑树（Red-Black Tree）
✅ 特点
- 每个节点额外有一个颜色属性（红或黑）
- 满足红黑五大性质（见下）
- 插入/删除后通过变色+旋转维持平衡，最多旋转一次
🧮 红黑树性质（重点）
- 每个节点非红即黑
- 根节点是黑色
- 每个叶子节点（NIL）是黑色
- 红色节点不能连续（不能有两个连续的红节点）
- 从任一节点到其所有叶子路径上的黑节点数相同
上述性质确保了：最坏高度 ≤
若某条路径的黑色节点数为bh，那么总高度最多是：
红黑树中，黑高为 bh的最少节点数为：
因此：
这就是红黑树的最坏高度上限
- 插入新节点：默认颜色为红色
- 若违反红黑性质（如出现红红），则需做：
- 颜色变换
- 左旋 / 右旋 / 双旋
- 最后确保根节点为黑色
🔄 平衡手段
- 插入：变色 + 旋转（最多一次）
- 删除：变色 + 多次旋转或递归调整
🕹️ 适用场景
- 插入/删除频繁，读写均衡（如 TreeMap/TreeSet）
- 红黑树在工业场景中比 AVL 更常用（如 Java 的
TreeMap、Linux内核）
3️⃣ AVL 与 红黑树对比总结
对比项 | AVL树 | 红黑树 |
平衡性 | 严格平衡，高度更低 | 相对平衡，高度略高 |
插入/删除效率 | 可能多次旋转，较慢 | 最多一次旋转，效率更高 |
查询效率 | 更快（因为高度更低） | 稍慢 |
应用场景 | 读多写少 | 读写均衡 |
典型应用 | 内存索引、少量变动的大数据查询 | Java TreeMap、Linux调度等 |
- AVL 树 更适合查找频繁、更新少的场景
- 红黑树 更适合高并发、频繁插入/删除的业务场景，是工业应用的主力
上一篇
05-二叉树
下一篇
07-图
Loading...