紅黑樹

紅黑樹是一種自平衡的二叉搜索樹。每個節點額外存儲了一個 color 字段 ("RED" or "BLACK")，用於確保樹在插入和刪除時保持平衡。

性質

一棵合法的紅黑樹必須遵循以下四條性質：

1. 節點為紅色或黑色
2. NIL 節點（空葉子節點）為黑色
3. 紅色節點的子節點為黑色
4. 從根節點到 NIL 節點的每條路徑上的黑色節點數量相同

下圖為一棵合法的紅黑樹：

注：部分資料中還加入了第五條性質，即根節點必須為黑色，這條性質要求完成插入操作後若根節點為紅色則將其染黑，但由於將根節點染黑的操作也可以延遲至刪除操作時進行，因此，該條性質並非必須滿足。（在本文給出的代碼實現中就沒有選擇滿足該性質）。為嚴謹起見，這裏同時引用 維基百科原文 進行説明：

Some authors, e.g. Cormen & al.,¹claim "the root is black" as fifth requirement; but not Mehlhorn & Sanders²or Sedgewick & Wayne.³Since the root can always be changed from red to black, this rule has little effect on analysis. This article also omits it, because it slightly disturbs the recursive algorithms and proofs.

結構

紅黑樹類的定義

template <typename Key, typename Value, typename Compare = std::less<Key>>
class RBTreeMap {
  // 排序函數
  Compare compare = Compare();

  // 節點結構體
  struct Node {
    ...
  };

  // 根節點指針
  Node* root = nullptr;
  // 記錄紅黑樹中當前的節點個數
  size_t count = 0;
}

節點維護的信息

Identifier	Type	Description
left	Node*	左子節點指針
right	Node*	右子節點指針
parent	Node*	父節點指針
color	enum { BLACK, RED }	顏色枚舉
key	Key	節點鍵值，具有唯一性和可排序性
value	Value	節點內儲存的值

注：由於本文提供的代碼示例中使用 std::share_ptr 進行內存管理，對此不熟悉的讀者可以將下文中所有的 NodePtr 和 ConstNodePtr 理解為裸指針 Node*。但在實現刪除操作時若使用 Node* 作為節點引用需注意應手動釋放內存以避免內存泄漏，該操作在使用 std::shared_ptr 作為節點引用的示例代碼中並未體現。

過程

注：由於紅黑樹是由 B 樹衍生而來（發明時的最初的名字 symmetric binary B-tree 足以證明這點），並非直接由平衡二叉樹外加限制條件推導而來，插入操作的後續維護和刪除操作的後續維護中部分對操作的解釋作用僅是幫助理解，並不能將其作為該操作的原理推導和證明。

旋轉操作

旋轉操作是多數平衡樹能夠維持平衡的關鍵，它能在不改變一棵合法 BST 中序遍歷結果的情況下改變局部節點的深度。

如上圖，從左圖到右圖的過程被稱為右旋，右旋操作會使得 \(T3\) 子樹上結點的深度均減 1，使 \(T1\) 子樹上結點的深度均加 1，而 \(T2\) 子樹上節點的深度則不變。從右圖到左圖的過程被稱為左旋，左旋是右旋的鏡像操作。

這裏給出紅黑樹中節點的左旋操作的示例代碼：

實現

void rotateLeft(ConstNodePtr node) {
  // clang-format off
  //     |                       |
  //     N                       S
  //    / \     l-rotate(N)     / \
  //   L   S    ==========>    N   R
  //      / \                 / \
  //     M   R               L   M
  assert(node != nullptr && node->right != nullptr);
  // clang-format on
  NodePtr parent = node->parent;
  Direction direction = node->direction();

  NodePtr successor = node->right;
  node->right = successor->left;
  successor->left = node;

  // 以下的操作用於維護各個節點的`parent`指針
  // `Direction`的定義以及`maintainRelationship`
  // 的實現請參照文章末尾的完整示例代碼
  maintainRelationship(node);
  maintainRelationship(successor);

  switch (direction) {
    case Direction::ROOT:
      this->root = successor;
      break;
    case Direction::LEFT:
      parent->left = successor;
      break;
    case Direction::RIGHT:
      parent->right = successor;
      break;
  }

  successor->parent = parent;
}

注：代碼中的 successor 並非平衡樹中的後繼節點，而是表示取代原本節點的新節點，由於在圖示中 replacement 的簡稱 R 會與右子節點的簡稱 R 衝突，因此此處使用 successor 避免歧義。

插入操作

紅黑樹的插入操作與普通的 BST 類似，對於紅黑樹來説，新插入的節點初始為紅色，完成插入後需根據插入節點及相關節點的狀態進行修正以滿足上文提到的四條性質。

插入後的平衡維護

Case 1

該樹原先為空，插入第一個節點後不需要進行修正。

Case 2

當前的節點的父節點為黑色且為根節點，這時性質已經滿足，不需要進行修正。

Case 3

當前節點 N 的父節點 P 是為根節點且為紅色，將其染為黑色即可，此時性質也已滿足，不需要進一步修正。

實現

// clang-format off
// Case 3: Parent is root and is RED
//   Paint parent to BLACK.
//    <P>         [P]
//     |   ====>   |
//    <N>         <N>
//   p.s.
//    `<X>` is a RED node;
//    `[X]` is a BLACK node (or NIL);
//    `{X}` is either a RED node or a BLACK node;
// clang-format on
assert(node->parent->isRed());
node->parent->color = Node::BLACK;
return;

Case 4

當前節點 N 的父節點 P 和叔節點 U 均為紅色，此時 P 包含了一個紅色子節點，違反了紅黑樹的性質，需要進行重新染色。由於在當前節點 N 之前該樹是一棵合法的紅黑樹，根據性質 3 可以確定 N 的祖父節點 G 一定是黑色，這時只要後續操作可以保證以 G 為根節點的子樹在不違反性質 4 的情況下再遞歸維護祖父節點 G 以保證性質 3 即可。

因此，這種情況的維護需要：

1. 將 P，U 節點染黑，將 G 節點染紅（可以保證每條路徑上黑色節點個數不發生改變）。
2. 遞歸維護 G 節點（因為不確定 G 的父節點的狀態，遞歸維護可以確保性質 3 成立）。

實現

// clang-format off
// Case 4: Both parent and uncle are RED
//   Paint parent and uncle to BLACK;
//   Paint grandparent to RED.
//        [G]             <G>
//        / \             / \
//      <P> <U>  ====>  [P] [U]
//      /               /
//    <N>             <N>
// clang-format on
assert(node->parent->isRed());
node->parent->color = Node::BLACK;
node->uncle()->color = Node::BLACK;
node->grandParent()->color = Node::RED;
maintainAfterInsert(node->grandParent());
return;

Case 5

當前節點 N 與父節點 P 的方向相反（即 N 節點為右子節點且父節點為左子節點，或 N 節點為左子節點且父節點為右子節點。類似 AVL 樹中 LR 和 RL 的情況）。根據性質 4，若 N 為新插入節點，U 則為 NIL 黑色節點，否則為普通黑色節點。

該種情況無法直接進行維護，需要通過旋轉操作將子樹結構調整為 Case 6 的初始狀態並進入 Case 6 進行後續維護。

實現

