红黑树是一种自平衡的二叉搜索树。每个节点额外存储了一个 color 字段 ("RED" or "BLACK")，用于确保树在插入和删除时保持平衡。

## 性质

一棵合法的红黑树必须遵循以下四条性质：

1. 节点为红色或黑色
2. NIL 节点（空叶子节点）为黑色
3. 红色节点的子节点为黑色
4. 从根节点到 NIL 节点的每条路径上的黑色节点数量相同

下图为一棵合法的红黑树：


注：部分资料中还加入了第五条性质，即根节点必须为黑色，这条性质要求完成插入操作后若根节点为红色则将其染黑，但由于将根节点染黑的操作也可以延迟至删除操作时进行，因此，该条性质并非必须满足。（在本文给出的代码实现中就没有选择满足该性质）。为严谨起见，这里同时引用维基百科原文进行说明：

> Some authors, e.g. Cormen & al.,\[[18\]](https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Cormen2009-18) claim "the root is black" as fifth requirement; but not Mehlhorn & Sanders\[[17\]](https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Mehlhorn2008-17) or Sedgewick & Wayne.\[[16\]](https://en.wikipedia.org/wiki/Red–black_tree#cite_note-Algs4-16): 432–447  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` | 节点内储存的值 |

> 注：由于红黑树是由 B 树衍生而来（发明时的最初的名字 symmetric binary B-tree 足以证明这点），并非直接由平衡二叉树外加限制条件推导而来，插入操作的后续维护和删除操作的后续维护中部分对操作的解释作用仅是帮助理解，并不能将其作为该操作的原理推导和证明。