具有隐式 NIL 叶子的红黑树

2.3 红黑树的性质

以下规则强制红黑树平衡：

1. 每个节点要么是红色，要么是黑色。
2. （根部是黑色的。）
3. 所有 NIL 叶子都是黑色的。
4. 红色节点一定不能有红色子节点。
5. 从一个节点到下面的叶子的所有路径都包含相同数量的黑色节点。

规则 2 放在括号中，因为它不影响树的平衡。如果红色根的子节点也是红色的，则根据规则 4，该根必须被涂成黑色。但是，如果红色根只有黑色子节点，则将根涂成黑色没有任何优势。

因此，文献中经常省略规则2。

在解释插入和删除操作以及 Java 代码时，我会指出如果我们也实现规则 2 会有什么不同。提前说这么多：每个操作的区别只有一行代码:)

顺便说一句，根据规则 4 和规则 5，红色节点总是有两个 NIL 叶子节点或两个带值的黑色子节点。如果它有一个 NIL 叶子节点和一个带值的黑色子节点，那么通过这个子节点的路径至少会比到 NIL 叶子节点的路径多一个黑色节点，这将违反规则 5。

2.4 红黑树的高度

我们将红黑树的高度称为从根到 NIL 叶子的最大节点数，不包括根。上例中红黑树的高度为 4：

根据规则 3 和规则 4 可知：

从根到叶子的最长路径（不包括根）最多是从根到叶子的最短路径的两倍。

这很容易解释：

假设最短路径（除根节点外）有n 个黑色节点，没有红色节点。那么我们可以在每个黑色节点前添加另外n 个红色节点，而不会违反规则 3（我们可以将其改写为：任何两个红色节点都不能相互跟随）。

下面的示例左侧显示了通过高度为 4 的红黑树的最短路径，右侧显示了最长路径：

到左侧 NIL 叶子的路径的长度（不包括根）为 2。到右下方 NIL 叶子的路径的长度为 4。

2.5 红黑树的黑色高度

黑色高度是从给定节点到其叶子的黑色节点数。黑色 NIL 叶子被计算在内，起始节点则不被计算在内。

整棵树的黑色高度是从根（这个不算）到NIL叶子的黑色节点的数量。

目前显示的所有红黑树的黑色高度为 2。

3. 红黑树Java实现

作为用 Java 实现红黑树的起点，我使用了二叉树系列第二部分中的二叉搜索树的 Java 源代码。
节点用Node 类来表示。为了简单起见，我们使用int原语作为节点值。
为了实现红黑树，除了子节点left和right之外，我们还需要对父节点和节点颜色的引用。我们将颜色存储在中boolean，将红色定义为false，将黑色定义为true。

public class Node {
  int data;

  Node left;
  Node right;
  Node parent;

  boolean color;

  public Node(int data) {
    this.data = data;
  }
}

我们在类中实现红黑树RedBlackTree。此类扩展了BaseBinaryTree本系列第二部分中介绍的类（本质上提供了一个getRoot()函数）。
我们将在后面的部分逐步添加操作（插入、搜索、删除）。
但首先，我们必须定义一些辅助函数。

4. 红黑树旋转

插入和删除的工作基本上与二叉搜索树的文章中描述的一样。
插入和删除后，将检查红黑规则（见上文）。如果违反了规则，则必须恢复规则。这可以通过重新着色节点和旋转来实现。
旋转的工作原理与我在上一篇教程中描述的AVL 树完全相同。我将在这里再次向您展示相应的图表。您可以在刚刚提到的文章的“AVL 树旋转”部分中找到详细的解释。

4.1 右旋转

下图展示了右旋转。颜色与红黑树的颜色无关。它们仅用于更好地跟踪节点移动。

左节点L成为新的根节点；根节点N成为其右子节点。旋转前的左节点L的右子节点LR成为旋转后的右节点N的左子节点。两个白色节点LL和R 的相对位置不变。

Java 代码比 AVL 树稍长 – 原因如下：

1. 我们还需要更新parent节点的引用（在 AVL 树中，我们在没有parent引用的情况下工作）。
2. 我们需要更新对旋转前顶节点父节点（图中的N ）的引用 。对于 AVL 树，我们通过返回旋转后的子树的新根并将旋转“挂钩”到插入和删除操作的递归调用中来间接实现此操作。

右旋转的实现：

private void rotateRight(Node node) {
  Node parent = node.parent;
  Node leftChild = node.left;

  node.left = leftChild.right;
  if (leftChild.right != null) {
    leftChild.right.parent = node;
  }

  leftChild.right = node;
  node.parent = leftChild;

  replaceParentsChild(parent, node, leftChild);
}

最后调用的方法设置了旋转后子树的原根节点N的父节点和它的新根节点LreplaceParentsChild()之间的父子关系。