// clang-format off
// Case 5: Current node is the opposite direction as parent
//   Step 1. If node is a LEFT child, perform l-rotate to parent;
//           If node is a RIGHT child, perform r-rotate to parent.
//   Step 2. Goto Case 6.
//      [G]                 [G]
//      / \    rotate(P)    / \
//    <P> [U]  ========>  <N> [U]
//      \                 /
//      <N>             <P>
// clang-format on

// Step 1: Rotation
NodePtr parent = node->parent;
if (node->direction() == Direction::LEFT) {
  rotateRight(node->parent);
} else /* node->direction() == Direction::RIGHT */ {
  rotateLeft(node->parent);
}
node = parent;
// Step 2: vvv

Case 6

當前節點 N 與父節點 P 的方向相同（即 N 節點為右子節點且父節點為右子節點，或 N 節點為左子節點且父節點為右子節點。類似 AVL 樹中 LL 和 RR 的情況）。根據性質 4，若 N 為新插入節點，U 則為 NIL 黑色節點，否則為普通黑色節點。

在這種情況下，若想在不改變結構的情況下使得子樹滿足性質 3，則需將 G 染成紅色，將 P 染成黑色。但若這樣維護的話則性質 4 被打破，且無法保證在 G 節點的父節點上性質 3 是否成立。而選擇通過旋轉改變子樹結構後再進行重新染色即可同時滿足性質 3 和 4。

因此，這種情況的維護需要：

1. 若 N 為左子節點則右旋祖父節點 G，否則左旋祖父節點 G.（該操作使得旋轉過後 P - N 這條路徑上的黑色節點個數比 P - G - U 這條路徑上少 1，暫時打破性質 4）。
2. 重新染色，將 P 染黑，將 G 染紅，同時滿足了性質 3 和 4。

實現

// clang-format off
// Case 6: Current node is the same direction as parent
//   Step 1. If node is a LEFT child, perform r-rotate to grandparent;
//           If node is a RIGHT child, perform l-rotate to grandparent.
//   Step 2. Paint parent (before rotate) to BLACK;
//           Paint grandparent (before rotate) to RED.
//        [G]                 <P>               [P]
//        / \    rotate(G)    / \    repaint    / \
//      <P> [U]  ========>  <N> [G]  ======>  <N> <G>
//      /                         \                 \
//    <N>                         [U]               [U]
// clang-format on
assert(node->grandParent() != nullptr);

// Step 1
if (node->parent->direction() == Direction::LEFT) {
  rotateRight(node->grandParent());
} else {
  rotateLeft(node->grandParent());
}

// Step 2
node->parent->color = Node::BLACK;
node->sibling()->color = Node::RED;

return;

刪除操作

紅黑樹的刪除操作情況繁多，較為複雜。這部分內容主要通過代碼示例來進行講解。大多數紅黑樹的實現選擇將節點的刪除以及刪除之後的維護寫在同一個函數或邏輯塊中（例如 Wikipedia 給出的 代碼示例，linux 內核中的 rbtree 以及 GNU libstdc++ 中的 std::_Rb_tree 都使用了類似的寫法）。筆者則認為這種實現方式並不利於對算法本身的理解，因此，本文給出的示例代碼參考了 OpenJDK 中 TreeMap 的實現，將刪除操作本身與刪除後的平衡維護操作解耦成兩個獨立的函數，並對這兩部分的邏輯單獨進行分析。

Case 0

若待刪除節點為根節點的話，直接刪除即可，這裏不將其算作刪除操作的 3 種基本情況中。

Case 1

若待刪除節點 N 既有左子節點又有右子節點，則需找到它的前驅或後繼節點進行替換（僅替換數據，不改變節點顏色和內部引用關係），則後續操作中只需要將後繼節點刪除即可。這部分操作與普通 BST 完全相同，在此不再過多贅述。

注：這裏選擇的前驅或後繼節點保證不會是一個既有非 NIL 左子節點又有非 NIL 右子節點的節點。這裏拿後繼節點進行簡單説明：若該節點包含非空左子節點，則該節點並非是 N 節點右子樹上鍵值最小的節點，與後繼節點的性質矛盾，因此後繼節點的左子節點必須為 NIL。

實現

// clang-format off
// Case 1: If the node is strictly internal
//   Step 1. Find the successor S with the smallest key
//           and its parent P on the right subtree.
//   Step 2. Swap the data (key and value) of S and N,
//           S is the node that will be deleted in place of N.
//   Step 3. N = S, goto Case 2, 3
//     |                    |
//     N                    S
//    / \                  / \
//   L  ..   swap(N, S)   L  ..
//       |   =========>       |
//       P                    P
//      / \                  / \
//     S  ..                N  ..
// clang-format on

// Step 1
NodePtr successor = node->right;
NodePtr parent = node;
while (successor->left != nullptr) {
  parent = successor;
  successor = parent->left;
}
// Step 2
swapNode(node, successor);
maintainRelationship(parent);
// Step 3: vvv

Case 2

待刪除節點為葉子節點，若該節點為紅色，直接刪除即可，刪除後仍能保證紅黑樹的 4 條性質。若為黑色，刪除後性質 4 被打破，需要重新進行維護。

注：由於維護操作不會改變待刪除節點的任何結構和數據，因此此處的代碼示例中為了實現方便起見選擇先進行維護，再解引用相關節點。

實現

// clang-format off
// Case 2: Current node is a leaf
//   Step 1. Unlink and remove it.
//   Step 2. If N is BLACK, maintain N;
//           If N is RED, do nothing.
// clang-format on
// The maintain operation won't change the node itself,
//  so we can perform maintain operation before unlink the node.
if (node->isBlack()) {
  maintainAfterRemove(node);
}
if (node->direction() == Direction::LEFT) {
  node->parent->left = nullptr;
} else /* node->direction() == Direction::RIGHT */ {
  node->parent->right = nullptr;
}

Case 3

待刪除節點 N 有且僅有一個非 NIL 子節點，則子節點 S 一定為紅色。因為如果子節點 S 為黑色，則 S 的黑深度和待刪除結點的黑深度不同，違反性質 4。由於子節點 S 為紅色，則待刪除節點 N 為黑色，直接使用子節點 S 替代 N 並將其染黑後即可滿足性質 4。

實現

// Case 3: Current node has a single left or right child
//   Step 1. Replace N with its child
//   Step 2. Paint N to BLACK
NodePtr parent = node->parent;
NodePtr replacement = (node->left != nullptr ? node->left : node->right);

switch (node->direction()) {
  case Direction::ROOT:
    this->root = replacement;
    break;
  case Direction::LEFT:
    parent->left = replacement;
    break;
  case Direction::RIGHT:
    parent->right = replacement;
    break;
}

if (!node->isRoot()) {
  replacement->parent = parent;
}

node->color = Node::BLACK;

刪除後的平衡維護

Case 1

兄弟節點 (sibling node) S 為紅色，則父節點 P 和侄節點 (nephew node) C 和 D 必為黑色（否則違反性質 3）。與插入後維護操作的 Case 5 類似，這種情況下無法通過直接的旋轉或染色操作使其滿足所有性質，因此通過前置操作優先保證部分結構滿足性質，再進行後續維護即可。

這種情況的維護需要：

