简介

红黑树（Red–black tree）是一种自平衡二叉查找树，典型的用途是实现关联数组（Associative Array，又称映射Map、字典Dictionary）。它在1972年由鲁道夫·贝尔发明，被称为”对称二叉B树“。红黑树的结构复杂，但它的操作有着良好的最坏情况运行时间：它可以在O(log n)时间内完成查找，插入和删除，这里的n是树中元素的数目。

红黑树是2-3-4树（也称4 阶B树，B树概括来说是一个一般化的二叉查找树BST，4阶指其每个节点最多包含 3 个元素和 4 个儿子）的一种等同。换句话说，对于每个2-3-4树，都存在至少一个数据元素是同样次序的红黑树。在2-3-4树上的插入和删除操作也等同于在红黑树中颜色翻转和旋转。这使得2-3-4树成为理解红黑树背后的逻辑的重要工具，这也是很多介绍算法的教科书在红黑树之前介绍2-3-4树的原因，尽管2-3-4树在实践中不经常使用。

The same red–black tree as in the example above, seen as a B-tree.

红黑树相对于AVL树（最早被发明的自平衡二叉查找树）来说，牺牲了部分平衡性以换取插入/删除操作时少量的旋转操作，整体来说性能要优于AVL树。

性质

红黑树是每个节点都带有颜色属性的二叉查找树。在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求：

节点是红色或黑色
根是黑色
所有叶子都是黑色（叶子是NIL节点）
每个红色节点必须有两个黑色的子节点（从每个叶子到根的所有路径上不能有两个连续的红色节点）
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点

这些约束确保了红黑树的关键特性：

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长

注意到性质4导致了路径不能有两个毗连的红色节点就足够了。最短的可能路径都是黑色节点，最长的可能路径有交替的红色和黑色节点。因为根据性质5所有最长的路径都有相同数目的黑色节点，这就表明了没有路径能多于任何其他路径的两倍长。

操作

因为每一个红黑树也是一个特化的二叉查找树，因此红黑树上的只读操作与普通二叉查找树上的只读操作相同。然而，在红黑树上进行插入操作和删除操作会导致不再符合红黑树的性质。恢复红黑树的性质需要少量O(log n)的颜色变更（实际是非常快速的）和不超过三次树旋转（对于插入操作是两次）。

使用示例C ++代码演示插入和删除操作的详细信息。示例代码可以调用下面的函数来查找父节点(parent)，兄弟节点(sibling)，叔父节点(uncle )和祖父节点(grandparent)，以及左旋和右旋：

// Basic type defintions:

enum color_t { BLACK, RED };

struct Node {
  Node* parent;
  Node* left;
  Node* right;
  enum color_t color;
  int key;
};

// Helper functions:

Node* GetParent(Node* n) {
  // Note that parent is set to null for the root node.
  return n->parent;
}

Node* GetGrandParent(Node* n) {
  Node* p = GetParent(n);

  // No parent means no grandparent.
  if (p == nullptr) {
    return nullptr;
  }

  // Note: Will be nullptr if parent is root.
  return GetParent(p);
}

Node* GetSibling(Node* n) {
  Node* p = GetParent(n);

  // No parent means no sibling.
  if (p == nullptr) {
    return nullptr;
  }

  if (n == p->left) {
    return p->right;
  } else {
    return p->left;
  }
}

Node* GetUncle(Node* n) {
  Node* p = GetParent(n);
  Node* g = GetGrandParent(n);

  // No grandparent means no uncle
  if (g == nullptr) {
    return nullptr;
  }

  return GetSibling(p);
}

void RotateLeft(Node* n) {
  Node* nnew = n->right;
  Node* p = GetParent(n);
  assert(nnew != nullptr);  // Since the leaves of a red-black tree are empty,
                            // they cannot become internal nodes.
  n->right = nnew->left;
  nnew->left = n;
  n->parent = nnew;
  // Handle other child/parent pointers.
  if (n->right != nullptr) {
    n->right->parent = n;
  }

  // Initially n could be the root.
  if (p != nullptr) {
    if (n == p->left) {
      p->left = nnew;
    } else if (n == p->right) {
      p->right = nnew;
    }
  }
  nnew->parent = p;
}

void RotateRight(Node* n) {
  Node* nnew = n->left;
  Node* p = GetParent(n);
  assert(nnew != nullptr);  // Since the leaves of a red-black tree are empty,
                            // they cannot become internal nodes.

  n->left = nnew->right;
  nnew->right = n;
  n->parent = nnew;

  // Handle other child/parent pointers.
  if (n->left != nullptr) {
    n->left->parent = n;
  }

  // Initially n could be the root.
  if (p != nullptr) {
    if (n == p->left) {
      p->left = nnew;
    } else if (n == p->right) {
      p->right = nnew;
    }
  }
  nnew->parent = p;
}

