红黑树如何保持平衡

红黑树是一种自平衡的二叉查找树，通过以下特性来保持平衡：

1. 节点颜色：每个节点要么是红色，要么是黑色。红黑树的根节点是黑色的。

2. 红色节点特性：

如果一个节点是红色的，那么它的子节点必须是黑色的（不允许两个红色节点相邻）。

3. 黑色高度一致性：

从任一节点到其每个叶节点的所有路径都包含相同数目的黑色节点。

具体来说，红黑树通过以下规则来维护这些特性：

插入规则：

1. 新插入的节点默认为红色。

2. 如果父节点是黑色，则树保持平衡。

3. 如果父节点是红色，需要检查叔叔节点（父节点的兄弟节点）的颜色：

如果叔叔节点是红色，则父节点和叔叔节点都变为黑色，祖父节点变为红色。

如果叔叔节点是黑色，则需要根据父节点和叔叔节点的位置进行旋转操作，调整颜色，以保持树的平衡。

删除规则：

1. 如果删除的是黑色节点，可能会导致树失去平衡，需要根据情况对树进行调整。

2. 删除操作与插入操作类似，也需要进行一系列的旋转和颜色调整，以确保树的平衡。

红黑树的旋转操作主要包括：

左旋：当右子节点的左子节点需要插入时使用。

右旋：当左子节点的右子节点需要插入时使用。

通过上述规则和旋转操作，红黑树能够保证在任何情况下都保持平衡，即任意节点的左右子树的高度差不超过1，从而确保查找、插入和删除操作的时间复杂度均为O(log n)。