红黑树

红黑树用黑节点提供粗粒度的完美平衡骨架，允许红节点在黑层之间插入有限松弛。局部颜色约束保证任意根到叶路径黑节点数相同，并禁止连续红节点，使松弛不会累积成长链：最短路径可以全黑，最长路径至多在每两个黑节点间插一个红节点，因此高度至多约为 $2{\log }_2(n+1)$。插入删除后的旋转保持二叉搜索次序，重新着色修复黑高与红红冲突。

插入新节点通常先着红色，避免立即改变所有根到叶路径的黑高；若父节点也红，则根据叔节点颜色重着色或旋转。删除黑节点更复杂，因为会造成一单位“黑高亏欠”：修复根据兄弟及其孩子的颜色选择重着色和旋转，要么在当前层消除亏欠，要么把它向父节点上移，直到到达根或被某个兄弟情形吸收。红黑树不是每个节点左右高度差至多一，那是 AVL 条件。不同教材对根是否必须黑、哨兵表示等约定略有差异，但高度结论等价。旋转本身不改变中序键序。

颜色规则的叶子通常包括统一的黑色 NIL 哨兵，而非只看真实节点；漏计会使黑高证明错误。旋转本身不自动恢复全部性质，必须与颜色更新配套；实现还需维护父指针和根颜色。

红黑树建立在二叉搜索树公理库二叉搜索树Binary search tree · BST每个结点左子树键小于、右子树键大于该结点键的二叉树。次序和平衡搜索树公理库平衡搜索树Balanced search tree以结构不变量保证对数高度和最坏对数搜索时间的二叉搜索树族。目标上，给最坏 $O(\log n)$ 查找、插入与删除。若节点再保存可由孩子合并的摘要，旋转必须同步重算；通用规则见搜索树增强公理库搜索树增强定理与方法Search-tree augmentation在搜索树节点维护可由局部子树摘要恢复的信息，并证明旋转后仍可常数更新。，维护子树大小并支持 rank/select 的具体接口见顺序统计树公理库顺序统计树order-statistic tree · dynamic order statistics在平衡搜索树中维护子树大小，动态支持按秩选择与键的秩查询。。

语言标准库的有序 map/set 常采用红黑树，是因为它在二叉指针 RAM 中兼顾最坏界与更新常数。B 树公理库B 树B-tree以高扇出、有界节点占用率和等深叶层降低外存查找 I/O 的平衡搜索树。则以多路节点和占用率适配外存块，把代价写成 I/O 次数；它不是给红黑树换一种颜色或简单增大分支度。增广字段、外存布局与红黑平衡分别承担不同问题。