private void replaceParentsChild(Node parent, Node oldChild, Node newChild) {
  if (parent == null) {
    root = newChild;
  } else if (parent.left == oldChild) {
    parent.left = newChild;
  } else if (parent.right == oldChild) {
    parent.right = newChild;
  } else {
    throw new IllegalStateException("Node is not a child of its parent");
  }

  if (newChild != null) {
    newChild.parent = parent;
  }
}

4.2 左旋转

左旋转的工作原理类似：右节点R向上移动到顶部。根N成为R的左子节点。原右节点R的左子节点RL成为旋转后左节点N的右子节点。L和RR不会改变它们的相对位置。

以下是左旋转的 Java 代码：

private void rotateLeft(Node node) {
  Node parent = node.parent;
  Node rightChild = node.right;

  node.right = rightChild.left;
  if (rightChild.left != null) {
    rightChild.left.parent = node;
  }

  rightChild.left = node;
  node.parent = rightChild;

  replaceParentsChild(parent, node, rightChild);
}

5. 红黑树操作

与任何二叉树一样，红黑树提供查找、插入和删除节点的操作。我们将在以下部分逐步介绍这些操作。

5.1 红黑树搜索

搜索的工作原理与任何二叉搜索树一样：我们首先将搜索关键字与根进行比较。如果搜索关键字较小，我们继续在左子树中搜索；如果搜索关键字较大，我们继续在右子树中搜索。

我们重复此操作，直到找到我们要查找的节点，或者直到到达 NIL 叶（在 Java 代码中：引用null）。到达 NIL 叶意味着我们要查找的键不存在于树中。

对于红黑树，我们实现了搜索的迭代变体：

public Node searchNode(int key) {
  Node node = root;
  while (node != null) {
    if (key == node.data) {
      return node;
    } else if (key < node.data) {
      node = node.left;
    } else {
      node = node.right;
    }
  }

  return null;
}

这段代码应该是不言自明的。

5.2 红黑树插入

要插入新节点，我们从根向下搜索插入位置，并将新节点附加到叶子或半叶子上。

public void insertNode(int key) {
  Node node = root;
  Node parent = null;

  // Traverse the tree to the left or right depending on the key
  while (node != null) {
    parent = node;
    if (key < node.data) {
      node = node.left;
    } else if (key > node.data) {
      node = node.right;
    } else {
      throw new IllegalArgumentException("BST already contains a node with key " + key);
    }
  }

  // Insert new node
  Node newNode = new Node(key);
  newNode.color = RED;
  if (parent == null) {
    root = newNode;
  } else if (key < parent.data) {
    parent.left = newNode;
  } else {
    parent.right = newNode;
  }
  newNode.parent = parent;

  fixRedBlackPropertiesAfterInsert(newNode);
}

我们最初将新节点染成红色以满足规则 5，即插入后所有路径都有相同数量的黑色节点。

但是，如果插入节点的父节点也是红色的，则违反了规则 4。然后我们必须通过重新着色和/或旋转来修复树，以便再次满足所有规则。这是在方法中完成的fixRedBlackPropertiesAfterInsert()，该方法在方法的最后一行中调用insertNode()。

在修复过程中，我们要处理五种不同的情况：

• 情况 1：新节点是根
• 情况 2：父节点为红色，根节点
• 情况 3：父节点和叔叔节点都是红色
• 情况 4：父节点为红色，叔叔节点为黑色，插入节点为“内孙”
• 情况5：父节点为红色，叔叔节点为黑色，插入节点为“外孙”

以下分别介绍这五个案例。

5.2.1 情况 1：新节点是根

如果新节点是根节点，我们就不需要做任何其他事情了。除非我们遵循规则 2（“根节点始终为黑色”）。在这种情况下，我们必须将根节点涂成黑色。

5.2.2 情况 2：父节点为红色，根节点

在这种情况下，规则 4（“没有红红！”）被违反。我们现在要做的就是将根部涂成黑色。这导致规则 4 再次得到遵守。

那么规则 5 呢？由于此规则不计算根节点，因此所有路径仍有一个黑色节点（图中未显示 NIL 叶子节点）。如果我们计算根节点，那么所有路径现在将有两个黑色节点，而不是一个——这也是允许的。

如果我们按照规则 2（“根始终为黑色”），那么在情况 1 中我们已经将根染成黑色，情况 2 就不会再发生。

5.2.3 情况 3：父节点和叔叔节点为红色

我们使用术语“叔叔节点”来指代父节点的兄弟节点；即祖父节点中紧挨着父节点的第二个子节点。下图应该可以理解这一点：插入的是 81；其父节点是 75，祖父节点是 19，叔叔节点是 18。

父节点和叔节点都是红色的。在这种情况下，我们执行以下操作：

我们将父节点和叔节点（示例中的 18 和 75）重新着色为黑色，将祖节点（19）重新着色为红色。因此，插入节点再次满足规则 4（“无红红！”）。每条路径的黑色节点数不变（示例中仍为 2）。

