形式陈述

红黑树是带颜色的二叉搜索树，常用不变量为：根黑；空叶哨兵黑；红节点的孩子均黑；从任一节点到其后代空叶的每条路径含相同黑节点数。于是任一路径长度至多最短路径的两倍，高度不超过 $2\log_2(n+1)$$2{\log }_2(n+1)$。插入和删除先按 BST 操作，再用常数次或 $O(\log n)$$O(\log n)$ 次重着色与旋转恢复不变量。

直觉

黑节点提供粗粒度完美平衡骨架，红节点允许在黑层之间插入有限松弛。不能出现连续红色，保证松弛不会累积成很长链。

例子与边界

插入新节点通常先着红色，避免立即改变所有根到叶路径的黑高；若父节点也红，则根据叔节点颜色重着色或旋转。删除黑节点更复杂，因为会造成一单位“黑高亏欠”。红黑树不是每个节点左右高度差至多一，那是 AVL 条件。不同教材对根是否必须黑、哨兵表示等约定略有差异，但高度结论等价。旋转本身不改变中序键序。

推论与应用

红黑树以较弱平衡换取较少更新旋转，广泛用于语言标准库的有序 map/set、内核调度结构和增广区间树。

参考资料

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022，Parts I–VI。
• Robert E. Tarjan, Data Structures and Network Algorithms, SIAM, 1983，Chs. 1–6。