1. 若待刪除節點 N 為左子節點，左旋 P; 若為右子節點，右旋 P。
2. 將 S 染黑，P 染紅（保證 S 節點的父節點滿足性質 4）。
3. 此時只需根據結構，在以 P 節點為根的子樹中，繼續對節點 N 進行維護即可（無需再考慮旋轉染色後的 S 和 D 節點）。

實現

// clang-format off

// Case 1: Sibling is RED, parent and nephews must be BLACK
//   Step 1. If N is a left child, left rotate P;
//           If N is a right child, right rotate P.
//   Step 2. Paint S to BLACK, P to RED
//   Step 3. Goto Case 2, 3, 4, 5
//      [P]                   <S>               [S]
//      / \    l-rotate(P)    / \    repaint    / \
//    [N] <S>  ==========>  [P] [D]  ======>  <P> [D]
//        / \               / \               / \
//      [C] [D]           [N] [C]           [N] [C]
// clang-format on
ConstNodePtr parent = node->parent;
assert(parent != nullptr && parent->isBlack());
assert(sibling->left != nullptr && sibling->left->isBlack());
assert(sibling->right != nullptr && sibling->right->isBlack());
// Step 1
rotateSameDirection(node->parent, direction);
// Step 2
sibling->color = Node::BLACK;
parent->color = Node::RED;
// Update sibling after rotation
sibling = node->sibling();
// Step 3: vvv

Case 2

兄弟節點 S 和侄節點 C, D 均為黑色，父節點 P 為紅色。此時只需將 S 染紅，將 P 染黑即可滿足性質 3 和 4。

實現

// clang-format off
// Case 2: Sibling and nephews are BLACK, parent is RED
//   Swap the color of P and S
//      <P>             [P]
//      / \             / \
//    [N] [S]  ====>  [N] <S>
//        / \             / \
//      [C] [D]         [C] [D]
// clang-format on
sibling->color = Node::RED;
node->parent->color = Node::BLACK;
return;

Case 3

兄弟節點 S，父節點 P 以及侄節點 C, D 均為黑色。

此時也無法通過一步操作同時滿足性質 3 和 4，因此選擇將 S 染紅，優先滿足局部性質 4 的成立，再遞歸維護 P 節點根據上部結構進行後續維護。

實現

// clang-format off
// Case 3: Sibling, parent and nephews are all black
//   Step 1. Paint S to RED
//   Step 2. Recursively maintain P
//      [P]             [P]
//      / \             / \
//    [N] [S]  ====>  [N] <S>
//        / \             / \
//      [C] [D]         [C] [D]
// clang-format on
sibling->color = Node::RED;
maintainAfterRemove(node->parent);
return;

Case 4

兄弟節點是黑色，且與 N 同向的侄節點 C（由於沒有固定中文翻譯，下文還是統一將其稱作 close nephew）為紅色，與 N 反向的侄節點 D（同理，下文稱作 distant nephew）為黑色，父節點既可為紅色又可為黑色。

此時同樣無法通過一步操作使其滿足性質，因此優先選擇將其轉變為 Case 5 的狀態利用後續 Case 5 的維護過程進行修正。

該過程分為三步：

1. 若 N 為左子節點，右旋 P，否則左旋 P。
2. 將節點 S 染紅，將節點 C 染黑。
3. 此時已滿足 Case 5 的條件，進入 Case 5 完成後續維護。

實現

// clang-format off
// Case 4: Sibling is BLACK, close nephew is RED,
//         distant nephew is BLACK
//   Step 1. If N is a left child, right rotate P;
//           If N is a right child, left rotate P.
//   Step 2. Swap the color of close nephew and sibling
//   Step 3. Goto case 5
//                            {P}                {P}
//      {P}                   / \                / \
//      / \    r-rotate(S)  [N] <C>   repaint  [N] [C]
//    [N] [S]  ==========>        \   ======>        \
//        / \                     [S]                <S>
//      <C> [D]                     \                  \
//                                  [D]                [D]
// clang-format on

// Step 1
rotateOppositeDirection(sibling, direction);
// Step 2
closeNephew->color = Node::BLACK;
sibling->color = Node::RED;
// Update sibling and nephews after rotation
sibling = node->sibling();
closeNephew = direction == Direction::LEFT ? sibling->left : sibling->right;
distantNephew = direction == Direction::LEFT ? sibling->right : sibling->left;
// Step 3: vvv

Case 5

兄弟節點是黑色，且 close nephew 節點 C 為黑色，distant nephew 節點 D 為紅色，父節點既可為紅色又可為黑色。此時性質 4 無法滿足，通過旋轉操作使得黑色節點 S 變為該子樹的根節點再進行染色即可滿足性質 4。具體步驟如下：

1. 若 N 為左子節點，左旋 P，反之右旋 P。
2. 交換父節點 P 和兄弟節點 S 的顏色，此時性質 3 可能被打破。
3. 將 distant nephew 節點 D 染黑，同時保證了性質 3 和 4。

實現

// clang-format off
// Case 5: Sibling is BLACK, close nephew is BLACK,
//         distant nephew is RED
//   Step 1. If N is a left child, left rotate P;
//           If N is a right child, right rotate P.
//   Step 2. Swap the color of parent and sibling.
//   Step 3. Paint distant nephew D to BLACK.
//      {P}                   [S]               {S}
//      / \    l-rotate(P)    / \    repaint    / \
//    [N] [S]  ==========>  {P} <D>  ======>  [P] [D]
//        / \               / \               / \
//      [C] <D>           [N] [C]           [N] [C]
// clang-format on
assert(closeNephew == nullptr || closeNephew->isBlack());
assert(distantNephew->isRed());
// Step 1
rotateSameDirection(node->parent, direction);
// Step 2
sibling->color = node->parent->color;
node->parent->color = Node::BLACK;
// Step 3
distantNephew->color = Node::BLACK;
return;

紅黑樹與 4 階 B 樹（2-3-4 樹）的關係

紅黑樹是由德國計算機科學家 Rudolf Bayer 在 1972 年從 B 樹上改進過來的，紅黑樹在當時被稱作 "symmetric binary B-tree"，因此與 B 樹有眾多相似之處。比如紅黑樹與 4 階 B 樹每個簇（對於紅黑樹來説一個簇是一個非 NIL 黑色節點和它的兩個子節點，對 B 樹來説一個簇就是一個節點）的最大容量為 3 且最小填充量均為 \(\frac{1}{3}\)。因此我們甚至可以説紅黑樹與 4 階 B 樹（2-3-4 樹）在結構上是等價的。

對這方面內容感興趣的可以觀看 從 2-3-4 樹的角度學習理解紅黑樹（視頻） 進行學習。

雖然二者在結構上是等價的，但這並不意味這二者可以互相取代或者在所有情況下都可以互換使用。最顯然的例子就是數據庫的索引，由於 B 樹不存在旋轉操作，因此其所有節點的存儲位置都是可以被確定的，這種結構對於不區分堆棧的磁盤來説顯然比紅黑樹動態分配節點存儲空間要更加合適。另外一點就是由於 B 樹/B+ 樹內儲存的數據都是連續的，對於有着大量連續查詢需求的數據庫來説更加友好。而對於小數據量隨機插入/查詢的需求，由於 B 樹的每個節點都存儲了若干條記錄，因此發生 cache miss 時就需要將整個節點的所有數據讀入緩存中，在這些情況下 BST（紅黑樹，AVL，Splay 等）則反而會優與 B 樹/B+ 樹。對這方面內容感興趣的讀者可以去閲讀一下 為什麼 rust 中的 Map 使用的是 B 樹而不是像其他主流語言一樣使用紅黑樹。