但是，现在祖父母节点可能有两个连续的红色节点——即，如果曾祖父母节点（示例中为 17）也是红色的。在这种情况下，我们必须进行进一步修复。我们将通过在祖父母节点上递归调用修复函数来执行此操作。

5.2.4 情况 4：父节点为红色，叔叔节点为黑色，插入节点为“内孙”

我必须首先解释一下这种情况：“内孙”意味着从祖父母节点到插入节点的路径形成一个三角形，如下图使用 19、75 和 24 所示。在这个例子中，你可以看到 NIL 叶子也被认为是黑色叔叔（根据规则 3）。

（为了清楚起见，我没有画出 9 和 24 的两片 NIL 叶，以及 75 的右 NIL 叶。）

在这种情况下，我们首先在父节点处按照插入节点的相反方向进行旋转。

这意味着什么？

如果插入的节点是其父节点的左子节点，则在父节点处向右旋转。如果插入的节点是右子节点，则向左旋转。

在示例中，插入的节点（24）是左子节点，因此我们在父节点（示例中为 75）处向右旋转：

其次，我们在祖父节点处按 与上一次旋转相反的方向进行旋转 。在示例中，我们围绕 19 向左旋转：

最后，我们将刚插入的节点（示例中的 24）涂成黑色，将原始祖父节点（示例中的 19）涂成红色：

由于现在最后一个旋转子树的顶部有一个黑色节点，因此该位置不能违反规则 4（“没有红红！”）。

此外，将原始祖父母 (19) 重新着色为红色并不违反规则 4。它的左孩子是叔叔，根据本例的定义，它是黑色的。而右孩子，作为第二次旋转的结果，是插入节点的左孩子，因此是黑色的 NIL 叶子。

此外，将原始祖父母 (19) 重新着色为红色并不违反规则 4。它的左孩子是叔叔，根据本例的定义，它是黑色的。而右孩子，作为第二次旋转的结果，是插入节点的左孩子，因此是黑色的 NIL 叶子。

插入的红色 75 有两个 NIL 叶子作为子节点，因此这里也不违反规则 4。

修复现已完成；不需要递归调用修复函数。

5.2.5 情况5：父节点为红色，叔叔节点为黑色，插入节点为“外孙”

“外孙”是指从祖父节点到插入节点的路径形成一条线，如下例中的 19、75 和 81：

在这种情况下，我们在祖父节点（示例中为 19）处按与父节点和插入节点相反的方向旋转（毕竟，在这种情况下，两者都朝同一方向旋转）。在示例中，父节点和插入节点都是右子节点，因此我们在祖父节点处向左旋转：

然后，我们将前父级（示例中为 75）重新着色为黑色，将前祖级（19）重新着色为红色：

如同在案例 4 的结尾一样，我们在旋转的顶部有一个黑色节点，因此那里不会违反规则 4（“没有红红！”）。

19 的左子节点是旋转后的原始叔叔节点，因此根据案例定义，它是黑色的。19 的右子节点是父节点 (75) 的原始左子节点，它也必须是黑色的 NIL 叶子节点；否则，我们插入 81 的右侧位置就不会是空闲的（因为红色节点总是有两个具有值的黑色子节点或两个黑色的 NIL 子节点）。

红色的 81 是插入节点，因此也有两个黑色的 NIL 叶子。

至此，我们就完成了红黑树的修复。

如果您仔细观察，就会发现案例 5 恰好对应于案例 4 的第二次旋转。在代码中，这将通过以下事实来显示：对于案例 4，仅实现了第一次旋转，然后程序跳转到案例 5 的代码。

5.2.6 插入后修复方法的实施

案例 4 和 5 分为 4a/4b 和 5a/5b，具体取决于父节点是祖父节点的左子节点（4a/5a）还是右子节点（4b/5b）。

