手撕红黑树——C++高阶数据结构详解

传统艺能😎

小编是双非本科大一菜鸟不赘述，欢迎各位指点江山（期待~）（QQ：1319365055）
此前博客点我！点我！请搜索博主 【知晓天空之蓝】

🎉🎉非科班转码社区诚邀您入驻🎉🎉
小伙伴们，打码路上一路向北，彼岸之前皆是疾苦
一个人的单打独斗不如一群人的砥砺前行
这是和梦想合伙人组建的社区，诚邀各位有志之士的加入！！
社区用户好文均加精（“标兵”文章字数2000+加精，“达人”文章字数1500+加精）
直达： 社区链接点我

---

---

红黑树是对树结构的一种高度综合运用，涉及到多叉树，树平衡调整，节点旋转等等，这些是对数据结构基本功的最佳历练，也是面试场上令人闻风丧胆的冷面一刀。能否给出完整的定义，能否介绍自己对红黑树的认识，能否通过旋转，染色等操作在给定的场景下对一颗红黑树进行调整使其符合定义…这些才是我们应该在学习后得到的信息

概念🤔

红黑树也是一种二叉搜索树，但是每个节点都存储了一个颜色，该颜色可以为黑可以为红，因此也叫红黑树。

红黑树和 AVL 树的区别就是红黑树属于近似平衡，他并不是完全平衡，红黑树不会像 AVL 树一样做到严密的平衡（高度差控制在 1 ），他是依靠每条路径上红黑节点的排布与限制，确保最长路径长度不超过最短路径长度的 2 倍.

五大特性🤔

红黑树有着标志性的五大特性：

1. 根节点一定为黑色
2. 一个节点只能是红或黑
3. 节点为红色，则该节点的两个子节点都为黑色
4. 对于每个节点，从根节点到叶子结点的简单路径上，黑色节点个数相等
5. 每个叶子结点（即空节点）都是黑色

那么问题来了，仅仅依靠这五大特性是如何确保最长路径长度 < 最短路径长度的 2 倍？

根据第 3,4 特性，我们不妨思考一下极端场景，最短可能路径其实就是全黑的情况，假设此时有 n 个节点，长度就为 n：

而最长可能路径就是在红色节点存在的条件下，以一红一黑的方式进行排列，此时假设依然有 n 个黑色节点，那么红色节点数目与黑色相同，则长度为 2n，以此证明。

节点定义🤔

这里和 AVL 树一样我们直接实现 KV 模型，为了方便后序的旋转操作，将红黑树的结点定义为三叉链结构，将 AVL 树中的平衡因子换成了新成员——结点的颜色。

因为节点颜色是贯穿的，我们可以直接定义成全局变量，并用枚举变量来给颜色赋予逻辑：

enum Color 
{
   Red, //0
   Black  //1
};
1
2
3
4
5

接下来就可以定义节点了：

template<class K，class V>
struct RBTreeNode
{
	RBTreeNode(const pair<K, V>& kv, Color color = Red)
		:_left(nullptr)
		, _right(nullptr)
		, _parent(nullptr)
		, _kv(kv)
		, _color(color)
	{}

	RBTreeNode<K，V>* _left;
	RBTreeNode<K,V>* _right;
	RBTreeNode<K,V>* _parent;//三叉链结构
	pair<K,V> _kv;//存储键值对
	Color _color;//节点颜色
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

注意这里有个细节：为什么构造结点时，默认将结点的颜色设置为红色？

因为我们要考虑插入场景，不论此时根节点为黑色还是红色，我们插入黑色节点，那么他一定会破坏性质 4 ，某条路径上的黑色节点一定会增加一个，那么为了维护结构，我们岂不是要给其他所有路径都加上一个黑色节点？但如果此时插入的是红色节点，如果根节点为红色，那么又会破坏性质 3 出现了连续的红色节点，但是如果根节点为黑色，就不需要进行调整。

这就是一个简单的伤害最小化理论：插入黑节点，一定会破坏性质 4，必须进行调整；插入红节点，可能破坏性质 3，可能进行调整，因此我们选择将插入节点定为红色。

红黑树插入🤔

插入逻辑依然和二叉搜索树差不多，三步走：

1. 按二叉搜索树的插入方法，找到待插入位置。
2. 将待插入结点插入到树中。
3. 若插入结点的父结点是红色的，则需要对红黑树进行调整。

插入的关键就在于这里的第三步，这调整里面有大学问。

插入调整🤔

我们给出一个基本模型（可以是一个完整的树，也可以是一个子树）：

并约定：

cur ：当前节点
p：parent，父节点
g：grandfather，祖父节点
u：uncle，叔叔节点
a，b，c，d，e：子树

顺便提一下，树的路径不是一路走到叶子结点算一条，要走到空节点（NIL 节点）算一条：

比如上图中该红黑树的有效路径不是 4 条而是 9 条。

情况一😎

cur 为红，p 为红，g 为黑， u 存在且为红

首先你需要知道，红黑树的调整关键看叔叔，因为节点的颜色是固定的，祖父存在且一定为黑，为什么？因为父节点为红色那么他一定不会是根，他一定有一个父节点且为黑，只有 u 节点不知道嘛情况。

我们调整并不是像 AVL 一样旋转，这里是进行变色，首先将叔叔变黑，此时就没有连续的红节点了，但是为了保持黑节点数目不变父亲也要变黑，万事大吉了吗？没有，紧接还要将祖父变红，为什么呀！？不要忘了，这里可能只是一个子树，叔叔父亲变黑了那么路径上黑节点就会多出一个，对整个结构必然有影响，所以还需要将祖父变红保持黑色数量不变。

最后不要忘了将祖父当成 cur 节点继续向上调整，因为在上一层父亲的颜色不知道，祖父改变可能违反规则还会继续调整。这种情况我们左右方向，翻转过来处理方法一样，只变色不旋转。

具体代码表示：

