【高阶数据结构】红黑树详解

前言

在前面我们学习了平衡二叉树，但是二叉搜索树有其自身的缺陷，假如往树中插入的元素有序或者接近有序，二叉搜索树就会退化成单支树，时间复杂度会退化成O(N)，因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理，即采用平衡树来实现，除了AVL树，下面我们要学习的红黑树也是处理二叉树自身缺陷的一种方式

一、红黑树的概念

红黑树是一种二叉搜索树，它在每个结点上增加一个存储位表示结点的颜色，可以是红（Red）或黑（Black），通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树能够确保没有任何一条路径的长度会超出其他路径两倍可以（小于等于），所以是接近平衡的。

二、红黑树的性质

红黑树有几大性质，通过维持这些性质，来保证红黑树最长路径的节点个数不会超过最短路径节点个数的两倍。

1. 每个节点不是黑色就是红色的
2. 根节点是黑色的
3. 如果一个节点是红色的，它的两个孩子节点一定是黑的
   （即：没有连续的红色节点）
4. 对于每个节点，从该节点到其所有后代叶节点的所有路径上，均包含数量相同的黑色节点
   （即：每条路径都包含相同数量的黑色节点）
5. 每个叶子节点是黑色的（此处的叶子结点指的是空节点）

我们可以得出：
最长路径为一黑一红
最短路径为全黑

三、红黑树节点的定义

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

这里我们将默认节点（新增节点）给为红节点，因为红黑树中的每条路径中黑色节点的路径必须相同，如果我们给黑节点，必定违反性质，但如果给红节点还有“一线生机”。

四、红黑树的插入

红黑树是加了平衡限制的二叉搜索树，因此我们可以分两步来进行插入操作
1.先按二叉搜索树的插入规则插入

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
	}
private:
	Node* _root = nullptr;
};
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

2.检查一下插入新节点后有没有破坏红黑树的性质
我们的新增节点默认是红色
如果新增节点的双亲节点是黑色，则未违反红黑树性质，不需要调整；
如果新增节点的双亲节点是红的，则违反了红黑树的性质（不能有连续的红节点），此时我们需要分情况来调整

为了方便，我们假设cur为当前节点，parent为父节点，grandfather为爷爷节点，uncle为叔叔节点
在这些节点中，叔叔尤为重要，基本上是通过叔叔的状态来控制的

情况1：cur为红，parent为红，grandfather为黑，uncle为红

例如：
注：此处的数可能是一颗完整的树，也可能是一颗子树
我们的解决方法是：将parent，uncle改为黑，grandfather改为红，然后把grandfather当成cur，继续向上调整

如果grandfather是根节点的话，需要将grandfather变成黑色，因为红黑树的性质（根节点是黑色的）

如果grandfather是子树的话，给就会有父节点，且父节点为红色，然后就以grandfather为cur，继续向上调整

情况2： cur为红，parent为红，grandfather为黑，uncle不存在或者uncle存在且为黑

1.uncle不存在：这种情况稍微简单一点，如果uncle不存在，说明cur一定是新增节点，则cur和parent定有一个节点是黑色的，就违反了红黑树的性质（每条路径黑色节点个数相同）

2.uncle存在：如果uncle存在且为黑，那么cur原来就应该是黑的，至于为什么是红的，原因是cur的子树在调整过程中将cur的颜色变成了红色，换句话说，这种情况是一个中间态，是由其他情况调整而变来的

如果出现了上述情况，我们就需要进行旋转了
旋转的思路我在AVL树中有详细讲解，对旋转不熟悉的可以看看（https://blog.csdn.net/liuty0125/article/details/139563426?spm=1001.2014.3001.5502），下面我就只给出具体代码了

1.右单旋

parent为grandfather的左孩子，cur为parent的左孩子

if (parent == gradfather->_left)
{
	Node* uncle = gradfather->_right;	
	if (uncle && uncle->_col == RED)//情况1：叔叔存在且为红
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//右单旋
		if (cur == parent->_left)
		{
			RotateR(gradfather);
			parent->_col = BLACK;
			gradfather->_col = RED;
		}
		//左右双旋
		else
		{
			//......
		}
		break;
	}
}
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

2.左单旋

parent为grandfather的右孩子，cur为parent的右孩子

if (parent == gradfather->_left)
{
	//......
}
else
{
	Node* uncle = gradfather->_left;
	//情况1：叔叔存在且为红
	if (uncle && uncle->_col == RED)
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//左单旋
		if (cur == parent->_right)
		{
			RotateL(gradfather);
			parent->_col = BLACK;
			gradfather->_col = RED;
		}
		//右左双旋
		else
		{
			//......
		}
		break;
	}
}
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

3.左右单旋

parent为grandfather的左孩子，cur为parent的右孩子

if (parent == gradfather->_left)
{
	Node* uncle = gradfather->_right;	
	if (uncle && uncle->_col == RED)//情况1：叔叔存在且为红
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//右单旋
		if (cur == parent->_left)
		{
			//.......
		}
		//左右双旋
		else
		{
			RotateL(parent);
			RotateR(grandfather);
			cur->_col = BLACK;
			gradfather->_col = RED;
		}
		break;
	}
}
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

4.右左单旋

parent为grandfather的右孩子，cur为parent的左孩子