private void fixRedBlackPropertiesAfterInsert(Node node) {
  Node parent = node.parent;

  // Case 1: Parent is null, we've reached the root, the end of the recursion
  if (parent == null) {
    // Uncomment the following line if you want to enforce black roots (rule 2):
    // node.color = BLACK;
    return;
  }

  // Parent is black --> nothing to do
  if (parent.color == BLACK) {
    return;
  }

  // From here on, parent is red
  Node grandparent = parent.parent;

  // Case 2:
  // Not having a grandparent means that parent is the root. If we enforce black roots
  // (rule 2), grandparent will never be null, and the following if-then block can be
  // removed.
  if (grandparent == null) {
    // As this method is only called on red nodes (either on newly inserted ones - or -
    // recursively on red grandparents), all we have to do is to recolor the root black.
    parent.color = BLACK;
    return;
  }

  // Get the uncle (may be null/nil, in which case its color is BLACK)
  Node uncle = getUncle(parent);

  // Case 3: Uncle is red -> recolor parent, grandparent and uncle
  if (uncle != null && uncle.color == RED) {
    parent.color = BLACK;
    grandparent.color = RED;
    uncle.color = BLACK;

    // Call recursively for grandparent, which is now red.
    // It might be root or have a red parent, in which case we need to fix more...
    fixRedBlackPropertiesAfterInsert(grandparent);
  }

  // Parent is left child of grandparent
  else if (parent == grandparent.left) {
    // Case 4a: Uncle is black and node is left->right "inner child" of its grandparent
    if (node == parent.right) {
      rotateLeft(parent);

      // Let "parent" point to the new root node of the rotated sub-tree.
      // It will be recolored in the next step, which we're going to fall-through to.
      parent = node;
    }

    // Case 5a: Uncle is black and node is left->left "outer child" of its grandparent
    rotateRight(grandparent);

    // Recolor original parent and grandparent
    parent.color = BLACK;
    grandparent.color = RED;
  }

  // Parent is right child of grandparent
  else {
    // Case 4b: Uncle is black and node is right->left "inner child" of its grandparent
    if (node == parent.left) {
      rotateRight(parent);

      // Let "parent" point to the new root node of the rotated sub-tree.
      // It will be recolored in the next step, which we're going to fall-through to.
      parent = node;
    }

    // Case 5b: Uncle is black and node is right->right "outer child" of its grandparent
    rotateLeft(grandparent);

    // Recolor original parent and grandparent
    parent.color = BLACK;
    grandparent.color = RED;
  }
}

getUncle()辅助函数：

private Node getUncle(Node parent) {
  Node grandparent = parent.parent;
  if (grandparent.left == parent) {
    return grandparent.right;
  } else if (grandparent.right == parent) {
    return grandparent.left;
  } else {
    throw new IllegalStateException("Parent is not a child of its grandparent");
  }
}

5.2.7 实施说明

与 AVL 树不同，我们无法轻松地将红黑树的修复函数挂接到现有的递归中BinarySearchTreeRecursive。这是因为我们不仅需要在插入新节点的节点处进行旋转，而且还需要在必要时在祖父节点处进行旋转（情况 3 和 4）。

您会在文献中找到许多替代实现。由于它们结合了多个步骤，因此有时它们的性能略高于此处介绍的方法。这不会改变性能的数量级，但可以提高几个百分点。对我来说，以易于理解的方式实现算法很重要。性能更高的算法也总是更复杂。

我通过两个步骤实现了迭代插入——先搜索，然后插入——与 不同BinarySearchTreeIterative，我将两者结合在一起。这使得阅读代码更容易一些，但需要额外的“ if (key < parent.data)”检查来确定新节点是否需要作为其父节点下的左子节点或右子节点插入。

5.3 红黑树删除

如果你刚刚读完插入章节，你可能想休息一会儿。毕竟删除更复杂。

首先，我们按照有关二叉搜索树的文章中的“二叉搜索树删除”部分所述进行操作。

以下是摘要：

1. 如果要删除的节点没有子节点，我们只需将其删除。
2. 如果要删除的节点有一个子节点，我们将删除该节点并让其唯一的子节点移动到其位置。
3. 如果要删除的节点有两个子节点，我们将右子节点的按序后继的内容（而不是颜色！）复制到要删除的节点中，然后根据规则 1 或 2 删除按序后继（根据定义，按序后继最多有一个子节点）。

之后，我们需要检查树的规则，并在必要时进行修复。为此，我们需要记住已删除节点的颜色以及我们已上移的节点。

• 如果删除的节点是红色的，我们就不能违反任何规则：它既不能导致两个连续的红色节点（规则 4），也不会改变任何路径上的黑色节点的数量（规则 5）。
• 然而，如果被删除的节点是黑色的，我们肯定会违反规则 5（除非树只包含黑色根），并且规则 4 也可能被违反 - 即如果被删除节点的父节点和上移的子节点都是红色的。

首先，这是实际删除节点的代码（类 RedBlackTree，第 163 行）。在代码下方，将解释其各个部分：

public void deleteNode(int key) {
  Node node = root;

  // Find the node to be deleted
  while (node != null && node.data != key) {
    // Traverse the tree to the left or right depending on the key
    if (key < node.data) {
      node = node.left;
    } else {
      node = node.right;
    }
  }

  // Node not found?
  if (node == null) {
    return;
  }

  // At this point, "node" is the node to be deleted

  // In this variable, we'll store the node at which we're going to start to fix the R-B
  // properties after deleting a node.
  Node movedUpNode;
  boolean deletedNodeColor;

  // Node has zero or one child
  if (node.left == null || node.right == null) {
    movedUpNode = deleteNodeWithZeroOrOneChild(node);
    deletedNodeColor = node.color;
  }

  // Node has two children
  else {
    // Find minimum node of right subtree ("inorder successor" of current node)
    Node inOrderSuccessor = findMinimum(node.right);

    // Copy inorder successor's data to current node (keep its color!)
    node.data = inOrderSuccessor.data;

    // Delete inorder successor just as we would delete a node with 0 or 1 child
    movedUpNode = deleteNodeWithZeroOrOneChild(inOrderSuccessor);
    deletedNodeColor = inOrderSuccessor.color;
  }

  if (deletedNodeColor == BLACK) {
    fixRedBlackPropertiesAfterDelete(movedUpNode);

    // Remove the temporary NIL node
    if (movedUpNode.getClass() == NilNode.class) {
      replaceParentsChild(movedUpNode.parent, movedUpNode, null);
    }
  }
}