			while (parent != _pHead && parent->_color == Red)
			{
				Node* grandfather = parent->_parent;
				assert(grandfather);   //祖父节点有效性
				if (parent == grandfather->_left)
				{
					Node* uncle = grandfather->_right; //情况一叔叔在祖父右
					if (uncle && uncle->_color == Red) //叔叔在右且为红
					{
						parent->_color = Black;
						uncle->_color = Black; 
						grandfather->_color = Red; 
						cur = grandfather; //继续向上调整
						parent = cur->_parent;
					}
					else //叔叔为黑情况二
					{
                        ……
					}
				}
				else
				{
					Node* uncle = grandfather->_left;//左右翻转（叔叔在祖父左）不影响情况一，和上面一样处理
					if (uncle && uncle->_color == Red)
					{
						parent->_color = Black;
						uncle->_color = Black;
						grandfather->_color = Red;
						cur = grandfather;
						parent = cur->_parent;
					}
					else
					{
                        ……
					}
				}
			}
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

情况二😎

具体情况一🎉

cur 为红，p 为红，g 为黑， u 存在且为黑

其实这里的 a，b，c 的情况就只有 4 种情况，只要有一个黑节点就能满足：

这种情况的 cur 节点一定不是新插入节点，cur 原来是黑色，他是第一种情况向上调整过程中，祖父节点形成的 cur 节点，为什么呢？

如上图所示，根据性质 4 假设祖父上面有 x 个黑节点，那么左子树（含祖父）现在是 x +1 个，右子树（含祖父）是 x + 2 + y 个，很明显 x + 2 + y > x + 1，因此在插入结点前就已经不满足要求了，所以说叔叔结点存在且为黑这种情况，一定是由情况一往上调整过程中才会出现的！

此时单纯使用变色已经无法处理了，这时我们需要进行旋转处理。若祖孙三代的关系是直线（cur、parent、grandfather这三个结点为一条直线），则一波 AVL 树里经典的旋转又来辣！这里左偏所以选择右单旋，再进行颜色调整，颜色调整后这棵被旋转子树的根结点是黑色的，且黑节点数量不变，因此无需继续往上进行处理。

但是此时翻转就不能像情况一一样一概而论了，反转过来偏右就要使用左单旋了。因此红黑树抽象逻辑就强在这里，能和 AVL 树契合到位的同时还能有机调整，AVL 树要是天才的话那么红黑树我只能叫他一声 lord 。

具体情况二🎉

cur 为红，p 为红，g 为黑，u 不存在

在这种情况下的 cur 结点一定是新插入的结点，而不可能是由情况一变化而来的，因为叔叔不存在那么 parent 的下面也不可能再挂黑结点了。

既然产生了连续的红节点那就必须把其中一个变黑，总不能把插进去的红节点变黑吧，不然就变成插黑节点了，因此就在只能把 parent 变黑，但是这样子树就会多出黑节点有会破坏结构，怎么办呢？

和具体情况一同理了，祖孙三代在一条直线上偏左，一波右单旋安排，接着根节点变成 parent 后调整颜色，父亲变黑，祖父变红，一波完美升级后续也不需要再向上调整（黑节点数目不变，根节点颜色正常）。

具体情况三😎

该情况是具体情况一的区别版本，情况一是三世同堂即一条直线，这里是一条折线，他和情况二的区别就是情况二 p 在 g 的左，而 cur 是 p 的左 ，情况三 cur 在 p 的右：

那么不必多言，从 AVL 树过来的小伙伴一眼就明白该干什么了，没错，说白了就是单旋变双旋：

以上情况的完整如下：

pair<Node*, bool> Insert(const pair<K, V>& kv)
{
	if (_root == nullptr) //若红黑树为空树，则插入结点直接作为根结点
	{
		_root = new Node(kv);
		_root->_col = BLACK; //根结点必须是黑色
		return make_pair(_root, true); //插入成功
	}
	//找到待插入位置
	Node* cur = _root;
	Node* parent = nullptr;
	while (cur)
	{
		if (kv.first < cur->_kv.first)
		{
			//key值小于当前结点的走左子树
			parent = cur;
			cur = cur->_left;
		}
		else if (kv.first > cur->_kv.first)
		{
			//key值大于当前结点的走右子树
			parent = cur;
			cur = cur->_right;
		}
		else //待插入结点的key值=当前结点
		{
			return make_pair(cur, false); //插入失败
		}
	}

	//插入到树中
	cur = new Node(kv); //构造结点
	Node* newnode = cur; //记录新插入的结点（便于后序返回）
	if (kv.first < parent->_kv.first)
	{
		//新结点的key值小于parent插入到左边
		parent->_left = cur;
		cur->_parent = parent;
	}
	else
	{
		//新结点的key值大于parent插入到右边
		parent->_right = cur;
		cur->_parent = parent;
	}

	//若插入结点的父结点是红色的，则需要对红黑树进行调整
	while (parent&&parent->_col == RED)
	{
		Node* grandfather = parent->_parent; //parent是红色，则其父结点一定存在
		if (parent == grandfather->_left) //parent是grandfather的左孩子
		{
			Node* uncle = grandfather->_right; //uncle是grandfather的右孩子
			if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
			{
				//颜色调整
				parent->_col = uncle->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else //情况2+情况3：uncle不存在 + uncle存在且为黑
			{
				if (cur == parent->_left)
				{
					RotateR(grandfather); //右单旋

					//颜色调整
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				else //cur == parent->_right
				{
					RotateLR(grandfather); //左右双旋

					//颜色调整
					grandfather->_col = RED;
					cur->_col = BLACK;
				}
				break; 
			}
		}
		else //parent是grandfather的右孩子
		{
			Node* uncle = grandfather->_left; //uncle 是 grandfather 的左孩子
			if (uncle&&uncle->_col == RED) //情况1：uncle存在且为红
			{
				//颜色调整
				uncle->_col = parent->_col = BLACK;
				grandfather->_col = RED;

				//继续往上处理
				cur = grandfather;
				parent = cur->_parent;
			}
			else //uncle不存在/ uncle存在且为黑
			{
			    //         g
				//     p       u
				// cur
				if (cur == parent->_left)
				{
					RotateRL(grandfather); //右左双旋

					//颜色调整
					cur->_col = BLACK;
					grandfather->_col = RED;
				}
				//        g
				//    u       p
				//        cur
				else 
				{
					RotateL(grandfather); //左单旋

					//颜色调整
					grandfather->_col = RED;
					parent->_col = BLACK;
				}
				break; //子树旋转后，该子树的根变成了黑色，无需继续往上进行处理
			}
		}
	}
	_root->_col = BLACK; //暴力处理根节点颜色，防止向上处理根节点变红
	return make_pair(newnode, true);
}

//左单旋
void RotateL(Node* parent)
{
	Node* subR = parent->_right;
	Node* subRL = subR->_left;
	Node* parentParent = parent->_parent;

	//建立subRL与parent之间的联系
	parent->_right = subRL;
	if (subRL)
		subRL->_parent = parent;

	//建立parent与subR之间的联系
	subR->_left = parent;
	parent->_parent = subR;

	//建立subR与parentParent之间的联系
	if (parentParent == nullptr)
	{
		_root = subR;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subR;
		}
		else
		{
			parentParent->_right = subR;
		}
		subR->_parent = parentParent;
	}
}

//右单旋
void RotateR(Node* parent)
{
	Node* subL = parent->_left;
	Node* subLR = subL->_right;
	Node* parentParent = parent->_parent;

	//建立subLR与parent之间的联系
	parent->_left = subLR;
	if (subLR)
		subLR->_parent = parent;

	//建立parent与subL之间的联系
	subL->_right = parent;
	parent->_parent = subL;

	//建立subL与parentParent之间的联系
	if (parentParent == nullptr)
	{
		_root = subL;
		_root->_parent = nullptr;
	}
	else
	{
		if (parent == parentParent->_left)
		{
			parentParent->_left = subL;
		}
		else
		{
			parentParent->_right = subL;
		}
		subL->_parent = parentParent;
	}
}

//左右双旋
void RotateLR(Node* parent)
{
	RotateL(parent->_left);
	RotateR(parent);
}

//右左双旋
void RotateRL(Node* parent)
{
	RotateR(parent->_right);
	RotateL(parent);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215

（对旋转有疑惑的小伙伴请走传送门：手撕 AVL 树）

注意，最后根节点我们暴力处理颜色设为黑色，防止向上调整时将根节点变为了红色的情况。

验证红黑树🤔

还是老套路，先来一手中序遍历看这棵树是否满足二叉搜索树性质：

void Inorder()
{
	_Inorder(_root);
}

void _Inorder(Node* root)
{
	if (root == nullptr)//空树也是红黑树
		return;
	_Inorder(root->_left);
	cout << root->_kv.first << " ";
	_Inorder(root->_right);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

然后要验证红黑树的整体结构，灵魂就在于是否满足五大特性：

	Node* GetRoot()//取根节点函数
	{
		return _pHead->_parent;
	}
	
	bool IsValidRBTRee()
	{
		Node* pRoot = GetRoot();//取根节点
		if (pRoot == nullptr)//空树也是红黑树
			return true;
		if (pRoot->_color != Black)
		{
			cout << "违反性质一：根节点是黑色" << endl;
			return false;
		}
		size_t count = 0;
		Node* cur = pRoot;
		while (cur)//取最左路径的黑节点个数为验证标准
		{
			if (cur->_color == Black)
				count++;
			cur = cur->_left;
		}
		size_t pathB = 0;//记录需验证路径的黑节点个数
		return _IsValidRBTRee(pRoot, count, pathB);//封装函数进行递归验证
	}
		
		bool  _IsValidRBTRee(Node* pRoot, size_t count, size_t pathB)
		{
			if (pRoot == nullptr)
				return true;
			if (pRoot->_color == Black)
				pathB++;
			Node* parent = pRoot->_parent;//遇到红节点检查其父亲（红节点一定存在父亲）
				if (parent->_color == Red && parent != _pHead && pRoot->_color == Red)
				{
					cout << "违反性质3：不能存在连在一起的红色节点" << endl;
					return false;
				}
			if (pRoot->_left == nullptr && pRoot->_right == nullptr)
			{
				if (pathB != count)
				{
					cout << "违反性质4：每条路径中黑色节点个数均相同" << endl;
					return false;
				}
			}
			return _IsValidRBTRee(pRoot->_left, count, pathB) && _IsValidRBTRee(pRoot->_right, count, pathB);
		}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

红黑树查找🤔

红黑树的查找函数与二叉搜索树的查找方式一模一样，四步走：

若树为空树，则查找失败，返回nullptr。
若key值小于当前结点的值，则应该在该结点的左子树当中进行查找。
若key值大于当前结点的值，则应该在该结点的右子树当中进行查找。
若key值等于当前结点的值，则查找成功，返回对应结点。

Node* Find(const K& key)
{
	Node* cur = _root;
	while (cur)
	{
		if (key < cur->_kv.first) 
		{
			cur = cur->_left; 
		}
		else if (key > cur->_kv.first) 
		{
			cur = cur->_right; 
		}
		else
		{
			return cur;
		}
	}
	return nullptr;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

红黑树的删除🤔

还是在 AVL 树说的，高阶数据结构概不展示删除部分，过于打脑壳有兴趣的自行查阅即可。

谁是一代宗师🤔

AVL 树和红黑树都是平衡二叉树的两个老大哥，他们增删查改的时间复杂度都是 O(logN)，到底谁更技高一筹？

其实在大数据的场景下，比如百万级量化数据，AVL 需要构建大约 20 多层，同时红黑树需要构建大约 40 多层，毕竟红黑树是近似平衡的二叉搜索树。

但是我们知道 20 和 40 在 CPU 运算速度面前并没有什么差别，虽然 AVL 树在效率上会略胜红黑树一点点，但是生活中红黑树的运用却比 AVL 树更为广泛，因为 AVL 树的效率是有代价的，是充分牺牲结构进行不断旋转得到的，而红黑树大大降低了旋转次数会更安全因此，换来了更优的性能

aqa 芭蕾 eqe 亏内，代表着开心代表着快乐，ok 了家人们。