红黑树

红黑结构仍按键大小划分左右子树，颜色用来表达额外的平衡信息。典型规则把空链接视为黑色，要求从一个节点到各空后继的黑色数量一致，并限制连续红色关系，从而阻止路径长度任意分化。

颜色不是业务键的属性，也不是图形上随意涂色。完成插入或删除后，结构必须恢复所规定的不变量；一次局部操作期间暂时出现某种形状，与最终对外提供一个有效的红黑树，是两个不同状态。

参考：[1]

教材中的左倾红黑树把2–3树的一个三节点表示为两个二叉节点，用一条向左的红链接连接。把这种红链接收缩回去，就可以看到多键节点的平衡结构；普通二叉搜索的查找逻辑仍然能够沿键顺序工作。

旋转改变红链接的朝向，变色把局部节点之间的组合关系向上调整。左倾是这种实现的额外约定，不能把它直接当作所有红黑树变体都采用的同一套程序；比较实现时要核对各自完成后承诺维持的规则。

参考：[1]

受这些约束限制，树高保持为键数量的对数级，查找与规定的插入、删除等操作具有对数级最坏上界。顺序插入不会像未经平衡的普通二叉搜索树那样，仅因输入已经有序就任意拉成单链。

结构也能保留有序接口，例如取最小键、最大键、上下界与范围计数。实现需同步维护这些操作依赖的辅助信息，并遵守键的比较规则；红黑平衡不会自动把不一致的比较器或外部私自修改的键修正成正确顺序。

参考：[1]