if (parent == gradfather->_left)
{
	//......
}
else
{
	Node* uncle = gradfather->_left;
	//情况1：叔叔存在且为红
	if (uncle && uncle->_col == RED)
	{
		//......
	}
	else//情况2：叔叔不存在或者叔叔存在且为黑
	{
		//左单旋
		if (cur == parent->_right)
		{
			//......
		}
		//右左双旋
		else
		{
			RotateR(parent);
			RotateL(grandfather);
			cur->_col = BLACK;
			gradfather->_col = RED;
		}
		break;
	}
}
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

五、红黑树与AVL树的比较

红黑树和AVL树都是性能十分不错的二叉搜索树，它们的增删查改的时间复杂度都是O(log_n)，

但是红黑树并不像AVL树一样追求绝对平衡，只需要保证最长路径不超过最短路径的两倍，所以相对的降低了插入和旋转的次数，因此在经常需要修改的结构中，红黑树的性能要比AVL树更佳，在实际中红黑树的运用更多。

六、完整代码

#pragma once

enum Colour
{
	RED,
	BLACK
};

template<class K,class V>
struct RBTreeNode
{
	RBTreeNode<K, V>* _left;
	RBTreeNode<K, V>* _right;
	RBTreeNode<K, V>* _parent;
	pair<K, V> _kv;
	Colour _col;

	RBTreeNode(const pair<K,V>& kv)
		:_left(nullptr)
		,_right(nullptr)
		,_parent(nullptr)
		,_kv(kv)
		,_col(RED)
	{}
};

template<class K,class V>
class RBTree
{
	typedef RBTreeNode<K, V> Node;
public:
	bool Insert(const pair<K, V>& kv)
	{
		if (_root == nullptr)
		{
			_root = new Node(kv);
			_root->_col = BLACK;
			return true;
		}
		Node* parent = nullptr;
		Node* cur = _root;
		while (cur)
		{
			if (cur->_kv.first < kv.first)
			{
				parent = cur;
				cur = cur->_right;
			}
			else if (cur->_kv.first > kv.first)
			{
				parent = cur;
				cur = cur->_left;
			}
			else
			{
				return false;
			}
		}
		cur = new Node(kv);
		if (parent->_kv.first < kv.first)
		{
			parent->_right = cur;
		}
		else
		{
			parent->_left = cur;
		}
		cur->_parent = parent;
		while (parent && parent->_col == RED)
		{
			Node* gradfather = parent->_parent;
			if (parent == gradfather->_left)
			{
				Node* uncle = gradfather->_right;	
				if (uncle && uncle->_col == RED)//情况1：叔叔存在且为红
				{
					parent->_col = uncle->_col = BLACK;
					gradfather->_col = RED;

					//继续往上处理
					cur = gradfather;
					parent = cur->_parent;
				}
				else//情况2：叔叔不存在或者叔叔存在且为黑
				{
					//右单旋
					if (cur == parent->_left)
					{
						RotateR(gradfather);
						parent->_col = BLACK;
						gradfather->_col = RED;
					}
					//左右双旋
					else
					{
						RotateL(parent);
						RotateR(grandfather);
						cur->_col = BLACK;
						gradfather->_col = RED;
					}
					break;
				}
			}
			else
			{
				Node* uncle = gradfather->_left;
				//情况1：叔叔存在且为红
				if (uncle && uncle->_col == RED)
				{
					parent->_col = uncle->_col = BLACK;
					gradfather->_col = RED;

					//继续往上处理
					cur = gradfather;
					parent = cur->_parent;
				}
				else//情况2：叔叔不存在或者叔叔存在且为黑
				{
					//左单旋
					if (cur == parent->_right)
					{
						RotateL(gradfather);
						parent->_col = BLACK;
						gradfather->_col = RED;
					}
					//右左双旋
					else
					{
						RotateR(parent);
						RotateL(grandfather);
						cur->_col = BLACK;
						gradfather->_col = RED;
					}
					break;
				}
			}
		}
		_root = BLACK;

		return true;
	}
	void RotateL(Node* parent)
	{
		Node* subR = parent->_right;
		Node* subRL = subR->_left;

		parent->_right = subRL;
		if (subRL)
			subRL->_parent = parent;

		subR->_left = parent;
		Node* ppnode = parent->_parent;
		parent->_parent = subR;

		if (parent == _root)
		{
			_root = subR;
			subR->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subR;
			}
			else
			{
				ppnode->_right = subR;
			}
			subR->_parent = ppnode;
		}
	}
	void RotateR(Node* parent)
	{
		Node* subL = parent->_left;
		Node* subLR = subL->_right;

		parent->_left = subLR;
		if (subLR)
			subLR->_parent = parent;

		subL->_right = parent;

		Node* ppnode = parent->_parent;
		parent->_parent = subL;

		if (parent == _root)
		{
			_root = subL;
			subL->_parent = nullptr;
		}
		else
		{
			if (ppnode->_left == parent)
			{
				ppnode->_left = subL;
			}
			else
			{
				ppnode->_right = subL;
			}
			subL->_parent = ppnode;
		}
	}
	void _InOrder(Node* root)
	{
		if (root == nullptr)
			return;

		_InOrder(root->_left);
		cout << root->_kv.first << endl;
		_InOrder(root->_right);
	}

	void InOrder()
	{
		_InOrder(_root);
	}
private:
	Node* _root = nullptr;
};
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
216
217
218
219
220
221