紅黑樹在實際工程項目中的使用

由於紅黑樹是目前主流工業界綜合效率最高的內存型平衡樹，其在實際的工程項目中有着廣泛的使用，這裏列舉幾個實際的使用案例並給出相應的源碼鏈接，以便讀者進行對比學習。

Linux

源碼：

• linux/lib/rbtree.c

Linux 中的紅黑樹所有操作均使用循環迭代進行實現，保證效率的同時又增加了大量的註釋來保證代碼可讀性，十分建議讀者閲讀學習。Linux 內核中的紅黑樹使用非常廣泛，這裏僅列舉幾個經典案例。

CFS 非實時任務調度

Linux 的穩定內核版本在 2.6.24 之後，使用了新的調度程序 CFS，所有非實時可運行進程都以虛擬運行時間為鍵值用一棵紅黑樹進行維護，以完成更公平高效地調度所有任務。CFS 棄用 active/expired 數組和動態計算優先級，不再跟蹤任務的睡眠時間和區別是否交互任務，而是在調度中採用基於時間計算鍵值的紅黑樹來選取下一個任務，根據所有任務佔用 CPU 時間的狀態來確定調度任務優先級。

epoll

epoll 全稱 event poll，是 Linux 內核實現 IO 多路複用 (IO multiplexing) 的一個實現，是原先 poll/select 的改進版。Linux 中 epoll 的實現選擇使用紅黑樹來儲存文件描述符。

Nginx

源碼：

• nginx/src/core/ngx_rbtree.h
• nginx/src/core/ngx_rbtree.c

nginx 中的用户態定時器是通過紅黑樹實現的。在 nginx 中，所有 timer 節點都由一棵紅黑樹進行維護，在 worker 進程的每一次循環中都會調用 ngx_process_events_and_timers 函數，在該函數中就會調用處理定時器的函數 ngx_event_expire_timers，每次該函數都不斷的從紅黑樹中取出時間值最小的，查看他們是否已經超時，然後執行他們的函數，直到取出的節點的時間沒有超時為止。

關於 nginx 中紅黑樹的源碼分析公開資源很多，讀者可以自行查找學習。

STL

源碼：

• GNU libstdc++

  • libstdc++-v3/include/bits/stl_tree.h
  • libstdc++-v3/src/c++98/tree.cc

• LLVM libcxx

  • libcxx/include/__tree

• Microsoft STL

  • stl/inc/xtree

大多數 STL 中的 std::map 和 std::set 的內部數據結構就是一棵紅黑樹（例如上面提到的這些）。不過值得注意的是，這些紅黑樹（包括可能有讀者用過的 std::_Rb_tree）都不是 C++ 標準，雖然部分競賽（例如 NOIP）並未明令禁止這類數據結構，但還是應當注意這類標準庫中的非標準實現不應該在工程項目中直接使用。

由於 STL 的特殊性，其中大多數實現的代碼可讀性都不高，因此並不建議讀者使用 STL 學習紅黑樹。

OpenJDK

源碼：

• java.util.TreeMap<K, V>
• java.util.TreeSet<K, V>
• java.util.HashMap<K, V>

JDK 中的 TreeMap 和 TreeSet 都是使用紅黑樹作為底層數據結構的。同時在 JDK 1.8 之後 HashMap 內部哈希表中每個表項的鏈表長度超過 8 時也會自動轉變為紅黑樹以提升查找效率。

筆者認為，JDK 中的紅黑樹實現是主流紅黑樹實現中可讀性最高的，本文提供的參考代碼很大程度上借鑑了 JDK 中 TreeMap 的實現，因此也建議讀者閲讀學習 JDK 中 TreeMap 的實現。

參考代碼

下面的代碼是用紅黑樹實現的 Map，即有序不可重映射：

完整代碼

/**
 * @file RBTreeMap.hpp
 * @brief An RBTree-based map implementation
 * @details The map is sorted according to the natural ordering of its
 *  keys or by a {@code Compare} function provided; This implementation
 *  provides guaranteed log(n) time cost for the contains, get, insert
 *  and remove operations.
 * @author [r.ivance](https://github.com/RIvance)
 */

#ifndef RBTREE_MAP_HPP
#define RBTREE_MAP_HPP

#include <cassert>
#include <cstddef>
#include <cstdint>
#include <functional>
#include <memory>
#include <stack>
#include <utility>
#include <vector>

/**
 * An RBTree-based map implementation
 * https://en.wikipedia.org/wiki/Red–black_tree
 *
 * A red–black tree (RBTree) is a kind of self-balancing binary search tree.
 * Each node stores an extra field representing "color" (RED or BLACK), used
 * to ensure that the tree remains balanced during insertions and deletions.
 *
 * In addition to the requirements imposed on a binary search tree the following
 * must be satisfied by a red–black tree:
 *
 *  1. Every node is either RED or BLACK.
 *  2. All NIL nodes (`nullptr` in this implementation) are considered BLACK.
 *  3. A RED node does not have a RED child.
 *  4. Every path from a given node to any of its descendant NIL nodes goes
 * through the same number of BLACK nodes.
 *
 * @tparam Key the type of keys maintained by this map
 * @tparam Value the type of mapped values
 * @tparam Compare the compare function
 */
template <typename Key, typename Value, typename Compare = std::less<Key> >
class RBTreeMap {
 private:
  using USize = size_t;

  Compare compare = Compare();

 public:
  struct Entry {
    Key key;
    Value value;

    bool operator==(const Entry &rhs) const noexcept {
      return this->key == rhs.key && this->value == rhs.value;
    }

    bool operator!=(const Entry &rhs) const noexcept {
      return this->key != rhs.key || this->value != rhs.value;
    }
  };

 private:
  struct Node {
    using Ptr = std::shared_ptr<Node>;
    using Provider = const std::function<Ptr(void)> &;
    using Consumer = const std::function<void(const Ptr &)> &;

    enum { RED, BLACK } color = RED;

    enum Direction { LEFT = -1, ROOT = 0, RIGHT = 1 };

    Key key;
    Value value{};

    Ptr parent = nullptr;
    Ptr left = nullptr;
    Ptr right = nullptr;

    explicit Node(Key k) : key(std::move(k)) {}

    explicit Node(Key k, Value v) : key(std::move(k)), value(std::move(v)) {}

    ~Node() = default;

    inline bool isLeaf() const noexcept {
      return this->left == nullptr && this->right == nullptr;
    }

    inline bool isRoot() const noexcept { return this->parent == nullptr; }

    inline bool isRed() const noexcept { return this->color == RED; }

    inline bool isBlack() const noexcept { return this->color == BLACK; }

    inline Direction direction() const noexcept {
      if (this->parent != nullptr) {
        if (this == this->parent->left.get()) {
          return Direction::LEFT;
        } else {
          return Direction::RIGHT;
        }
      } else {
        return Direction::ROOT;
      }
    }

    inline Ptr &sibling() const noexcept {
      assert(!this->isRoot());
      if (this->direction() == LEFT) {
        return this->parent->right;
      } else {
        return this->parent->left;
      }
    }