代码的第一行搜索要删除的节点；如果找不到该节点，该方法将终止。

如何进行取决于要删除的子节点的数量。

5.3.1 删除具有零个或一个子节点的节点

如果被删除的节点最多只有一个子节点，我们将调用该方法deleteNodeWithZeroOrOneChild()。

private Node deleteNodeWithZeroOrOneChild(Node node) {
  // Node has ONLY a left child --> replace by its left child
  if (node.left != null) {
    replaceParentsChild(node.parent, node, node.left);
    return node.left; // moved-up node
  }

  // Node has ONLY a right child --> replace by its right child
  else if (node.right != null) {
    replaceParentsChild(node.parent, node, node.right);
    return node.right; // moved-up node
  }

  // Node has no children -->
  // * node is red --> just remove it
  // * node is black --> replace it by a temporary NIL node (needed to fix the R-B rules)
  else {
    Node newChild = node.color == BLACK ? new NilNode() : null;
    replaceParentsChild(node.parent, node, newChild);
    return newChild;
  }
}

我已经向你介绍了replaceParentsChild()旋转中的方法（这里多次提到）。

删除的节点为黑色且没有子节点的情况是特殊情况。这将在最后一个else块中处理：

我们已经看到，删除一个黑色节点会导致所有路径上的黑色节点数量不再相同。也就是说，我们必须修复树。树修复总是从上移的节点开始（正如您稍后将看到的那样）。

如果删除的节点没有子节点，则其中一个 NIL 叶子节点实际上会向上移动到其位置。为了稍后能够从这个 NIL 叶子节点导航到其父节点，我们需要一个特殊的占位符。我在类中实现了一个占位符NilNode：

private static class NilNode extends Node {
  private NilNode() {
    super(0);
    this.color = BLACK;
  }
}

最后，该方法返回调用方法存储在变量中的deleteNodeWithZeroOrOneChild()上移节点。deleteNode()movedUpNode
删除具有两个子节点的节点
如果要删除的节点有两个子节点，我们首先使用方法findMinimum()找到从右子节点开始的子树的按顺序后继节点：

private Node findMinimum(Node node) {
  while (node.left != null) {
    node = node.left;
  }
  return node;
}

然后，我们将中序后继的数据复制到要删除的节点中，并调用deleteNodeWithZeroOrOneChild()上面介绍的方法从树中删除中序后继。再次记住 中的上移节点movedUpNode。

5.3.2 修复树

以下再次是if该方法的最后一个块deleteNode()：

if (deletedNodeColor == BLACK) {
  fixRedBlackPropertiesAfterDelete(movedUpNode);

  // Remove the temporary NIL node
  if (movedUpNode.getClass() == NilNode.class) {
    replaceParentsChild(movedUpNode.parent, movedUpNode, null);
  }
}

如上所述，删除红色节点并不违反任何规则。但是，如果删除的节点是黑色的，我们调用修复方法fixRedBlackPropertiesAfterDelete()。

如果有的话，我们只需要在调用修复函数时NilNode创建临时占位符。因此我们可以在之后将其删除。deleteNodeWithZeroOrOneChild()

删除时，我们需要考虑比插入时多一种情况。与插入不同，此处与叔叔节点的颜色无关，而是与被删除节点的兄弟节点的颜色有关。

• 情况 1：删除的节点是根节点
• 情况 2：兄弟元素为红色
• 案例 3：兄弟姐妹是黑人，有两个黑人孩子，父母是红人
• 案例 4：兄弟姐妹是黑人，有两个黑人孩子，父母也是黑人
• 案例 5：兄弟姐妹是黑色的，并且至少有一个红色的孩子，“外侄子”是黑色的
• 案例 6：兄弟姐妹是黑色的，并且至少有一个红色的孩子，“外侄子”是红色的

以下各节详细描述了这六个案例：

5.3.3 场景 1：删除节点是根

如果我们移除根节点，另一个节点将移至其位置。这只有在根节点没有子节点或只有一个子节点时才会发生。如果根节点有两个子节点，那么最终被移除的将是有序后继节点，而不是根节点。

如果根节点没有子节点，则新根节点为黑色 NIL 节点。因此树为空且有效：

如果根有一个子节点，那么这个子节点必须是红色的，并且没有其他子节点。

解释：如果红色子节点还有另一个红色子节点，则规则 4（“没有红色-红色！”）将被违反。如果红色子节点有一个黑色子节点，则通过红色节点的路径将比根的 NIL 子树至少多一个黑色节点，因此规则 5 将被违反。

