红黑树的性质与平衡操作

红黑树是一种自平衡的二叉搜索树，它在每个节点上增加一个存储位表示颜色（红或黑），通过对节点颜色的约束和旋转操作，确保树在插入和删除后保持近似平衡，从而保证基本操作的时间复杂度为O(log n)。下面我将详细讲解红黑树的性质和平衡操作。

红黑树的五个性质

1. 每个节点是红色或黑色。
2. 根节点是黑色。
3. 所有叶子节点（NIL节点，空节点）是黑色。
4. 红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。
5. 从任意节点到其所有后代叶子节点的路径上，黑色节点的数量相同（称为黑高平衡）。

这些性质保证了红黑树的关键特性：从根到最远叶子节点的路径长度不会超过到最近叶子节点路径长度的两倍，从而维持平衡。

平衡操作：旋转与颜色调整

当插入或删除节点破坏红黑树性质时，需要通过旋转和颜色调整来修复。旋转分为左旋和右旋，与AVL树类似，但红黑树的修复逻辑更复杂。

插入操作的平衡修复

插入新节点时，我们将其着色为红色（以避免破坏黑高），然后检查是否违反性质。修复过程分为三种情况（假设新节点为N，父节点为P，祖父节点为G，叔节点为U）：

• 情况1：叔节点U是红色

  • 操作：将P和U变为黑色，G变为红色（除非G是根）。然后将G视为新节点N，递归向上修复。
  • 原因：通过颜色翻转保持黑高，但可能使G违反性质（如G是根或G的父节点是红色）。

• 情况2：叔节点U是黑色，且N是P的右子节点（P是G的左子节点）

  • 操作：对P进行左旋，转换为情况3。此时N和P角色互换。

• 情况3：叔节点U是黑色，且N是P的左子节点（P是G的左子节点）

  • 操作：将P变为黑色，G变为红色，然后对G进行右旋。
  • 结果：修复了连续红色问题，且黑高保持不变。

对称情况（P是G的右子节点）类似，只需将左旋/右旋操作互换。

删除操作的平衡修复

删除节点时，如果删除的是黑色节点，会破坏黑高，需要修复。修复过程分为四种情况（假设被删除节点的替代节点为N，父节点为P，兄弟节点为S，S的左子节点为SL，右子节点为SR）：

• 情况1：兄弟节点S是红色

  • 操作：将S变为黑色，P变为红色，对P进行左旋（如果S是右子节点）或右旋（如果S是左子节点），转换为情况2、3或4。
  • 目的：将问题转化为S为黑色的情况。

• 情况2：兄弟节点S是黑色，且S的子节点都是黑色

  • 操作：将S变为红色，将P视为新节点N，递归向上修复。
  • 原因：通过减少S路径的黑高来平衡，但可能使P路径黑高不足。

• 情况3：兄弟节点S是黑色，且SL是红色（S是右子节点时）

  • 操作：将SL变为黑色，S变为红色，对S进行右旋，转换为情况4。
  • 目的：调整S的子节点颜色，为后续旋转做准备。

• 情况4：兄弟节点S是黑色，且SR是红色（S是右子节点时）

  • 操作：将S的颜色设为P的颜色，将P和SR变为黑色，对P进行左旋。
  • 结果：黑高恢复，所有性质满足。

对称情况类似，需调整旋转方向。

总结

红黑树通过颜色约束和旋转操作，以较少的旋转次数（插入最多2次旋转，删除最多3次旋转）维持平衡。虽然平衡性不如AVL树严格，但修复开销更小，适合频繁插入删除的场景（如Linux内核内存管理）。理解红黑树的关键在于掌握五种性质及其修复逻辑的对称性。