    inline bool hasSibling() const noexcept {
      return !this->isRoot() && this->sibling() != nullptr;
    }

    inline Ptr &uncle() const noexcept {
      assert(this->parent != nullptr);
      return parent->sibling();
    }

    inline bool hasUncle() const noexcept {
      return !this->isRoot() && this->parent->hasSibling();
    }

    inline Ptr &grandParent() const noexcept {
      assert(this->parent != nullptr);
      return this->parent->parent;
    }

    inline bool hasGrandParent() const noexcept {
      return !this->isRoot() && this->parent->parent != nullptr;
    }

    inline void release() noexcept {
      // avoid memory leak caused by circular reference
      this->parent = nullptr;
      if (this->left != nullptr) {
        this->left->release();
      }
      if (this->right != nullptr) {
        this->right->release();
      }
    }

    inline Entry entry() const { return Entry{key, value}; }

    static Ptr from(const Key &k) { return std::make_shared<Node>(Node(k)); }

    static Ptr from(const Key &k, const Value &v) {
      return std::make_shared<Node>(Node(k, v));
    }
  };

  using NodePtr = typename Node::Ptr;
  using ConstNodePtr = const NodePtr &;
  using Direction = typename Node::Direction;
  using NodeProvider = typename Node::Provider;
  using NodeConsumer = typename Node::Consumer;

  NodePtr root = nullptr;
  USize count = 0;

  using K = const Key &;
  using V = const Value &;

 public:
  using EntryList = std::vector<Entry>;
  using KeyValueConsumer = const std::function<void(K, V)> &;
  using MutKeyValueConsumer = const std::function<void(K, Value &)> &;
  using KeyValueFilter = const std::function<bool(K, V)> &;

  class NoSuchMappingException : protected std::exception {
   private:
    const char *message;

   public:
    explicit NoSuchMappingException(const char *msg) : message(msg) {}

    const char *what() const noexcept override { return message; }
  };

  RBTreeMap() noexcept = default;

  ~RBTreeMap() noexcept {
    // Unlinking circular references to avoid memory leak
    this->clear();
  }

  /**
   * Returns the number of entries in this map.
   * @return size_t
   */
  inline USize size() const noexcept { return this->count; }

  /**
   * Returns true if this collection contains no elements.
   * @return bool
   */
  inline bool empty() const noexcept { return this->count == 0; }

  /**
   * Removes all of the elements from this map.
   */
  void clear() noexcept {
    // Unlinking circular references to avoid memory leak
    if (this->root != nullptr) {
      this->root->release();
      this->root = nullptr;
    }
    this->count = 0;
  }

  /**
   * Returns the value to which the specified key is mapped; If this map
   * contains no mapping for the key, a {@code NoSuchMappingException} will
   * be thrown.
   * @param key
   * @return RBTreeMap<Key, Value>::Value
   * @throws NoSuchMappingException
   */
  Value get(K key) const {
    if (this->root == nullptr) {
      throw NoSuchMappingException("Invalid key");
    } else {
      NodePtr node = this->getNode(this->root, key);
      if (node != nullptr) {
        return node->value;
      } else {
        throw NoSuchMappingException("Invalid key");
      }
    }
  }

  /**
   * Returns the value to which the specified key is mapped; If this map
   * contains no mapping for the key, a new mapping with a default value
   * will be inserted.
   * @param key
   * @return RBTreeMap<Key, Value>::Value &
   */
  Value &getOrDefault(K key) {
    if (this->root == nullptr) {
      this->root = Node::from(key);
      this->root->color = Node::BLACK;
      this->count += 1;
      return this->root->value;
    } else {
      return this
          ->getNodeOrProvide(this->root, key,
                             [&key]() { return Node::from(key); })
          ->value;
    }
  }

  /**
   * Returns true if this map contains a mapping for the specified key.
   * @param key
   * @return bool
   */
  bool contains(K key) const {
    return this->getNode(this->root, key) != nullptr;
  }

  /**
   * Associates the specified value with the specified key in this map.
   * @param key
   * @param value
   */
  void insert(K key, V value) {
    if (this->root == nullptr) {
      this->root = Node::from(key, value);
      this->root->color = Node::BLACK;
      this->count += 1;
    } else {
      this->insert(this->root, key, value);
    }
  }

  /**
   * If the specified key is not already associated with a value, associates
   * it with the given value and returns true, else returns false.
   * @param key
   * @param value
   * @return bool
   */
  bool insertIfAbsent(K key, V value) {
    USize sizeBeforeInsertion = this->size();
    if (this->root == nullptr) {
      this->root = Node::from(key, value);
      this->root->color = Node::BLACK;
      this->count += 1;
    } else {
      this->insert(this->root, key, value, false);
    }
    return this->size() > sizeBeforeInsertion;
  }

  /**
   * If the specified key is not already associated with a value, associates
   * it with the given value and returns the value, else returns the associated
   * value.
   * @param key
   * @param value
   * @return RBTreeMap<Key, Value>::Value &
   */
  Value &getOrInsert(K key, V value) {
    if (this->root == nullptr) {
      this->root = Node::from(key, value);
      this->root->color = Node::BLACK;
      this->count += 1;
      return root->value;
    } else {
      NodePtr node = getNodeOrProvide(this->root, key,
                                      [&]() { return Node::from(key, value); });
      return node->value;
    }
  }

  Value operator[](K key) const { return this->get(key); }

  Value &operator[](K key) { return this->getOrDefault(key); }

  /**
   * Removes the mapping for a key from this map if it is present;
   * Returns true if the mapping is present else returns false
   * @param key the key of the mapping
   * @return bool
   */
  bool remove(K key) {
    if (this->root == nullptr) {
      return false;
    } else {
      return this->remove(this->root, key, [](ConstNodePtr) {});
    }
  }

  /**
   * Removes the mapping for a key from this map if it is present and returns
   * the value which is mapped to the key; If this map contains no mapping for
   * the key, a {@code NoSuchMappingException} will be thrown.
   * @param key
   * @return RBTreeMap<Key, Value>::Value
   * @throws NoSuchMappingException
   */
  Value getAndRemove(K key) {
    Value result;
    NodeConsumer action = [&](ConstNodePtr node) { result = node->value; };

    if (root == nullptr) {
      throw NoSuchMappingException("Invalid key");
    } else {
      if (remove(this->root, key, action)) {
        return result;
      } else {
        throw NoSuchMappingException("Invalid key");
      }
    }
  }

  /**
   * Gets the entry corresponding to the specified key; if no such entry
   * exists, returns the entry for the least key greater than the specified
   * key; if no such entry exists (i.e., the greatest key in the Tree is less
   * than the specified key), a {@code NoSuchMappingException} will be thrown.
   * @param key
   * @return RBTreeMap<Key, Value>::Entry
   * @throws NoSuchMappingException
   */
  Entry getCeilingEntry(K key) const {
    if (this->root == nullptr) {
      throw NoSuchMappingException("No ceiling entry in this map");
    }

    NodePtr node = this->root;

    while (node != nullptr) {
      if (key == node->key) {
        return node->entry();
      }

      if (compare(key, node->key)) {
        /* key < node->key */
        if (node->left != nullptr) {
          node = node->left;
        } else {
          return node->entry();
        }
      } else {
        /* key > node->key */
        if (node->right != nullptr) {
          node = node->right;
        } else {
          while (node->direction() == Direction::RIGHT) {
            if (node != nullptr) {
              node = node->parent;
            } else {
              throw NoSuchMappingException(
                  "No ceiling entry exists in this map");
            }
          }
          if (node->parent == nullptr) {
            throw NoSuchMappingException("No ceiling entry exists in this map");
          }
          return node->parent->entry();
        }
      }
    }

    throw NoSuchMappingException("No ceiling entry in this map");
  }

