7.3.3 红黑树

红黑树满足根黑、空叶黑、红结点孩子黑、任一点到后代空叶黑高相同。由此最长路径不超过最短路径两倍，高度O(log n)。它用较弱平衡换取较少旋转，常用于动态集合。

手工推演

向只有黑根10的树插5，默认新结点红，无冲突。再插1，父5红、叔为空黑，形成LL：右旋10并交换5与10颜色，得到黑5、红1、红10。

结构与代码

插入修复分叔红（父叔变黑、祖父变红后向上）与叔黑（旋转并变色）。删除黑结点可能产生双黑，需依据兄弟颜色及孩子颜色修复。

正确性

颜色与旋转保持BST次序；黑高和禁止连续红共同给高度上界。

错解反馈

把红黑树当AVL要求高度差1；新结点染黑导致所有路径黑高变化；漏把空指针视黑叶。

迁移训练

红结点能有红父亲吗？答案不能；否则违反红结点孩子必须黑。