红黑树

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

插入：先把折线变直，再旋转祖父 ​

用 B/R 表示黑/红，省略的孩子均为黑 NIL。依次插入 $10,5,7$：先有根 10B、左孩子 5R；新 7R 是 5R 的右孩子，出现红红冲突，叔节点是黑 NIL。先对 $5$ 左旋，局部链成为 10B →左 7R →左 5R；再将 $7$ 染黑、$10$ 染红，对 $10$ 右旋。最终根 7B，左右孩子为 5R,10R。中序键始终为 $5,7,10$，每条根到 NIL 路径都含两个黑节点（含根和 NIL）。若叔节点也红，应先将父、叔染黑、祖父染红并向上检查，而非套用这组旋转。

删除：用兄弟的远侧红孩子消除亏欠 ​

取根 10B，左孩子 5B，右孩子 15B，且 $15$ 的右孩子为 20R。删除黑叶 $5$ 后，$10$ 的左 NIL 少一个黑节点。其兄弟 15B 的远侧孩子 20R 为红，故把 $20$ 染黑，将 $15$ 设为父节点原来的黑色、$10$ 染黑，再对 $10$ 左旋。结果为根 15B、两个孩子 10B,20B，各根到 NIL 路径均有三个黑节点，亏欠消失。若兄弟和两个孩子都黑，则通常先把兄弟染红，把亏欠移给父节点；若兄弟红或仅近侧孩子红，还要先转换情形。这个轨迹只展开一个可核对的删除分支，完整分支见 CLRS §13.4。

红黑树不要求每个节点的左右高度差至多一，那是 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 次数。