当前位置：首页 > java >正文

【JAVA】红黑树详解

java 2025/7/1 2:49:50

红黑树

红黑树（Red-Black Tree）是 TreeMap 底层实现的一种自平衡二叉搜索树。红黑树的特性保证了在最坏情况下基本操作（如插入、删除、查找）的时间复杂度为 O(log n)。以下是红黑树的详细介绍，包括其性质、插入与删除操作、平衡调整机制等。

1. 红黑树的性质

红黑树是一种特殊的二叉搜索树，具有以下五个基本性质：

节点是红色或黑色：红黑树中的每个节点都是红色或黑色。
根节点是黑色：红黑树的根节点必须是黑色的。
叶节点（NIL节点）是黑色的：红黑树的每个叶节点（空节点，即null节点）都是黑色的。
红色节点的子节点必须是黑色：即在一条路径上，不能有两个连续的红色节点。红色节点的子节点可以是黑色节点或 null 节点。
从任一节点到其每个叶节点的所有路径都包含相同数量的黑色节点：这个属性确保了树的平衡性，避免了极端不平衡的情况。

这些性质保证了红黑树的平衡性，即树的最长路径不会超过最短路径的两倍，确保了查找、插入和删除操作的效率。

2. 红黑树的核心操作

红黑树的核心在于如何在插入和删除节点时保持树的平衡。为此，红黑树使用了旋转（Rotation）和重新着色（Recoloring）两种主要操作。

2.1 旋转（Rotation）

旋转是红黑树维护平衡性的重要操作。旋转分为两种：左旋和右旋。

左旋（Left Rotation）：左旋操作是将当前节点的右子节点变为其父节点，并将当前节点变为新的父节点的左子节点。
例子：假设节点 x 需要进行左旋。

     x                        y/ \                      / \a   y     ====>           x   c/ \                  / \b   c                a   b

右旋（Right Rotation）：右旋操作是将当前节点的左子节点变为其父节点，并将当前节点变为新的父节点的右子节点。
例子：假设节点 y 需要进行右旋。

       y                        x/ \                      / \x   c    ====>           a   y/ \                          / \a   b                        b   c

2.2 插入操作

当一个新节点插入红黑树时，它初始为红色。插入操作后，红黑树可能会违反其性质，需要通过旋转和重新着色来恢复红黑树的性质。
插入的步骤：

普通的二叉搜索树插入：将节点插入到红黑树中，初始颜色为红色。插入位置遵循二叉搜索树的规则。
调整树结构：根据插入节点的位置，可能会违反红黑树的性质，因此需要对树进行调整。根据插入节点的父节点、叔叔节点的颜色，有以下几种情况：
- 情况 1: 插入节点的父节点是黑色：不需要做任何调整，因为树的性质没有被破坏。
- 情况 2: 插入节点的父节点是红色，且叔叔节点也是红色：将父节点和叔叔节点涂黑，将祖父节点涂红，然后将祖父节点作为新的插入节点，继续检查。
- 情况 3: 插入节点的父节点是红色，但叔叔节点是黑色：
  - 左左情况：父节点是祖父节点的左子节点，插入节点是父节点的左子节点。右旋祖父节点，交换父节点和祖父节点的颜色。
  - 左右情况：父节点是祖父节点的左子节点，插入节点是父节点的右子节点。左旋父节点，形成左左情况，再进行右旋和颜色交换。
  - 右右情况：父节点是祖父节点的右子节点，插入节点是父节点的右子节点。左旋祖父节点，交换父节点和祖父节点的颜色。
  - 右左情况：父节点是祖父节点的右子节点，插入节点是父节点的左子节点。右旋父节点，形成右右情况，再进行左旋和颜色交换。
调整完成后：确保根节点为黑色，以维护红黑树的性质。

2.3 删除操作

删除节点的操作比插入复杂得多，因为删除节点可能会导致多种红黑树性质被破坏。删除操作同样依赖旋转和重新着色来恢复平衡。
删除的步骤：