图表说明

标签N表示每种情况下的当前节点。起初，它是插入节点或替换节点和叶子节点，但整个过程也可以递归地应用于其他节点（见情形3）。
P表示N的父亲，G表示N的祖父，S表示N的兄弟，U表示N的叔父（即父节点的兄弟，如人类家族树）。
在某些情况下，节点的角色和标签会发生偏移，但在每种情况下，每个标签始终表示相同的节点。
在图中，左边环绕当前节点N有一圈蓝色，右边目标节点N也有一圈蓝色。下一步中，将相对于它重新分配其他节点。
图中所示的红色或黑色要么是假设的，要么是由这些假设所暗示的。白色表示红色或黑色，但在左右图中是一致的。
一个编号的三角形表示一个深度未指定的子树。三角形上的黑色圆圈表示子树的黑高度比没有这个圆圈的子树大1。

插入

首先以非常类似于标准二叉搜索树插入的方式添加节点并标记它为红色（如果设为黑色，会导致根到叶子的某条路径上多一个额外的黑节点，很难调整。而设为红色节点后，虽然可能会出现两个连续红色节点，却可以通过颜色调换和树旋转来调整）。最大的区别是，在二叉搜索树中，一个新节点作为叶子添加，而叶子在红黑树中不包含任何信息，因此新节点替换了一个现有的叶子，然后添加了两个自己的黑叶子。

Node* Insert(Node* root, Node* n) {
  // Insert new Node into the current tree.
  InsertRecurse(root, n);

  // Repair the tree in case any of the red-black properties have been violated.
  InsertRepairTree(n);

  // Find the new root to return.
  root = n;
  while (GetParent(root) != nullptr) {
    root = GetParent(root);
  }
  return root;
}

void InsertRecurse(Node* root, Node* n) {
  // Recursively descend the tree until a leaf is found.
  if (root != nullptr && n->key < root->key) {
    if (root->left != nullptr) {
      InsertRecurse(root->left, n);
      return;
    } else {
      root->left = n;
    }
  } else if (root != nullptr) {
    if (root->right != nullptr) {
      InsertRecurse(root->right, n);
      return;
    } else {
      root->right = n;
    }
  }

  // Insert new Node n.
  n->parent = root;
  n->left = nullptr;
  n->right = nullptr;
  n->color = RED;
}

下面要进行什么操作取决于其他临近节点的颜色。有几种插入情况：

N是根节点，即红黑树的第一个节点
N的父亲（P）是黑
P是红色的（所以它不能是树的根）而N的叔叔（U）是红色的
P为红色，U为黑色

void InsertRepairTree(Node* n) {
  if (GetParent(n) == nullptr) {
    InsertCase1(n);
  } else if (GetParent(n)->color == BLACK) {
    InsertCase2(n);
  } else if (GetUncle(n) != nullptr && GetUncle(n)->color == RED) {
    InsertCase3(n);
  } else {
    InsertCase4(n);
  }
}

注意：

性质1（每个节点为红或黑）和性质3（所有叶子都是黑）总是保持着
性质2（根节点为黑）使用性质1检查并更正
性质4（红色节点只有黑色子节点）只在增加红色节点、重绘黑色节点为红色，或做旋转时受到威胁
性质5（路径黑节点相同）只在增加黑色节点、重绘红色节点为黑色，或做旋转时受到威胁

情形1：新节点N位于树的根上

在这种情形下，我们把它重绘为黑色以满足性质2（根为黑）。因为它在每个路径上对黑节点数目增加一，性质5（路径黑相同）符合。

void InsertCase1(Node* n) {
  if (GetParent(n) == nullptr) {
    n->color = BLACK;
  }
}

情形2：新节点的父节点P是黑色

在这种情形下，性质4（一红生两黑）没有失效，树仍是有效的。性质5（路径黑相同）也未受到威胁，尽管新节点N有两个黑色叶子子节点，但由于新节点N是红色，通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点，所以依然满足这个性质。

void InsertCase2(Node* n) {
  // Do nothing since tree is still valid.
  return;
}

注：在下列情形下，可以假设N具有祖父节点G，因为其父P是红色，如果它是根，则它将是黑色。因此，N也具有叔叔节点U，尽管它可以是情形4中的叶子。

情形3：父节点P和叔父节点U都是红色

