红黑树

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);}}
};