  /**
   * Gets the entry corresponding to the specified key; if no such entry exists,
   * returns the entry for the greatest key less than the specified key;
   * if no such entry exists, a {@code NoSuchMappingException} will be thrown.
   * @param key
   * @return RBTreeMap<Key, Value>::Entry
   * @throws NoSuchMappingException
   */
  Entry getFloorEntry(K key) const {
    if (this->root == nullptr) {
      throw NoSuchMappingException("No floor entry exists in this map");
    }

    NodePtr node = this->root;

    while (node != nullptr) {
      if (key == node->key) {
        return node->entry();
      }

      if (compare(key, node->key)) {
        /* key < node->key */
        if (node->left != nullptr) {
          node = node->left;
        } else {
          while (node->direction() == Direction::LEFT) {
            if (node != nullptr) {
              node = node->parent;
            } else {
              throw NoSuchMappingException("No floor entry exists in this map");
            }
          }
          if (node->parent == nullptr) {
            throw NoSuchMappingException("No floor entry exists in this map");
          }
          return node->parent->entry();
        }
      } else {
        /* key > node->key */
        if (node->right != nullptr) {
          node = node->right;
        } else {
          return node->entry();
        }
      }
    }

    throw NoSuchMappingException("No floor entry exists in this map");
  }

  /**
   * Gets the entry for the least key greater than the specified
   * key; if no such entry exists, returns the entry for the least
   * key greater than the specified key; if no such entry exists,
   * a {@code NoSuchMappingException} will be thrown.
   * @param key
   * @return RBTreeMap<Key, Value>::Entry
   * @throws NoSuchMappingException
   */
  Entry getHigherEntry(K key) {
    if (this->root == nullptr) {
      throw NoSuchMappingException("No higher entry exists in this map");
    }

    NodePtr node = this->root;

    while (node != nullptr) {
      if (compare(key, node->key)) {
        /* key < node->key */
        if (node->left != nullptr) {
          node = node->left;
        } else {
          return node->entry();
        }
      } else {
        /* key >= node->key */
        if (node->right != nullptr) {
          node = node->right;
        } else {
          while (node->direction() == Direction::RIGHT) {
            if (node != nullptr) {
              node = node->parent;
            } else {
              throw NoSuchMappingException(
                  "No higher entry exists in this map");
            }
          }
          if (node->parent == nullptr) {
            throw NoSuchMappingException("No higher entry exists in this map");
          }
          return node->parent->entry();
        }
      }
    }

    throw NoSuchMappingException("No higher entry exists in this map");
  }

  /**
   * Returns the entry for the greatest key less than the specified key; if
   * no such entry exists (i.e., the least key in the Tree is greater than
   * the specified key), a {@code NoSuchMappingException} will be thrown.
   * @param key
   * @return RBTreeMap<Key, Value>::Entry
   * @throws NoSuchMappingException
   */
  Entry getLowerEntry(K key) const {
    if (this->root == nullptr) {
      throw NoSuchMappingException("No lower entry exists in this map");
    }

    NodePtr node = this->root;

    while (node != nullptr) {
      if (compare(key, node->key) || key == node->key) {
        /* key <= node->key */
        if (node->left != nullptr) {
          node = node->left;
        } else {
          while (node->direction() == Direction::LEFT) {
            if (node != nullptr) {
              node = node->parent;
            } else {
              throw NoSuchMappingException("No lower entry exists in this map");
            }
          }
          if (node->parent == nullptr) {
            throw NoSuchMappingException("No lower entry exists in this map");
          }
          return node->parent->entry();
        }
      } else {
        /* key > node->key */
        if (node->right != nullptr) {
          node = node->right;
        } else {
          return node->entry();
        }
      }
    }

    throw NoSuchMappingException("No lower entry exists in this map");
  }

  /**
   * Remove all entries that satisfy the filter condition.
   * @param filter
   */
  void removeAll(KeyValueFilter filter) {
    std::vector<Key> keys;
    this->inorderTraversal([&](ConstNodePtr node) {
      if (filter(node->key, node->value)) {
        keys.push_back(node->key);
      }
    });
    for (const Key &key : keys) {
      this->remove(key);
    }
  }

  /**
   * Performs the given action for each key and value entry in this map.
   * The value is immutable for the action.
   * @param action
   */
  void forEach(KeyValueConsumer action) const {
    this->inorderTraversal(
        [&](ConstNodePtr node) { action(node->key, node->value); });
  }

  /**
   * Performs the given action for each key and value entry in this map.
   * The value is mutable for the action.
   * @param action
   */
  void forEachMut(MutKeyValueConsumer action) {
    this->inorderTraversal(
        [&](ConstNodePtr node) { action(node->key, node->value); });
  }

  /**
   * Returns a list containing all of the entries in this map.
   * @return RBTreeMap<Key, Value>::EntryList
   */
  EntryList toEntryList() const {
    EntryList entryList;
    this->inorderTraversal(
        [&](ConstNodePtr node) { entryList.push_back(node->entry()); });
    return entryList;
  }

 private:
  static void maintainRelationship(ConstNodePtr node) {
    if (node->left != nullptr) {
      node->left->parent = node;
    }
    if (node->right != nullptr) {
      node->right->parent = node;
    }
  }

  static void swapNode(NodePtr &lhs, NodePtr &rhs) {
    std::swap(lhs->key, rhs->key);
    std::swap(lhs->value, rhs->value);
    std::swap(lhs, rhs);
  }

  void rotateLeft(ConstNodePtr node) {
    // clang-format off
    //     |                       |
    //     N                       S
    //    / \     l-rotate(N)     / \
    //   L   S    ==========>    N   R
    //      / \                 / \
    //     M   R               L   M
    assert(node != nullptr && node->right != nullptr);
    // clang-format on
    NodePtr parent = node->parent;
    Direction direction = node->direction();

    NodePtr successor = node->right;
    node->right = successor->left;
    successor->left = node;

    maintainRelationship(node);
    maintainRelationship(successor);

    switch (direction) {
      case Direction::ROOT:
        this->root = successor;
        break;
      case Direction::LEFT:
        parent->left = successor;
        break;
      case Direction::RIGHT:
        parent->right = successor;
        break;
    }

    successor->parent = parent;
  }

  void rotateRight(ConstNodePtr node) {
    // clang-format off
    //       |                   |
    //       N                   S
    //      / \   r-rotate(N)   / \
    //     S   R  ==========>  L   N
    //    / \                     / \
    //   L   M                   M   R
    assert(node != nullptr && node->left != nullptr);
    // clang-format on

    NodePtr parent = node->parent;
    Direction direction = node->direction();

    NodePtr successor = node->left;
    node->left = successor->right;
    successor->right = node;

    maintainRelationship(node);
    maintainRelationship(successor);

    switch (direction) {
      case Direction::ROOT:
        this->root = successor;
        break;
      case Direction::LEFT:
        parent->left = successor;
        break;
      case Direction::RIGHT:
        parent->right = successor;
        break;
    }

    successor->parent = parent;
  }

