红黑树（Red-Black Tree）
一句话说明
红黑树的目标不是“绝对平衡”，而是“别退化得太难看”，用较少调整把二叉搜索树的高度稳定在
O(log n)。
先别急着背 5 条性质
理解红黑树，最重要的一句话是：
红黑树是一棵“近似平衡”的二叉搜索树。它为什么不追求像 AVL 那样严格平衡？
- 因为严格平衡意味着更新时要做更多旋转
- 红黑树选择放松一点平衡要求
- 换来插入、删除时更稳定的工程表现
所以工程里很多有序 map / set 更喜欢红黑树。
经典 5 条性质
- 每个节点非红即黑。
- 根节点是黑色。
- 所有空叶子（NIL）视为黑色。
- 红节点的孩子必须是黑色。
- 任一节点到其所有叶子的路径，黑节点数量相同。
真正要抓住的是后两条：
- 不允许红红相连
- 每条路径黑高一致
这两件事一起约束了树高不会太离谱。
你可以这样理解“为什么它平衡”
红节点可以看成“临时粘在黑节点上的附属节点”。
如果把红节点向上收缩，红黑树就能类比成一棵多路平衡树。
这就是为什么红黑树虽然不是严格平衡，但仍然能保证：
高度 = O(log n)旋转本身并不难，难的是“何时旋”
红黑树操作真正难的地方，不是左旋右旋，而是：
- 什么时候变色
- 什么时候先旋再变色
- 什么时候问题会向上冒
所以学习红黑树时，建议先把旋转当成基础工具，再用一个更顺手的版本理解插入。
用左倾红黑树（LLRB）来理解更直观
很多资料会直接上标准 CLRS 红黑树修复分类，细节非常多。
从做题和理解角度，更推荐先看左倾红黑树（Left-Leaning Red-Black Tree）：
- 红链接默认左倾
- 插入后局部修正
- 本质仍然是红黑树
这样代码会短很多，也更适合 Go 演示。
Go 代码：节点定义
const (
red = true
black = false
)
type RBNode struct {
key int
color bool
left, right *RBNode
}Go 代码：基础辅助函数
func isRed(node *RBNode) bool {
return node != nil && node.color == red
}
func rotateLeft(h *RBNode) *RBNode {
x := h.right
h.right = x.left
x.left = h
x.color = h.color
h.color = red
return x
}
func rotateRight(h *RBNode) *RBNode {
x := h.left
h.left = x.right
x.right = h
x.color = h.color
h.color = red
return x
}
func flipColors(h *RBNode) {
h.color = !h.color
if h.left != nil {
h.left.color = !h.left.color
}
if h.right != nil {
h.right.color = !h.right.color
}
}这三个动作分别在干什么
rotateLeft：把右侧红链接转成左侧红链接rotateRight：处理连续左红链接flipColors：把一个临时 4-节点向上拆分
也就是说，修复逻辑其实是在不断维持局部结构合法。
Go 代码：插入
type RedBlackTree struct {
root *RBNode
}
func (t *RedBlackTree) Insert(key int) {
t.root = insert(t.root, key)
t.root.color = black
}
func insert(h *RBNode, key int) *RBNode {
if h == nil {
return &RBNode{
key: key,
color: red,
}
}
if key < h.key {
h.left = insert(h.left, key)
} else if key > h.key {
h.right = insert(h.right, key)
}
if isRed(h.right) && !isRed(h.left) {
h = rotateLeft(h)
}
if isRed(h.left) && isRed(h.left.left) {
h = rotateRight(h)
}
if isRed(h.left) && isRed(h.right) {
flipColors(h)
}
return h
}这段插入逻辑可以直接背成 3 条规则
从下往上回溯时：
- 右红左黑，左旋
- 左红且左左红，右旋
- 左右都红，变色
这就是 LLRB 风格最值钱的地方：
把原本复杂的插入修复压缩成几个稳定局部规则。
Go 代码：查找
func (t *RedBlackTree) Search(key int) bool {
cur := t.root
for cur != nil {
if key == cur.key {
return true
}
if key < cur.key {
cur = cur.left
} else {
cur = cur.right
}
}
return false
}为什么标准库爱用红黑树
因为它在工程上是很均衡的选择：
- 查找足够快
- 插入删除旋转次数通常较少
- 最坏复杂度稳定
- 不像 AVL 那样为了更矮的树付出更高更新代价
所以它特别适合“增删查都很多”的有序字典场景。
红黑树和 AVL 怎么选
红黑树更像
- 更新友好
- 近似平衡
- 工程取舍更强
AVL 更像
- 查找更极致
- 平衡更严格
- 更新时旋转更积极
这也是为什么 平衡二叉树 常被当作“理论上更规整”的代表，而红黑树更常落地到标准库实现。
复杂度
| 操作 | 时间复杂度 |
|---|---|
| 查找 | O(log n) |
| 插入 | O(log n) |
| 删除 | O(log n) |
易错点
学红黑树最容易卡住的地方
- 不要只背性质，不理解它们为什么控制树高。
- 左旋右旋本身不难，真正难的是修复触发条件。
- 红黑树不是严格平衡树，它只是把最坏高度压在
O(log n)。- 如果你是第一次系统学习，建议先从 LLRB 版本建立直觉。
经典题目 / 思考题
- 手写一棵支持插入和查找的红黑树
- 证明红黑树高度是
O(log n) - 比较红黑树、AVL 树、跳表的更新代价
- 理解
map/set为什么更偏爱红黑树