找到并删除节点：根据二叉搜索树的删除规则找到并删除目标节点。如果被删除的节点有两个子节点，则用其直接后继节点替换该节点，然后删除后继节点。
调整树结构：删除节点后，红黑树可能会违反其性质，因此需要进行调整。
- 情况 1: 删除的节点是红色：如果删除的是红色节点，红黑树的性质不会被破坏，不需要做额外操作。
- 情况 2: 删除的节点是黑色，且其唯一的子节点是红色：将子节点涂黑即可，树的性质不会被破坏。
- 情况 3: 删除的节点是黑色，且其子节点是黑色：此时，需要根据兄弟节点的颜色及其子节点的颜色进行复杂的调整，包括旋转和重新着色。主要有以下几种情况：
  - 兄弟节点是红色：将兄弟节点涂黑，父节点涂红，然后以父节点为中心左旋或右旋。
    兄弟节点是黑色且两个子节点都是黑色：将兄弟节点涂红，重新将父节点视为新的被删除节点，继续检查。
  - 兄弟节点是黑色，兄弟的一个子节点是红色：根据兄弟子节点的颜色进行旋转和重新着色。
  - 确保根节点为黑色：删除调整完成后，必须确保根节点为黑色，以维持红黑树的性质。

3. 代码实现

红黑树的核心操作在 TreeMap 的源码中体现得非常清晰。以下是红黑树在 TreeMap 中的几个关键方法。
3.1 插入操作的调整代码 (fixAfterInsertion)

private void fixAfterInsertion(Entry<K,V> x) {x.color = RED;while (x != null && x != root && x.parent.color == RED) {if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {Entry<K,V> y = rightOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == rightOf(parentOf(x))) {x = parentOf(x);rotateLeft(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateRight(parentOf(parentOf(x)));}} else {Entry<K,V> y = leftOf(parentOf(parentOf(x)));if (colorOf(y) == RED) {setColor(parentOf(x), BLACK);setColor(y, BLACK);setColor(parentOf(parentOf(x)), RED);x = parentOf(parentOf(x));} else {if (x == leftOf(parentOf(x))) {x = parentOf(x);rotateRight(x);}setColor(parentOf(x), BLACK);setColor(parentOf(parentOf(x)), RED);rotateLeft(parentOf(parentOf(x)));}}}root.color = BLACK;
}

分析：

插入节点后，通过 while 循环检查并调整树的平衡性。
如果父节点是红色，可能会违反红黑树的性质，需要进行调整。
根据父节点的位置和兄弟节点的颜色，通过旋转和重新着色来恢复平衡。

3.2 删除操作的调整代码 (fixAfterDeletion)

private void fixAfterDeletion(Entry<K,V> x) {while (x != root && colorOf(x) == BLACK) {if (x == leftOf(parentOf(x))) {Entry<K,V> sib = rightOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateLeft(parentOf(x));sib = rightOf(parentOf(x));}if (colorOf(leftOf(sib)) == BLACK &&colorOf(rightOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(rightOf(sib)) == BLACK) {setColor(leftOf(sib), BLACK);setColor(sib, RED);rotateRight(sib);sib = rightOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(rightOf(sib), BLACK);rotateLeft(parentOf(x));x = root;}} else { // symmetricEntry<K,V> sib = leftOf(parentOf(x));if (colorOf(sib) == RED) {setColor(sib, BLACK);setColor(parentOf(x), RED);rotateRight(parentOf(x));sib = leftOf(parentOf(x));}if (colorOf(rightOf(sib)) == BLACK &&colorOf(leftOf(sib)) == BLACK) {setColor(sib, RED);x = parentOf(x);} else {if (colorOf(leftOf(sib)) == BLACK) {setColor(rightOf(sib), BLACK);setColor(sib, RED);rotateLeft(sib);sib = leftOf(parentOf(x));}setColor(sib, colorOf(parentOf(x)));setColor(parentOf(x), BLACK);setColor(leftOf(sib), BLACK);rotateRight(parentOf(x));x = root;}}}setColor(x, BLACK);
}