  inline void rotateSameDirection(ConstNodePtr node, Direction direction) {
    assert(direction != Direction::ROOT);
    if (direction == Direction::LEFT) {
      rotateLeft(node);
    } else {
      rotateRight(node);
    }
  }

  inline void rotateOppositeDirection(ConstNodePtr node, Direction direction) {
    assert(direction != Direction::ROOT);
    if (direction == Direction::LEFT) {
      rotateRight(node);
    } else {
      rotateLeft(node);
    }
  }

  void maintainAfterInsert(NodePtr node) {
    assert(node != nullptr);

    if (node->isRoot()) {
      // Case 1: Current node is root (RED)
      //  No need to fix.
      assert(node->isRed());
      return;
    }

    if (node->parent->isBlack()) {
      // Case 2: Parent is BLACK
      //  No need to fix.
      return;
    }

    if (node->parent->isRoot()) {
      // clang-format off
      // Case 3: Parent is root and is RED
      //   Paint parent to BLACK.
      //    <P>         [P]
      //     |   ====>   |
      //    <N>         <N>
      //   p.s.
      //    `<X>` is a RED node;
      //    `[X]` is a BLACK node (or NIL);
      //    `{X}` is either a RED node or a BLACK node;
      // clang-format on
      assert(node->parent->isRed());
      node->parent->color = Node::BLACK;
      return;
    }

    if (node->hasUncle() && node->uncle()->isRed()) {
      // clang-format off
      // Case 4: Both parent and uncle are RED
      //   Paint parent and uncle to BLACK;
      //   Paint grandparent to RED.
      //        [G]             <G>
      //        / \             / \
      //      <P> <U>  ====>  [P] [U]
      //      /               /
      //    <N>             <N>
      // clang-format on
      assert(node->parent->isRed());
      node->parent->color = Node::BLACK;
      node->uncle()->color = Node::BLACK;
      node->grandParent()->color = Node::RED;
      maintainAfterInsert(node->grandParent());
      return;
    }

    if (!node->hasUncle() || node->uncle()->isBlack()) {
      // Case 5 & 6: Parent is RED and Uncle is BLACK
      //   p.s. NIL nodes are also considered BLACK
      assert(!node->isRoot());

      if (node->direction() != node->parent->direction()) {
        // clang-format off
        // Case 5: Current node is the opposite direction as parent
        //   Step 1. If node is a LEFT child, perform l-rotate to parent;
        //           If node is a RIGHT child, perform r-rotate to parent.
        //   Step 2. Goto Case 6.
        //      [G]                 [G]
        //      / \    rotate(P)    / \
        //    <P> [U]  ========>  <N> [U]
        //      \                 /
        //      <N>             <P>
        // clang-format on

        // Step 1: Rotation
        NodePtr parent = node->parent;
        if (node->direction() == Direction::LEFT) {
          rotateRight(node->parent);
        } else /* node->direction() == Direction::RIGHT */ {
          rotateLeft(node->parent);
        }
        node = parent;
        // Step 2: vvv
      }

      // clang-format off
      // Case 6: Current node is the same direction as parent
      //   Step 1. If node is a LEFT child, perform r-rotate to grandparent;
      //           If node is a RIGHT child, perform l-rotate to grandparent.
      //   Step 2. Paint parent (before rotate) to BLACK;
      //           Paint grandparent (before rotate) to RED.
      //        [G]                 <P>               [P]
      //        / \    rotate(G)    / \    repaint    / \
      //      <P> [U]  ========>  <N> [G]  ======>  <N> <G>
      //      /                         \                 \
      //    <N>                         [U]               [U]
      // clang-format on

      assert(node->grandParent() != nullptr);

      // Step 1
      if (node->parent->direction() == Direction::LEFT) {
        rotateRight(node->grandParent());
      } else {
        rotateLeft(node->grandParent());
      }

      // Step 2
      node->parent->color = Node::BLACK;
      node->sibling()->color = Node::RED;

      return;
    }
  }

  NodePtr getNodeOrProvide(NodePtr &node, K key, NodeProvider provide) {
    assert(node != nullptr);

    if (key == node->key) {
      return node;
    }

    assert(key != node->key);

    NodePtr result;

    if (compare(key, node->key)) {
      /* key < node->key */
      if (node->left == nullptr) {
        result = node->left = provide();
        node->left->parent = node;
        maintainAfterInsert(node->left);
        this->count += 1;
      } else {
        result = getNodeOrProvide(node->left, key, provide);
      }
    } else {
      /* key > node->key */
      if (node->right == nullptr) {
        result = node->right = provide();
        node->right->parent = node;
        maintainAfterInsert(node->right);
        this->count += 1;
      } else {
        result = getNodeOrProvide(node->right, key, provide);
      }
    }

    return result;
  }

  NodePtr getNode(ConstNodePtr node, K key) const {
    assert(node != nullptr);

    if (key == node->key) {
      return node;
    }

    if (compare(key, node->key)) {
      /* key < node->key */
      return node->left == nullptr ? nullptr : getNode(node->left, key);
    } else {
      /* key > node->key */
      return node->right == nullptr ? nullptr : getNode(node->right, key);
    }
  }

  void insert(NodePtr &node, K key, V value, bool replace = true) {
    assert(node != nullptr);

    if (key == node->key) {
      if (replace) {
        node->value = value;
      }
      return;
    }

    assert(key != node->key);

    if (compare(key, node->key)) {
      /* key < node->key */
      if (node->left == nullptr) {
        node->left = Node::from(key, value);
        node->left->parent = node;
        maintainAfterInsert(node->left);
        this->count += 1;
      } else {
        insert(node->left, key, value, replace);
      }
    } else {
      /* key > node->key */
      if (node->right == nullptr) {
        node->right = Node::from(key, value);
        node->right->parent = node;
        maintainAfterInsert(node->right);
        this->count += 1;
      } else {
        insert(node->right, key, value, replace);
      }
    }
  }

