红黑树平衡变换

红黑树平衡变换图解

注意：此页面为平衡树的补充。

变化情况

1. 叔叔节点(父亲节点的兄弟节点)为红，变色 + 继续向上更新。变色过程如下：

   • 将 P，U 节点染黑，将 G 节点染红（可以保证每条路径上黑色节点个数不发生改变）。
   • 递归维护 G 节点（因为不确定 G 的父节点的状态，递归维护可以确保性质 3 成立）。

   

2. 叔叔不存在，或者叔叔存在且为黑，旋转 + 变色。

如何旋转（满足上述变化情况2的基础上）

• 当前节点 N 与父节点 P的方向相同：（类似 AVL 树中 LL 和 RR 的情况）
  • N 节点为右子节点且父节点为右子节点
  • N 节点为左子节点且父节点为左子节点。

• 当前节点 N 与父节点 P 的方向相反：（类似 AVL 树中 LR 和 RL 的情况），谋权篡位。
  • N 节点为右子节点且父节点为左子节点。
  • N 节点为左子节点且父节点为右子节点。

注意：这里直接使用了(LL,LR的图片，N和P的编号发生了改变，但实际LR（RL）改变中不会发生)