因此，该树仅由一个红根组成，因此也是有效的。

如果我们按照规则 2（“根始终为黑色”），我们现在将重新着色根。

5.3.4 场景 2：兄弟节点为红色

对于所有其他情况，我们首先检查兄弟节点的颜色。即被删除节点的父节点的第二个子节点。在下面的例子中，我们删除了 9；它的兄弟节点是红色的 19：

在这种情况下，我们首先将兄弟部分涂成黑色，将父部分涂成红色：

 

这显然违反了规则 5：父节点右子树中的路径比左子树中的路径多两个黑色节点。我们通过围绕父节点沿被删除节点的方向旋转来解决这个问题。

在示例中，我们删除了父节点的左节点 - 因此，我们执行左旋转：

现在我们在右边的路径上有两个黑色节点，在通往 18 的路径上也有两个黑色节点。但是，在通往 17 的左侧 NIL 叶子的路径上只有一个黑色节点（记住：根不算数，NIL 节点才算数 —— 即使是图中未画出的节点）。

我们查看已删除节点的新兄弟节点（示例中为 18）。该新兄弟节点现在肯定是黑色的，因为它是本例开头红色兄弟节点的原始子节点。

此外，新的兄弟节点有黑色子节点。因此，我们将兄弟节点（18）涂成红色，将父节点（17）涂成黑色：

步骤 3：重新着色父母和新的兄弟姐妹

现在所有路径都有两个黑色节点；我们再次拥有一棵有效的红黑树。

事实上，在这最后一步我已经预料到了一些事情。也就是说，我们执行了案例 3​​ 的规则（这就是为什么图片字幕在括号中）。

在案例 2 的最后一步，我们总是有一个黑人兄弟姐妹。黑人兄弟姐妹有两个黑人孩子，这是案例 3 的要求，但这纯属巧合。事实上，在案例 2 结束时，案例 3 至案例 6 中的任何一种情况都可能发生，必须根据以下部分进行处理。

5.3.5 场景 3：兄弟姐妹是黑人，有两个黑人孩子，父母是红人

在下面的例子中，我们删除 75 并让它的一个黑色 NIL 叶子向上移动。

（再次提醒：我只在与理解相关时才在图形中显示 NIL 节点。）

案例 3：黑人兄弟姐妹与黑人孩子和红色父母

删除违反了规则 5：在最右边的路径上，现在比所有其他路径上少一个黑色节点。

兄弟节点（示例中的 18）是黑色的，有两个黑色子节点（NIL 叶子未显示）。父节点（19）是红色的。在这种情况下，我们按如下方式修复树：

我们将兄弟节点（18）重新着色为红色，将父节点（19）重新着色为黑色：

这样，我们又得到了一棵有效的红黑树。所有路径上的黑色节点数相同（符合规则 5 的要求）。而且由于兄弟节点只有黑色子节点，因此将其染成红色不会违反规则 4（“不红红！”）。

5.3.6 场景 4：兄弟姐妹是黑人，有两个黑人孩子，父母也是黑人

在以下示例中，我们删除 18：

这导致（就像情况 3 一样）违反规则 5：在指向已删除节点的路径上，现在比所有其他路径上少一个黑色节点。

与情况 3 相反，在这种情况下，已删除节点的父节点为黑色。我们首先将兄弟节点涂成红色：

这意味着从父节点开始的子树的黑色高度再次是均匀的（2）。然而，在左子树中，它高出一个（3）。因此仍然违反了规则 5。

—— 递归

我们通过假装删除节点 17 和 19 之间的一个黑色节点（效果相同）来解决这个问题。因此，我们在父节点（即 19（在本例中是向上移动的节点）上递归调用修复函数。

19 有一个黑人兄弟姐妹（9），还有两个黑人孩子（3 和 12）和一个红衣父母（17）。因此，我们现在回到案例 3。

我们通过将父节点涂成黑色、将兄弟节点涂成红色来解决情况 3：

步骤 2：重新着色父母和兄弟姐妹

现在所有路径上的黑色高度都是 2，所以我们的红黑树再次有效。

5.3.7 场景 5：兄弟姐妹是黑色的，并且至少有一个红色的孩子，“外侄子”是黑色的

在此示例中，我们删除 18：

结果，我们再次违反了规则 5，因为从兄弟节点开始的子树现在的黑色高度大了一。

我们检查已删除节点的“外侄子”。“外侄子”是指已删除节点对面的兄弟节点的子节点。在本例中，这是 75 下的右侧（按定义是黑色的）NIL 叶子节点。

在下图中，您可以看到父母、兄弟姐妹和侄子一起形成一条线（示例中为：19、75 和其右边的 NIL 孩子）。

我们通过将内侄子（示例中的 24）涂成黑色并将兄弟（75）涂成红色来开始修复：

然后我们在兄弟节点处按被删除节点的反方向执行旋转。在示例中，我们删除了父节点的 左 孩子，因此我们  在兄弟节点（75）处执行右旋转：