P和U都可以变为黑色同时祖父节点G变为红色，以保正性质5（路径黑相同），因为通过父节点或叔父节点的路径必然通过祖父节点，所以这些路径上的黑色节点的数量没有改变。但是，如果祖父节点G是根则违反属性2（根是黑色），如果它有红色的父节点则违反属性4（一红生两黑），为了解决此问题，需在G上递归地运行树的红黑修复程序。

注意，这是一个尾递归调用，因此可以将其重写为循环。因为这是唯一的循环，而且任何旋转都是在这个循环之后发生的，这证明了旋转的次数是恒定的。

void InsertCase3(Node* n) {
  GetParent(n)->color = BLACK;
  GetUncle(n)->color = BLACK;
  GetGrandParent(n)->color = RED;
  InsertRepairTree(GetGrandParent(n));
}

注：在其余情形，图中父节点P是其父节点的左子节点，不过P可能位于任一侧。代码示例已涵盖两种可能性。

情形4，步骤1：父节点P是红色而叔父节点U是黑色

最终目标是将当前节点旋转到祖父节点的位置，但如果当前节点位于G下子树的“内侧” （即N是G的左子节点的右孩子或是G的右子节点的左孩子）则无法直接调整实现。这时，在P处进行左旋可以交换当前节点N与父节点P的角色。旋转将导致一些之前没有经过N的路径（标记为“1”的子树中的路径）经过N，以及一些之前没有经过P的路径（标记为“3”的子树中的路径）经过P 。然而，由于这两个节点都是红色的，因此旋转没有影响性质5（路径黑相同）。完成此步骤后，性质4（一红生两黑）仍不满足，我们可以通过继续执行步骤2来解决此问题。

void InsertCase4(Node* n) {
  Node* p = GetParent(n);
  Node* g = GetGrandParent(n);

  if (n == p->right && p == g->left) {
    RotateLeft(p);
    n = n->left;
  } else if (n == p->left && p == g->right) {
    RotateRight(p);
    n = n->right;
  }

  InsertCase4Step2(n);
}

情形4，步骤2：节点N已在G下的子树的“外侧”

在这种情况下，在G上执行右旋，使得之前的父节点P成为当前节点N和之前祖父节点G的父亲。我们知道以前的祖父节点G是黑色，否则父节点P就不可能是红色（如果P和G都是红色就违反了性质4）。一旦是P和G的颜色切换后，生成的树满足性质4（一红生两黑）。性质5（路径黑相同）也满足，因为通过这三种节的所有路径之前都经过G，现在他们都通过P。

void InsertCase4Step2(Node* n) {
  Node* p = GetParent(n);
  Node* g = GetGrandParent(n);

  if (n == p->left) {
    RotateRight(g);
  } else {
    RotateLeft(g);
  }
  p->color = BLACK;
  g->color = RED;
}

注意，插入实际上是就地算法，因为上面的所有调用都使用尾递归。

在上面的算法中，所有情况只被调用一次，除了在情形3中的祖父节点可递归调用到情形1，这是唯一的迭代循环情况。因为修正问题每次每次被扩大两个级别，它需要最大h/2次迭代来修复树（其中h是树的高度）。由于向上调整的概率随着每次迭代呈指数级下降，平均插入成本实际上是恒定的。

删除

在常规的二叉搜索树中，当删除具有两个非叶子节点的节点时，我们找到其左子树中的最大元素（其为有序前导）或其右子树中的最小元素（其为有序后继）并移动它的值的被删除节点。然后删除复制值的节点，该节点必须有少于两个非叶节点的子节点。(这里指定非叶节点，而不是所有的子节点，因为与普通的二叉搜索树不同，红黑树可以在任何地方有叶节点，它们实际上是哨兵结点Nil，因此所有节点要么是内部节点，有两个子节点，要么是定义为零个子节点的叶节点。实际上，红黑树中有两个叶子子节点的内部节点就像常规二叉搜索树中的叶子节点。)

因为仅仅复制一个值并不违反任何红黑属性，所以这就减少了删除最多只有一个非叶子子节点的问题。一旦我们解决了这个问题，这个解决方案同样适用于我们最初想删除的节点最多有一个非叶子节点的情况，就像刚才考虑的它有两个非叶子节点的情况一样。

因此，在本讨论的其余部分中，我们将处理删除最多包含一个非叶子子节点的节点。我们使用标签M来表示要删除的节点; C将表示M的一个选定子元素，我们也称它为“它的子元素”。如果M确实有一个非叶节点的子节点，则将其称为子节点C ; 否则，选择任意一个叶子作为它的子节点C。