  void maintainAfterRemove(ConstNodePtr node) {
    if (node->isRoot()) {
      return;
    }

    assert(node->isBlack() && node->hasSibling());

    Direction direction = node->direction();

    NodePtr sibling = node->sibling();
    if (sibling->isRed()) {
      // clang-format off
      // Case 1: Sibling is RED, parent and nephews must be BLACK
      //   Step 1. If N is a left child, left rotate P;
      //           If N is a right child, right rotate P.
      //   Step 2. Paint S to BLACK, P to RED
      //   Step 3. Goto Case 2, 3, 4, 5
      //      [P]                   <S>               [S]
      //      / \    l-rotate(P)    / \    repaint    / \
      //    [N] <S>  ==========>  [P] [D]  ======>  <P> [D]
      //        / \               / \               / \
      //      [C] [D]           [N] [C]           [N] [C]
      // clang-format on
      ConstNodePtr parent = node->parent;
      assert(parent != nullptr && parent->isBlack());
      assert(sibling->left != nullptr && sibling->left->isBlack());
      assert(sibling->right != nullptr && sibling->right->isBlack());
      // Step 1
      rotateSameDirection(node->parent, direction);
      // Step 2
      sibling->color = Node::BLACK;
      parent->color = Node::RED;
      // Update sibling after rotation
      sibling = node->sibling();
      // Step 3: vvv
    }

    NodePtr closeNephew =
        direction == Direction::LEFT ? sibling->left : sibling->right;
    NodePtr distantNephew =
        direction == Direction::LEFT ? sibling->right : sibling->left;

    bool closeNephewIsBlack = closeNephew == nullptr || closeNephew->isBlack();
    bool distantNephewIsBlack =
        distantNephew == nullptr || distantNephew->isBlack();

    assert(sibling->isBlack());

    if (closeNephewIsBlack && distantNephewIsBlack) {
      if (node->parent->isRed()) {
        // clang-format off
        // Case 2: Sibling and nephews are BLACK, parent is RED
        //   Swap the color of P and S
        //      <P>             [P]
        //      / \             / \
        //    [N] [S]  ====>  [N] <S>
        //        / \             / \
        //      [C] [D]         [C] [D]
        // clang-format on
        sibling->color = Node::RED;
        node->parent->color = Node::BLACK;
        return;
      } else {
        // clang-format off
        // Case 3: Sibling, parent and nephews are all black
        //   Step 1. Paint S to RED
        //   Step 2. Recursively maintain P
        //      [P]             [P]
        //      / \             / \
        //    [N] [S]  ====>  [N] <S>
        //        / \             / \
        //      [C] [D]         [C] [D]
        // clang-format on
        sibling->color = Node::RED;
        maintainAfterRemove(node->parent);
        return;
      }
    } else {
      if (closeNephew != nullptr && closeNephew->isRed()) {
        // clang-format off
        // Case 4: Sibling is BLACK, close nephew is RED,
        //         distant nephew is BLACK
        //   Step 1. If N is a left child, right rotate P;
        //           If N is a right child, left rotate P.
        //   Step 2. Swap the color of close nephew and sibling
        //   Step 3. Goto case 5
        //                            {P}                {P}
        //      {P}                   / \                / \
        //      / \    r-rotate(S)  [N] <C>   repaint  [N] [C]
        //    [N] [S]  ==========>        \   ======>        \
        //        / \                     [S]                <S>
        //      <C> [D]                     \                  \
        //                                  [D]                [D]
        // clang-format on

        // Step 1
        rotateOppositeDirection(sibling, direction);
        // Step 2
        closeNephew->color = Node::BLACK;
        sibling->color = Node::RED;
        // Update sibling and nephews after rotation
        sibling = node->sibling();
        closeNephew =
            direction == Direction::LEFT ? sibling->left : sibling->right;
        distantNephew =
            direction == Direction::LEFT ? sibling->right : sibling->left;
        // Step 3: vvv
      }

      // clang-format off
      // Case 5: Sibling is BLACK, close nephew is BLACK,
      //         distant nephew is RED
      //      {P}                   [S]
      //      / \    l-rotate(P)    / \
      //    [N] [S]  ==========>  {P} <D>
      //        / \               / \
      //      [C] <D>           [N] [C]
      // clang-format on
      assert(closeNephew == nullptr || closeNephew->isBlack());
      assert(distantNephew->isRed());
      // Step 1
      rotateSameDirection(node->parent, direction);
      // Step 2
      sibling->color = node->parent->color;
      node->parent->color = Node::BLACK;
      if (distantNephew != nullptr) {
        distantNephew->color = Node::BLACK;
      }
      return;
    }
  }

  bool remove(NodePtr node, K key, NodeConsumer action) {
    assert(node != nullptr);

    if (key != node->key) {
      if (compare(key, node->key)) {
        /* key < node->key */
        NodePtr &left = node->left;
        if (left != nullptr && remove(left, key, action)) {
          maintainRelationship(node);
          return true;
        } else {
          return false;
        }
      } else {
        /* key > node->key */
        NodePtr &right = node->right;
        if (right != nullptr && remove(right, key, action)) {
          maintainRelationship(node);
          return true;
        } else {
          return false;
        }
      }
    }

    assert(key == node->key);
    action(node);

    if (this->size() == 1) {
      // Current node is the only node of the tree
      this->clear();
      return true;
    }

    if (node->left != nullptr && node->right != nullptr) {
      // clang-format off
      // Case 1: If the node is strictly internal
      //   Step 1. Find the successor S with the smallest key
      //           and its parent P on the right subtree.
      //   Step 2. Swap the data (key and value) of S and N,
      //           S is the node that will be deleted in place of N.
      //   Step 3. N = S, goto Case 2, 3
      //     |                    |
      //     N                    S
      //    / \                  / \
      //   L  ..   swap(N, S)   L  ..
      //       |   =========>       |
      //       P                    P
      //      / \                  / \
      //     S  ..                N  ..
      // clang-format on

      // Step 1
      NodePtr successor = node->right;
      NodePtr parent = node;
      while (successor->left != nullptr) {
        parent = successor;
        successor = parent->left;
      }
      // Step 2
      swapNode(node, successor);
      maintainRelationship(parent);
      // Step 3: vvv
    }

    if (node->isLeaf()) {
      // Current node must not be the root
      assert(node->parent != nullptr);

      // Case 2: Current node is a leaf
      //   Step 1. Unlink and remove it.
      //   Step 2. If N is BLACK, maintain N;
      //           If N is RED, do nothing.

      // The maintain operation won't change the node itself,
      //  so we can perform maintain operation before unlink the node.
      if (node->isBlack()) {
        maintainAfterRemove(node);
      }
      if (node->direction() == Direction::LEFT) {
        node->parent->left = nullptr;
      } else /* node->direction() == Direction::RIGHT */ {
        node->parent->right = nullptr;
      }
    } else /* !node->isLeaf() */ {
      assert(node->left == nullptr || node->right == nullptr);
      // Case 3: Current node has a single left or right child
      //   Step 1. Replace N with its child
      //   Step 2. If N is BLACK, maintain N
      NodePtr parent = node->parent;
      NodePtr replacement = (node->left != nullptr ? node->left : node->right);
      switch (node->direction()) {
        case Direction::ROOT:
          this->root = replacement;
          break;
        case Direction::LEFT:
          parent->left = replacement;
          break;
        case Direction::RIGHT:
          parent->right = replacement;
          break;
      }

      if (!node->isRoot()) {
        replacement->parent = parent;
      }

      if (node->isBlack()) {
        if (replacement->isRed()) {
          replacement->color = Node::BLACK;
        } else {
          maintainAfterRemove(replacement);
        }
      }
    }

    this->count -= 1;
    return true;
  }

  void inorderTraversal(NodeConsumer action) const {
    if (this->root == nullptr) {
      return;
    }

    std::stack<NodePtr> stack;
    NodePtr node = this->root;

    while (node != nullptr || !stack.empty()) {
      while (node != nullptr) {
        stack.push(node);
        node = node->left;
      }
      if (!stack.empty()) {
        node = stack.top();
        stack.pop();
        action(node);
        node = node->right;
      }
    }
  }
};

#endif  // RBTREE_MAP_HPP

其他資料

• Red-Black Tree - Wikipedia
• Red-Black Tree Visualization

---

1. https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Cormen2009-18 ↩

2. https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Mehlhorn2008-17 ↩

3. https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Algs4-16: 432–447 ↩

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：LeverImmy
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用