紅黑樹

1 基本概念

1.1 定義

紅黑樹首先是二叉搜索樹（左<根<右）；
基本性質：

1. 結點非紅即黑；
2. 根/葉子都是黑；
3. 任意節點向下的所有路徑上存在黑結點數量一致；
4. 紅結點下不能直連紅結點；

1.2 基本特性推理

• 最長路徑不超過最短路徑的兩倍；

1.3 對比

與AVL樹對比：

	AVL	RB
高度	任一結點左右子樹的高度差絕對值不超過1	任一結點左右子樹的高度差不超過兩倍
查詢效率（相對）	稍高 O(lg n)	稍低 O(lg n)
插入/刪除效率（相對）	低	高

1.4 延伸

1.4.1 簡單判別是否是紅黑樹

• 答案：否
  • 如果添加NIL結點，發現某一結點下路徑的黑結點數量并不相同

1.4.2 應用

• c++ stl中的map/set 是基于紅黑樹實現的

2 插入

2.1 插入結點默認紅色

• 如果默認黑色，首先就會破壞黑高同原則，調整相對比較麻煩；
• 默認紅色，可能破壞不紅紅原則或根為黑原則，調整相對容易；

2.2 插入結點

如果紅黑樹性質被破壞，分三種情況調整：

2.2.1 插入結點是根結點

• 違反根為黑原則
• 調整方案：直接變黑

2.2.2 插入結點的叔叔是紅色

示例1：插入結點1

調整方案：

• father 和 uncle 變紅，grandpather 變黑
• grandfather變為插入結點，繼續判斷是否違反原則

2.2.3 插入結點的叔叔是黑色

示例：插入結點1

該情況下，uncle可能直觀上不存在，但是紅黑樹默認有NIL結點，是黑的

調整方案：

• 根據不同場景（LL/LR/RR/RL）進行旋轉，然后變色

場景分析

LL型

step 1：基于grandfather右旋

step 2：變色

RR型

step 1：基于grandfather進行左旋

step 2：變色

LR型

調整方案：

RL型

調整方案：

3 構建

按照二叉搜索樹規則，依次插入結點，并根據插入規則進行調整

4 示例代碼

根據算法導論偽代碼實現：

#pragma once#include <iostream>
#include <functional>enum Color {RED, BLACK};struct RBNode {int key;Color color;RBNode *left;RBNode *right;RBNode *parent;
};class RBTree {
private:RBNode *root;RBNode *NIL;void LeftRotate(RBNode *x) {RBNode *y = x->right;x->right = y->left;if (x->right != NIL) {x->right->parent = x;}y->parent = x->parent;if (x->parent == NIL) {root = y;} else if (x == x->parent->left) {x->parent->left = y;} else {x->parent->right = y;}x->parent = y;y->left = x;}void RightRotate(RBNode *y) {RBNode *x = y->left;y->left = x->right;if (y->left != NIL) {y->left->parent = y;}x->parent = y->parent;if (y->parent == NIL) {root = x;} else if (y->parent->left = y) {y->parent->left = x;} else {y->parent->right = x;}y->parent = x;x->right = y;}void InsertFixup(RBNode *z) {while (z->parent->color == RED) {if (z->parent == z->parent->parent->left) {RBNode *y = z->parent->parent->right;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->right) {z = z->parent;LeftRotate(z);}z->parent->color = BLACK;z->parent->parent->color = RED;RightRotate(z->parent->parent);}} else {RBNode *y = z->parent->parent->left;if (y->color == RED) {z->parent->color = BLACK;y->color = BLACK;z->parent->parent->color = RED;z = z->parent->parent;} else {if (z == z->parent->left) {z = z->parent;RightRotate(z);}z->parent->color = BLACK;z->parent->parent->color = RED;LeftRotate(z->parent->parent);}}}root->color = BLACK;}void Transplant(RBNode *u, RBNode *v) {if (u->parent == NIL) {root = v;} else if (u == u->parent->left) {u->parent->left = v;} else {u->parent->right = v;}v->parent = u->parent; // if v is nullptr or NIL}void DeleteFixup(RBNode *x) {while (x != root && x->color == BLACK) {if (x == x->parent->left) {RBNode *w = x->parent->right;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;LeftRotate(x->parent);w = x->parent->right;}if (w->left->color == BLACK && w->right->color == BLACK) {w->color = RED;x = x->parent;} else {if (w->right->color == BLACK) {w->left->color = BLACK;w->color = RED;RightRotate(w);w = x->parent->right;}w->color = x->parent->color;x->parent->color = BLACK;w->right->color = BLACK;LeftRotate(x->parent);x = root;}} else {RBNode *w = x->parent->left;if (w->color == RED) {w->color = BLACK;x->parent->color = RED;RightRotate(x->parent);w = x->parent->left;}if (w->right->color == BLACK && w->left->color == BLACK) {w->color = RED;x = x->parent;} else {if (w->left->color == BLACK) {w->right->color = BLACK;w->color = RED;LeftRotate(w);w = x->parent->left;}w->color = x->parent->color;x->parent->color = BLACK;w->left->color = BLACK;RightRotate(x->parent);x = root;}}}x->color = BLACK;}RBNode* Minimum(RBNode *node) {while (node->left != NIL) {node = node->left;}return node;}public:RBTree() {NIL = new RBNode{0, BLACK, nullptr, nullptr, nullptr};root = NIL;}~RBTree() {std::function<void(RBNode *)> deleteNode = [&](RBNode *node) {if (node != NIL) {deleteNode(node->left);deleteNode(node->right);delete node;}};deleteNode(root);delete NIL;}void Insert(int key) {RBNode *z = new RBNode{key, RED, NIL, NIL};RBNode *y = NIL;RBNode *x = root;while (x != NIL) {y = x;if (z->key < x->key) {x = x->left;} else {x = x->right;}}z->parent = y;if (y == NIL) {root = z;} else if (z->key < y->key) {y->left = z;} else {y->right = z;}InsertFixup(z);}void Remove(int key) {RBNode *z = root;while (z != NIL && z->key != key) {if (key < z->key) {z = z->left;} else {z = z->right;}}if (z == NIL) {return;}RBNode *y = z;RBNode *x;Color yOriColor = y->color;if (z->left == NIL) {x = z->right;Transplant(z, z->right);} else if (z->right == NIL) {x = z->left;Transplant(z, z->left);} else {y = Minimum(z->right);yOriColor = y->color;x = y->right;if (y->parent == z) {x->parent = y;} else {Transplant(y, y->right);y->right = z->right;y->right->parent = y;}Transplant(z, y);y->left = z->left;y->left->parent = y;y->color = z->color;}delete z;if (yOriColor == BLACK) {DeleteFixup(x);}}void Inorder() {InorderHelper(root);std::cout << std::endl;}void InorderHelper(RBNode* node) {if (node != NIL) {InorderHelper(node->left);std::cout << node->key << " (" << (node->color == RED ? "R)" : "B)") << " ";InorderHelper(node->right);}}
};