红黑树平衡原理

红黑树平衡原理

红黑树是一种自平衡二叉搜索树，保证操作在最坏情况下O(log n)时间。

定义规则

1. 节点红色或黑色
2. 根节点是黑色
3. 叶节点NIL是黑色
4. 红色节点的子节点必须是黑色
5. 任一节点到叶节点的路径包含相同数目的黑节点

黑高度

从节点到叶节点的黑节点数
记为bh(x)
性质：bh(x) >= h(x)/2

平衡操作

旋转
左旋：右子节点上移，自己下沉
右旋：左子节点上移，自己下沉
O(1)时间完成

变色
改变节点颜色
配合旋转保持性质

插入修复

情况1：叔节点是红色
父节点和叔节点变黑
祖父节点变红
继续向上修复

情况2：叔节点是黑色
旋转和变色组合
最多两次旋转恢复

删除修复

更复杂，需要分类讨论
最多三次旋转
保证树的高度平衡

时间复杂度

查找：O(log n)
插入：O(log n)
删除：O(log n)

对比AVL树

AVL树更严格平衡，查找更快
红黑树插入删除更快
实际应用红黑树更常见

应用场景

C++的std::map
Java的TreeMap
Linux内核的进程调度
epoll的事件管理

实现要点

递归还是迭代
哨兵节点简化边界
维护父指针
旋转时更新引用