我们再次进行重新着色：

• 我们将兄弟节点重新着色为其父节点的颜色（本例中为 24 红色）。
• 然后我们将已删除节点的父节点（19）和外侄子节点（即新兄弟节点（示例中的 75）的右孩子）重新着色为黑色：

最后，我们对父节点进行一次向被删除节点方向的旋转。在示例中，被删除的节点是左子节点，因此我们相应地进行一次左旋转（示例中的 19 处）：

第4步：围绕父节点旋转

最后一步恢复了所有红黑规则。没有两个连续的红色节点，并且所有路径上的黑色节点数量均匀为两个。这样我们就完成了树的修复。

5.3.8 场景 6：兄弟姐妹是黑色的，并且至少有一个红色的孩子，“外侄子”是红色的

在最后一个例子中，与案例 5 非常相似，我们也删除了 18：

黑色兄弟姐妹至少有一个红色孩子和一个红色“外侄子”

结果，与情况 5 一样，我们违反了规则 5，因为到已删除节点的路径现在少了一个黑节点。

在案例 6 中，与案例 5 不同，外部侄子（示例中为 81）是红色而不是黑色。

我们首先将兄弟节点重新着色为父节点的颜色（示例中为 75 红色）。然后我们将父节点（示例中为 19）和外层侄子节点（81）重新着色为黑色：

其次，我们在父节点处按照被删除节点的方向执行旋转。在示例中，我们删除了一个 左 孩子；因此，我们围绕 19执行左旋转：

步骤 2：围绕父节点旋转

这种旋转恢复了红黑规则。没有两个红色节点互相跟随，并且所有路径上的黑色节点数量相同（即 2）。

最后一种情况的规则与情况 5 的最后两步类似。在源代码中，你会看到，对于情况 5，只实现了它的前两步，然后程序转到情况 6 来执行最后两步。

至此，我们已经研究了所有六种情况。让我们继续讨论 Java 中修复函数的实现。

5.3.9 删除后修复方法的实现

该fixRedBlackPropertiesAfterDelete()方法。见注释标记了Case 1 至 6。

private void fixRedBlackPropertiesAfterDelete(Node node) {
  // Case 1: Examined node is root, end of recursion
  if (node == root) {
    // Uncomment the following line if you want to enforce black roots (rule 2):
    // node.color = BLACK;
    return;
  }

  Node sibling = getSibling(node);

  // Case 2: Red sibling
  if (sibling.color == RED) {
    handleRedSibling(node, sibling);
    sibling = getSibling(node); // Get new sibling for fall-through to cases 3-6
  }

  // Cases 3+4: Black sibling with two black children
  if (isBlack(sibling.left) && isBlack(sibling.right)) {
    sibling.color = RED;

    // Case 3: Black sibling with two black children + red parent
    if (node.parent.color == RED) {
      node.parent.color = BLACK;
    }

    // Case 4: Black sibling with two black children + black parent
    else {
      fixRedBlackPropertiesAfterDelete(node.parent);
    }
  }

  // Case 5+6: Black sibling with at least one red child
  else {
    handleBlackSiblingWithAtLeastOneRedChild(node, sibling);
  }
}

上面代码调用的辅助方法getSibling()，isBlack():

private Node getSibling(Node node) {
  Node parent = node.parent;
  if (node == parent.left) {
    return parent.right;
  } else if (node == parent.right) {
    return parent.left;
  } else {
    throw new IllegalStateException("Parent is not a child of its grandparent");
  }
}

private boolean isBlack(Node node) {
  return node == null || node.color == BLACK;
}

handleRedSibling（场景 2）：

private void handleRedSibling(Node node, Node sibling) {
  // Recolor...
  sibling.color = BLACK;
  node.parent.color = RED;

  // ... and rotate
  if (node == node.parent.left) {
    rotateLeft(node.parent);
  } else {
    rotateRight(node.parent);
  }
}

handleBlackSiblingWithAtLeastOneRedChild方法（场景 5 和 6）的实现：

private void handleBlackSiblingWithAtLeastOneRedChild(Node node, Node sibling) {
  boolean nodeIsLeftChild = node == node.parent.left;

  // Case 5: Black sibling with at least one red child + "outer nephew" is black
  // --> Recolor sibling and its child, and rotate around sibling
  if (nodeIsLeftChild && isBlack(sibling.right)) {
    sibling.left.color = BLACK;
    sibling.color = RED;
    rotateRight(sibling);
    sibling = node.parent.right;
  } else if (!nodeIsLeftChild && isBlack(sibling.left)) {
    sibling.right.color = BLACK;
    sibling.color = RED;
    rotateLeft(sibling);
    sibling = node.parent.left;
  }

  // Fall-through to case 6...

  // Case 6: Black sibling with at least one red child + "outer nephew" is red
  // --> Recolor sibling + parent + sibling's child, and rotate around parent
  sibling.color = node.parent.color;
  node.parent.color = BLACK;
  if (nodeIsLeftChild) {
    sibling.right.color = BLACK;
    rotateLeft(node.parent);
  } else {
    sibling.left.color = BLACK;
    rotateRight(node.parent);
  }
}