如果M是一个红色节点，我们只需用它的子节点C替换它，根据性质4它必须是黑色。（这只能在M有两个叶子元素时发生，因为如果红色节点M有一边有一个黑色非叶子元素而另一边只有一个叶子，那么两边的黑色节点的数量会不同，违反性质5）通过删除节点的所有路径将只通过一个较少的红色节点，并且删除节点的父节点和子节点都必须是黑色，因此性质3（所有叶子为黑）和性质4（一红生两黑）仍然保持。

另一个简单的例子是当M是黑色而C是红色时。简单地删除黑色节点可能会破坏性质4（一红生两黑）和性质5（路径黑相同），但是如果我们重新绘制C黑色，这两个性质都会保留下来。

复杂的情况是M和C都是黑色的。（这只有在删除具有两个叶子节点的黑色节点时才会发生，因为如果黑色节点M的一侧有一个黑色的非叶子节点而另一侧只有一个叶子节点，那么两侧的黑色节点的不同，即违反性质5。）我们首先将要删除的节点M替换为它的儿子C 。我们将重新标记这个孩子C（在新的位置）为N，它的兄弟（它的新父亲的另一个儿子）为S（S以前是M的兄弟）。在下图中，我们也使用P作为N的新父亲（M的老父亲），S_L代表S的左儿子，S_R代表S的右儿子。（S不能是叶子，因为如果M和C是黑色的，那么P的一个包含M 的子树计算两个黑色高度，因此P的其它包含S的子树也必须计算两个黑色高度，而如果S是叶节点，情况就不一样了。）

我们可以使用以下代码执行上面列出的步骤，其中函数replace_node替换child为树中的第n的位置。为方便起见，本节中的代码将假定null叶子由实际节点对象而不是NULL表示。

void ReplaceNode(Node* n, Node* child) {
  child->parent = n->parent;
  if (n == n->parent->left) {
    n->parent->left = child;
  } else {
    n->parent->right = child;
  }
}

void DeleteOneChild(Node* n) {
  // Precondition: n has at most one non-leaf child.
  Node* child = (n->right == nullptr) ? n->left : n->right;
  assert(child);

  ReplaceNode(n, child);
  if (n->color == BLACK) {
    if (child->color == RED) {
      child->color = BLACK;
    } else {
      DeleteCase1(child);
    }
  }
  free(n);
}

注意：如果N是空叶并且我们不想将空叶表示为实际节点对象，我们可以通过首先在其父节点（我们删除的节点，n在上面的代码中）调用delete_case1（）并删除来修改算法事后呢。如果父级是黑色（红色是微不足道的），我们这样做，因此它的行为方式与空叶子相同（有时也称为“幻影”叶子）。我们可以安全地删除它，因为n在所有操作之后它仍然是一片叶子，如上所示。此外，案例2和案例3中的兄弟测试需要更新，因为兄弟姐妹不再将孩子表示为对象。

如果N及其原始父项都是黑色，则删除此原始父项会导致通过N的路径比没有路径的路径少一个黑色节点。由于这违反了属性5（从任何给定节点到其叶节点的所有路径都包含相同数量的黑色节点），因此必须重新平衡树。有几种情况需要考虑：

情形1：N是新的根

在这种情形下，我们就做完了。我们从所有路径去除了一个黑色节点，而新根是黑色的，所有性质都保持着。

void DeleteCase1(Node* n) {
  if (n->parent != nullptr) {
    DeleteCase2(n);
  }
}

注：在情形2、5和6下，我们假定N是它父亲P的左儿子。如果它是右儿子，则在这些情形下的左和右应当对调。同样，代码示例将两种情况都考虑在内。

情形2：S是红色

在这种情形下我们反转P和S的颜色，然后在P处进行左旋，将S变成N的祖父。注意P一定是是黑色的，因为它有一个红色的孩子。现在子树右一个路径短了一个黑色节点（N是删除了黑色节点后替换上来的子节点），所以我们没有完成。现在N有一个黑色兄弟（因为它曾经是红色S的孩子）和一个红色父亲，所以我们可以进入第4步，第5步或第6步。在以后的情况下，我们将重新标记N的新兄弟S。

void DeleteCase2(Node* n) {
  Node* s = GetSibling(n);

  if (s->color == RED) {
    n->parent->color = RED;
    s->color = BLACK;
    if (n == n->parent->left) {
      RotateLeft(n->parent);
    } else {
      RotateRight(n->parent);
    }
  }
  DeleteCase3(n);
}

