定义
红黑树是一种自平衡二叉搜索树(BST)，通过节点颜色约束保持近似平衡。
为什么需要红黑树
我们需要一种动态维护有序数据的结构，能高效地：
- 插入、删除、查找（O(log n)）
- 保持有序性（方便范围查询、前驱/后继操作）
但普通的数据结构各有缺陷：
| 结构 | 查找 | 插入 | 删除 | 是否有序 |
|---|---|---|---|---|
| 数组（有序） | O(log n) | O(n) | O(n) | √ |
| 链表 | O(n) | O(1) | O(1) | × |
| 哈希表 | O(1) | O(1) | O(1) | × |
| 二叉搜索树 | O(h) | O(h) | O(h) | √ |
其中 h 是树高。若树高接近 log₂n，BST 十分高效；但若插入有序序列，树会退化为链表，性能降为 O(n)。所以还需要一种能自动保持平衡的 BST。
从BST到平衡树
为解决树高失衡问题，出现了各种平衡二叉搜索树：
| 树种类 | 平衡标准 | 调整方式 | 特点 |
|---|---|---|---|
| AVL树 | 左右子树高度差 ≤ 1 | 严格旋转 | 查找快，插删慢 |
| 红黑树 | 路径黑高平衡 | 旋转 + 染色 | 插删快，工程应用广 |
| Treap | 随机优先级 | 随机旋转 | 实现简单 |
| Splay树 | 自调整 | 访问后旋转到根 | 适合频繁访问同节点场景 |
在工程实践中（如 STL map, set），插入与删除操作频繁，AVL 太严格，Treap 太随机，于是选用了红黑树（Red-Black Tree）—— 一种在效率与复杂度之间折衷的平衡树。
红黑树的核心思想
红黑树不追求“绝对平衡”，而是通过给每个节点增加一个“颜色位”（红或黑），并维护一组颜色约束规则，在插入或删除时执行：
- 局部旋转
- 颜色翻转
从而保证整棵树不会严重倾斜，保持“近似平衡”—— 任何从根到叶子的路径长度至多相差一倍。
红黑树是 4 阶 B 树（2-3-4 树）的变体，待确认
性质
红黑树首先是一颗二叉搜索树，对于任意节点，其左子树上所有节点的键值均小于该节点的键值，其右子树上所有节点的键值均大于该节点的键值。
其次还必须遵循以下四条性质：
- 每个节点为红色或黑色
- NIL 节点（空叶子节点）为黑色；根节点为黑色（可以延迟至删除操作时进行修正，所以也并非需要严格满足）
- 红色节点的子节点为黑色
- 从任一节点出发，到其所有叶子节点的路径上，黑色节点数目（黑高）相同
1# 设红黑树的黑高为 bh，最坏情况下，红节点与黑节点交替排列。则
2h ≤ 2 * bh
3# 又根据黑高性质，至少有
4n ≥ 2^bh - 1
5# 可得
6h ≤ 2 * log₂(n + 1)这说明，红黑树的高度至多是理想平衡树的两倍。因此查找、插入、删除操作都能保证 O(log n)。
原理
红黑树通过强制执行上述性质来确保树的平衡性。插入和删除节点时，可能会违反这些性质，因此需要进行修正操作（旋转和重新着色）以恢复红黑树的合法性。
旋转
红黑树的平衡维护依赖于两种局部结构变换：左旋（Left Rotate） 与 右旋（Right Rotate），这与AVL树中的旋转类似。旋转本身不直接修复红黑性质，但在修复算法中用于：
把“红红冲突”节点上移（插入修复）； 调整“黑高不平衡”的分布（删除修复）。
它们在保持中序遍历顺序（BST 性质不变）的前提下，调整节点之间的相对高度。
插入
插入规则
- 新节点初始颜色：红色（保证不会破坏黑高平衡）。
- 插入位置：BST 搜索到的叶子位置。
- 插入后可能违背的性质：
- 性质 2（根黑性）
- 性质 3（红节点不能相邻）
插入修复目标
修复过程要恢复四条红黑性质，主要解决：
- 红红冲突：新节点 z 与其父节点 p 都是红色。
- 可能引起的局部不平衡：通过旋转 + 染色恢复。
插入的新节点初始颜色为红色，如果新节点的父节点是红色，违反性质3，此时需要将其中的一个节点变为黑色，但是当前子树的黑色节点数量增加，需要。
根据叔节点的颜色，可以通过重新着色或旋转来恢复平衡。
-
如果叔叔节点是红色，则将父节点和叔叔节点重新着色为黑色，祖父节点重新着色为红色，然后将当前节点指向祖父节点，继续检查。
-
如果叔叔节点是黑色，则根据当前节点的位置进行旋转操作，以确保红黑树的性质得到维护。
删除
删除时，如果删除的节点是黑色，可能会导致路径上的黑色节点数量不平衡。通过一系列的旋转和重新着色操作，可以恢复红黑树的性质。
如果兄弟节点为红色，则通过旋转将其变为黑色，并将父节点变为红色。
如果兄弟节点为黑色且其子节点也为黑色，则将兄弟节点变为红色，并将当前节点指向父节点，继续检查。
如果兄弟节点为黑色且至少有一个子节点为红色，则通过旋转和重新着色来恢复平衡。
实现
1template<typename Key, typename Value = Key>
2class RBTree {
3public:
4 RBTree(const RBTree&) = delete;
5 RBTree& operator=(const RBTree&) = delete;
6 RBTree() :
7 root(nullptr), nil(nullptr), cnt(0)
8 {
9 nil = new Node();
10 nil->c = BLACK;
11 nil->l = nil->r = nil->p = nil;
12 root = nil;
13 }
14 ~RBTree()
15 {
16 clear_node(root);
17 delete nil;
18 }
19
20 void insert(const Key& k, const Value& v = Value())
21 {
22 Node* parent = nil;
23 for (Node* cur = root; cur != nil;) {
24 parent = cur;
25 if (k == cur->key) {
26 cur->val = v;
27 return;
28 }
29 cur = (k < cur->key) ? cur->l : cur->r;
30 }
31 Node* node = new Node(k, v);
32 node->l = node->r = nil;
33 node->p = parent;
34 if (parent == nil)
35 root = node;
36 else
37 ((k < parent->key) ? parent->l : parent->r) = node;
38 ++cnt;
39 insert_fixup(node);
40 }
41
42 bool erase(const Key& k)
43 {
44 Node* node = find_node(k);
45 if (node == nil) return false;
46 Node* repl = node;
47 Color repl_original_c = repl->c;
48 Node* cur;
49 if (node->l == nil) {
50 cur = node->r;
51 transplant(node, node->r);
52 }
53 else if (node->r == nil) {
54 cur = node->l;
55 transplant(node, node->l);
56 }
57 else {
58 repl = minimum(node->r);
59 repl_original_c = repl->c;
60 cur = repl->r;
61 if (repl->p == node) {
62 cur->p = repl; // 如果是nil也更新父节点
63 }
64 else {
65 transplant(repl, repl->r);
66 repl->r = node->r;
67 repl->r->p = repl;
68 }
69 transplant(node, repl);
70 repl->l = node->l;
71 repl->l->p = repl;
72 repl->c = node->c;
73 }
74 delete node;
75 --cnt;
76 if (repl_original_c == BLACK) erase_fixup(cur);
77 return true;
78 }
79
80 bool empty() const { return root == nil; }
81 size_t size() const { return cnt; }
82 bool contains(const Key& k) const { return find_node(k) != nil; }
83 Value* get(const Key& k)
84 {
85 Node* n = find_node(k);
86 return n != nil ? &n->val : nullptr;
87 }
88
89private:
90 enum Color { RED, BLACK };
91 struct Node {
92 Key key;
93 Value val;
94 Node *l, *r, *p;
95 Color c;
96 Node(const Node&) = delete;
97 Node& operator=(const Node&) = delete;
98 Node(const Key& k = {}, const Value& v = Value {}, Color col = RED) :
99 key(k), val(v), l(nullptr), r(nullptr), p(nullptr), c(col) {}
100 auto right_child() const -> bool { return this == p->r; }
101 };
102 Node *root, *nil;
103 size_t cnt = 0;
104
105 void rotate_left(Node* parent)
106 {
107 Node* succ = parent->r;
108 parent->r = succ->l;
109 if (succ->l != nil) succ->l->p = parent;
110 succ->p = parent->p;
111 if (parent->p == nil) root = succ;
112 else if (parent == parent->p->l) parent->p->l = succ;
113 else parent->p->r = succ;
114 succ->l = parent;
115 parent->p = succ;
116 }
117
118 void rotate_right(Node* parent)
119 {
120 Node* succ = parent->l;
121 parent->l = succ->r;
122 if (succ->r != nil) succ->r->p = parent;
123 succ->p = parent->p;
124 if (parent->p == nil) root = succ;
125 else if (parent == parent->p->r) parent->p->r = succ;
126 else parent->p->l = succ;
127 succ->r = parent;
128 parent->p = succ;
129 }
130
131 void insert_fixup(Node* cur)
132 {
133 while (cur->p->c == RED) {
134 if (cur->p == cur->p->p->l) {
135 Node* uncle = cur->p->p->r;
136 if (uncle->c == RED) {
137 cur->p->c = uncle->c = BLACK;
138 cur->p->p->c = RED; // 叔父爷颜色取反
139 cur = cur->p->p; // 继续考虑爷节点
140 }
141 else {
142 /* [3] [3] [2]
143 * / / / \
144 * 1 -> 2 -> 1 3
145 * \ /
146 * *2 *1
147 */
148 if (cur == cur->p->r) {
149 cur = cur->p;
150 rotate_left(cur);
151 }
152 cur->p->c = BLACK;
153 cur->p->p->c = RED;
154 rotate_right(cur->p->p);
155 }
156 }
157 else {
158 Node* uncle = cur->p->p->l;
159 if (uncle->c == RED) {
160 cur->p->c = uncle->c = BLACK;
161 cur->p->p->c = RED;
162 cur = cur->p->p;
163 }
164 else {
165 if (cur == cur->p->l) {
166 cur = cur->p;
167 rotate_right(cur);
168 }
169 cur->p->c = BLACK;
170 cur->p->p->c = RED;
171 rotate_left(cur->p->p);
172 }
173 }
174 }
175 root->c = BLACK;
176 }
177
178 Node* find_node(const Key& k) const
179 {
180 Node* cur = root;
181 while (cur != nil && cur->key != k) {
182 cur = (k < cur->key) ? cur->l : cur->r;
183 }
184 return cur;
185 }
186
187 void transplant(Node* u, Node* v)
188 {
189 if (u->p == nil)
190 root = v;
191 else
192 ((u == u->p->l) ? u->p->l : u->p->r) = v;
193 v->p = u->p;
194 }
195
196 Node* minimum(Node* cur) const
197 {
198 while (cur->l != nil)
199 cur = cur->l;
200 return cur;
201 }
202
203 void erase_fixup(Node* cur)
204 {
205 while (cur != root && cur->c == BLACK) {
206 if (cur == cur->p->l) {
207 Node* sib = cur->p->r;
208 /*
209 * [2] [4]
210 * / \ / \
211 * *[n] 4 -> 2 [5]
212 * / \ / \
213 * [3] [5] *[n] [3]
214 */
215 if (sib->c == RED) {
216 sib->c = BLACK;
217 cur->p->c = RED;
218 rotate_left(cur->p);
219 sib = cur->p->r;
220 }
221 /* [4] [4]
222 * / \ / \
223 * 2 [5] -> *2 [5]
224 * / \ \
225 * *[n] [3] 3
226 */
227 if (sib->l->c == BLACK && sib->r->c == BLACK) {
228 sib->c = RED;
229 cur = cur->p;
230 }
231 else {
232 /* 2 2
233 * / \ / \
234 * *[n] [4] -> *[n] [3]
235 * / \
236 * 3 4
237 */
238 if (sib->r->c == BLACK) {
239 sib->l->c = BLACK;
240 sib->c = RED;
241 rotate_right(sib);
242 sib = cur->p->r;
243 }
244 /* 2 *3
245 * / \ / \
246 * *[n] [3] -> [2] [4]
247 * \
248 * 4
249 */
250 sib->c = cur->p->c;
251 cur->p->c = BLACK;
252 sib->r->c = BLACK;
253 rotate_left(cur->p);
254 cur = root;
255 }
256 }
257 else {
258 Node* sib = cur->p->l;
259 if (sib->c == RED) {
260 sib->c = BLACK;
261 cur->p->c = RED;
262 rotate_right(cur->p);
263 sib = cur->p->l;
264 }
265 if (sib->r->c == BLACK && sib->l->c == BLACK) {
266 sib->c = RED;
267 cur = cur->p;
268 }
269 else {
270 if (sib->l->c == BLACK) {
271 sib->r->c = BLACK;
272 sib->c = RED;
273 rotate_left(sib);
274 sib = cur->p->l;
275 }
276 sib->c = cur->p->c;
277 cur->p->c = BLACK;
278 sib->l->c = BLACK;
279 rotate_right(cur->p);
280 cur = root;
281 }
282 }
283 }
284 cur->c = BLACK;
285 }
286
287 void clear_node(Node* cur)
288 {
289 if (cur == nil) return;
290 clear_node(cur->l);
291 clear_node(cur->r);
292 delete cur;
293 }
294};