就像插入一样，您会在文献中找到许多用于删除的替代方法。我已尝试构造代码，以便您尽可能地遵循代码流程。

5.4 遍历红黑树

和任何二叉树一样，我们可以按前序、后序、中序、逆序和水平顺序遍历红黑树。在二叉树入门文章的“二叉树遍历”部分，我已经详细描述了遍历。

在该部分中，您还将找到在类DepthFirstTraversal、 DepthFirstTraversalIterative和 中实现的相应 Java 源代码DepthFirstTraversalRecursive。

遍历方法在BinaryTree接口上起作用。由于RedBlackTree也实现了此接口，因此我们也可以轻松地将遍历方法应用于它。

6. 红黑树时间复杂度

我们可以按如下方式确定二叉树中搜索、插入和删除节点的时间开销成本：

6.1 搜索时间

我们沿着从根到搜索节点（或到 NIL 叶）的路径。在每一层，我们都进行比较。比较的工作量是恒定的。

因此，搜索成本与树的高度成正比。

我们用n表示树节点的数量。在“红黑树的高度”一节中，我们已经认识到最长路径最多是最短路径的两倍。因此，树的高度以O(log n)为界。

因此，在红黑树中查找节点的时间复杂度为：O（log n）

6.2 插入时间

插入时，我们首先进行搜索。我们刚刚确定搜索成本为O(log n)。

接下来，我们插入一个节点。无论树的大小如何，此操作的成本都是恒定的，因此为O(1)。

然后我们检查红黑规则，并在必要时恢复它们。我们从插入的节点开始，一直到根节点。在每个级别，我们执行以下一个或多个操作：

• 检查父节点的颜色
• 确定叔叔节点并检查其颜色
• 重新着色一个至三个节点
• 进行一到两次旋转

这些操作中的每一个本身都是常数时间，O(1)。因此，检查和修复树的总时间也与其高度成正比。

所以插入红黑树的时间复杂度也是：O(log n)

6.3 删除时间

与插入一样，我们首先在O(log n)时间内搜索要删除的节点。

此外，删除成本与树的大小无关，因此它是常数O(1)。

为了检查规则和修复树，会发生以下一个或多个操作 - 每个级别最多一次：

• 检查已删除节点的颜色
• 确定兄弟姐妹并检查其颜色
• 检查兄弟姐妹孩子的颜色
• 重新着色父节点
• 重新着色兄弟节点及其子节点之一
• 进行一到两次旋转

这些操作本身也都具有常数复杂度。因此，删除节点后检查和恢复规则的总工作量也与树的高度成正比。

所以从红黑树中删除的时间复杂度也是：O（log n）

7. 红黑树与其他数据结构的比较

以下各节描述了红黑树与其他数据结构相比的区别和优缺点。

7.1 红黑树与 AVL 树

红黑树和AVL 树都是自平衡二叉搜索树。
在红黑树中，到根的最长路径最多是到根的最短路径的两倍。另一方面，在 AVL 树中，任何两棵子树的深度之差都不会超过 1。
在红黑树中，平衡由节点颜色、一组规则以及旋转和重新着色节点来维持。在 AVL 树中，会比较子树的高度，并在必要时执行旋转。
两类树的特性上的差异导致了性能和内存要求上的以下差异：

两类树的特性上的差异导致了性能和内存要求上的以下差异：

• 由于 AVL 树的平衡性更均匀，因此 AVL 树中的搜索通常更快。但就量级而言，两者都在O(log n)范围内。
• 对于插入和删除，两棵树的时间复杂度都是O(log n)。然而，直接比较一下，红黑树更快，因为它重新平衡的频率较低。
• 两种树都需要额外的内存：AVL 树每个节点占用一个字节，用于存储从某个节点开始的子树的高度；红黑树每个节点占用一个比特，用于存储颜色信息。这在实践中几乎没有什么区别，因为一个比特通常至少占用一个字节。

如果您预计插入/删除操作较多，则应使用红黑树。另一方面，如果您预计搜索操作较多，则应选择 AVL 树。

7.2 红黑树与二叉搜索树

红黑树是自平衡二叉搜索树的具体实现。因此，每个红黑树也是一棵二叉搜索树。

还有其他类型的二叉搜索树，例如上面提到的 AVL 树，或者简单的非平衡实现。因此，并非每个二叉搜索树都是红黑树。

8. 总结

本文详细阐述了什么是红黑树，哪些规则控制它以及如何在插入和删除节点后评估和恢复这些规则，还详细介绍了一种尽可能易于理解的 Java 实现。

JDK 在TreeMap中使用红黑树（这里是GitHub 上的源代码），在HashMap中的桶碰撞中使用红黑树（这里是源代码）。