情形3：P、S和S的儿子都是黑色

在这种情形下，我们只是重新绘制S红色。结果是所有通过S的路径（正是那些不通过N的路径）的黑色节点少一个。因为删除N的原始父级使得通过N的所有路径都有一个较少的黑色节点，这使事情都平衡了起来。但是，现在通过P的所有路径都比没有通过P的路径少一个黑色节点，即违反了性质5（路径黑相同）。为纠正这个问题，我们按照情形1在P上重新调整平衡。

void DeleteCase3(Node* n) {
  Node* s = GetSibling(n);

  if ((n->parent->color == BLACK) && (s->color == BLACK) &&
      (s->left->color == BLACK) && (s->right->color == BLACK)) {
    s->color = RED;
    DeleteCase1(n->parent);
  } else {
    DeleteCase4(n);
  }
}

情形4：S和S的儿子都是黑色，但P是红色

在这种情形下，我我们只需交换S和P的颜色。这不会影响通过S的路径上的黑色节点数量，但它会在通过N的路径上添加一个黑色节点数，这恰好弥补了这些路径上已删除的黑色节点。

void DeleteCase4(Node* n) {
  Node* s = GetSibling(n);

  if ((n->parent->color == RED) && (s->color == BLACK) &&
      (s->left->color == BLACK) && (s->right->color == BLACK)) {
    s->color = RED;
    n->parent->color = BLACK;
  } else {
    DeleteCase5(n);
  }
}

情形5：S是黑色，S的左儿子是红色，S的右儿子是黑色，而N是它父亲的左儿子

在这种情形下我们在S处右旋，这样S的左孩子就成了S的父亲和N的新兄弟。然后我们交换S和它的新父亲的颜色。所有路径仍然有相同数量的黑结点，但现在N有了一个黑兄弟，其右孩子是红色，所以我们进入情形6。N和它的父亲不受这种转变的影响。（同样，对于情形6，我们将N的新兄弟重新标记为**S.**）

void DeleteCase5(Node* n) {
  Node* s = GetSibling(n);

  // This if statement is trivial, due to case 2 (even though case 2 changed
  // the sibling to a sibling's child, the sibling's child can't be red, since
  // no red parent can have a red child).
  if (s->color == BLACK) {
    // The following statements just force the red to be on the left of the
    // left of the parent, or right of the right, so case six will rotate
    // correctly.
    if ((n == n->parent->left) && (s->right->color == BLACK) &&
        (s->left->color == RED)) {
      // This last test is trivial too due to cases 2-4.
      s->color = RED;
      s->left->color = BLACK;
      RotateRight(s);
    } else if ((n == n->parent->right) && (s->left->color == BLACK) &&
               (s->right->color == RED)) {
      // This last test is trivial too due to cases 2-4.
      s->color = RED;
      s->right->color = BLACK;
      RotateLeft(s);
    }
  }
  DeleteCase6(n);
}

情形6：S是黑色，S的右儿子是红色，N是它父亲的左儿子

我们在P处左旋，这样S成为P和S的右孩子的父亲。然后我们交换P和S的颜色，并使S的右孩子变成黑色。子树的根仍然具有相同的颜色，因此不违反性质4（一红生两黑）和性质5（路径黑相同）。然而，N现在有一个额外的黑色祖先：或者P变成黑色，或者它是黑色而S被添加为一个黑色祖父。因此，通过N的路径都增加了一个黑色节点。此时，如果一个路径不通过N，则有两种可能性：

它通过N的新兄弟S_L，一个任意颜色的节点和子树标记为3的根节点。那么它以前和现在都必定经过S和P，而它们只是交换了颜色，所以路径保持了同样数目的黑色节点。
它通过N的新叔父和S的右儿子。那么它以前通过S、S的父亲和S的右儿子S_R（红色），但是现在只通过S，它被假定为它以前父亲的颜色，和S的右儿子，它被从红色改变为黑色（假设S的是黑色）。合成效果是这个路径通过了同样数目的黑色节点。

无论哪种情况，在这些路径上的黑色节点数目都没有改变。因此我们恢复了性质4（一红生两黑）和性质5（路径黑相同）。图中的白色节点可以是红色或黑色，但是在变换前后都必须指定相同的颜色。

void DeleteCase6(Node* n) {
  Node* s = GetSibling(n);

  s->color = n->parent->color;
  n->parent->color = BLACK;

  if (n == n->parent->left) {
    s->right->color = BLACK;
    RotateLeft(n->parent);
  } else {
    s->left->color = BLACK;
    RotateRight(n->parent);
  }
}