目录

回顾

情况

假如父亲在爷爷的左节点上，插入的节点在父亲的右节点

打脸.jpg

 如果有叔叔节点

假如父亲在爷爷的右节点上

插入的节点在父亲的右节点

 插入的节点在父亲的左节点

对于上一章所讲的新节点最好不要变（阿巴阿巴…）

小技巧

代码实现

左旋节点

先左旋后右旋

先右旋再左旋

分类

总代码

总结

回顾

上期的博客

c++红黑树（3/4）_木木em哈哈的博客-CSDN博客https://blog.csdn.net/mumuemhaha/article/details/131191005?spm=1001.2014.3001.5501

在上一期的博客中我们学到了第二种情况红黑树如何进行平衡性调整

接下来我们要试试剩下的情况，红黑树如何进行平衡性调整

其实说是这一章一共三种情况，但是如果理解了前面两章，其实要比前两章简单的多得多

情况

假如父亲在爷爷的左节点上，插入的节点在父亲的右节点

（往下的情况默认没叔叔节点或者叔叔节点为黑）

做法很简单——只需要先做左旋再右旋

这样节点就行了

接下来就是变色了

打脸.jpg

emmm…

上一章好像讲过新节点最好不要变色来着…

这个我后面会解释

如果有叔叔节点

就是这样变

类似就是加了一个叔叔节点的变化

假如父亲在爷爷的右节点上

这时只需要左右反过来就行了，会更好理解

插入的节点在父亲的右节点

此时只需要与之相反的左旋就行了

如果有叔叔节点就是

插入的节点在父亲的左节点

这个只需要与之相反的先做右旋在做左旋

然后老样子

如果有叔叔节点就是其实

这样所有的就完成了

对于上一章所讲的新节点最好不要变（阿巴阿巴…）

这是因为一个特殊情况必须要把新节点当成一个整体

但是，仔细看

无论如何变交换的时候只要把30这个节点交换就行了

其他的不用变，自然而然，新节点就可以变色

小技巧

左旋右旋只需要判断是左节点向下"拉"还是右节点向下"拉"

代码实现

其实这里没有什么好说的，左旋只是相反的右旋，只需要把所有的方向一变就行

左旋节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void RotateLeft(RBNode<T>*& pointer)
{
	//     4      -----左旋----             6
	//  /      \                         /     \
	// 3        6                     4         7
	//         /   \                 /  \
	//        5     7              3     5   
	RBNode<T>* node_1 = pointer;
	pointer = pointer->rchild;
	pointer->parent = node_1->parent;
	node_1->rchild = pointer->lchild;
	if (pointer->lchild)
		pointer->lchild->parent = node_1;
	pointer->lchild = node_1;
	node_1->parent = pointer;

}

先左旋后右旋

这里附上先左旋在右旋的节点

//如下图不全，只是示意，不要按照这个图写代码否则会造成代码出现bug
        //      6     -----先左旋----    6       -----再右旋----    5
        //   /      \                   /   \                      /    \
        //  4        7                 5     7                    4      6 
        //    \                       /                                    \
        //     5                     4                                      7

代码就为

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void RotateLeftRight(RBNode<T>*& pointer)
{
	//如下图不全，只是示意，不要按照这个图写代码否则会造成代码出现bug
	//      6      -----先左旋----    6       -----再右旋----    5
	//   /      \                   /   \                      /    \
	//  4        7                 5     7                    4      6 
	//    \                       /                                    \
	//     5                     4                                      7
	RBNode<T>* noderoot = pointer;
	RBNode<T>* noderoot_left = pointer->lchild;
	RBNode<T>* noderoot_right = pointer->rchild;
	RotateLeft(noderoot_left);
	pointer->lchild = noderoot;
	RotateRight(noderoot_right);
}

先右旋再左旋

理解了先左后右，那这个也会十分好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//先右后左
void RotateRightLeft(RBNode<T>*& pointer)
{
	//      6     -----先右旋----     6       -----再左旋----     7
	//   /     \                   /     \                      /    \
	//  4        8                4       7                    6      8 
	//          /                           \                 /                   
	//         7                             8               4      
	RBNode<T>* noderoot = pointer;
	RBNode<T>* noderoot_left = pointer->lchild;
	RBNode<T>* noderoot_right = pointer->rchild;
	RotateRight(noderoot_right);
	pointer->rchild = noderoot;
	RotateLeft(noderoot_left);
}

分类

函数打好了，现在只需要分类把情况一填

把颜色一变就行了

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
if (parent->parent->lchild==parent)
{
	//插入数据是父亲的左节点
	if (parent->lchild = point)
	{
		RotateRight(grandpa);
		grandpa->colour = BLACK;
		grandpa->rchild->colour = RED;
	}
	//插入数据是父亲的右节点
	else
	{
		RotateLeftRight(grandpa);
		grandpa->lchild = RED;
	}
}
else
{
	if (parent->lchild = point)
	{
		Rotateleft(grandpa);
		grandpa->colour = BLACK;
		grandpa->lchild->colour = RED;
	}
	//插入数据是父亲的右节点
	else
	{
		RotateRightLeft(grandpa);
		grandpa->lchild = RED;
	}
}

总代码

最后附上最后的总代码（未插入数据，自己编写就行）

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
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
#include <iostream>
using namespace std;
//定义一个颜色
enum Colour
{
	RED,
	BLACK,
};
//定义一个模版T
template<typename T>
//一个节点的结构体
struct RBNode
{
	RBNode* lchild,
		* rchild,
		* parent;
	T	data;
	//初始化为RED也可以后面定义一个初始化函数
	Colour colour=RED;
};
//再定义一个模版T（template只能联系到下面一句语句）
template <typename T>
class RBTree//树
{
public:
	RBTree()
	{
		root = nullptr;
	}
	~RBTree()
	{
		ReleaseNode(root);
	}
	//插入元素
	void InsNode(const T& e)
	{
		InsNode(root, e);
	}
	void InsNode(RBNode<T>*& tnode, const T& e)
	{
		RBNode<T>* point = tnode;
		RBNode<T>* parent = nullptr;
		//深入到叶子节点准备插入新数据
		while (point->data==nullptr)
		{
			if (e == point->data)
			{
				printf("该数据已经存在");
				return;
			}
			parent = point;
			if (e >= point)
				point = point->rchild;
			else
				point = point->lchild;

		}
		//准备插入数据
		point = new RBNode<T>;
		point->data = e;
		point->lchild = nullptr;
		point->rchild = nullptr;
		point->parent = nullptr;
		point->colour = RED;
		
		if (parent == nullptr)
		{
			//插入的是根节点
			point->colour = BLACK;
			tnode = point;
		}
		//不是根节点
		if (e > parent->data)
			parent->rchild = point; 
		else
			parent->lchild = point;

		point->parent = parent;
		if (parent->colour == BLACK)
		{
			count << e << "插入完成" << endl;
			return;
		}
		//接下来就是插入地方的父亲节点是红色的，且深度至少为3（因为第二层父亲节点颜色一定为黑色
		RBNode<T>* uncle = nullptr;
		RBNode<T>* grandpa = nullptr;
		//开始整个平衡性调整
		while (true)
		{
			uncle = (parent->parent != nullptr) ? (getuncle(parent) :nullptr);
			grandpa = point->parent->parent;
			if grandpa == nullptr
				break;
			if (uncle != nullptr && uncle->colour == RED)
			{
				parent->colour = BLACK;
				uncle->colour = BLACK;
				grandpa->colour = RED;
				if (grandpa == root)
				{
					grandpa->colour = BLACK;
					break;
				}
				point = grandpa;
				parent = grandpa->parent;
				if (parent->colour == BLACK)
					break;
				continue;
			}


			//（uncle != nullptr && uncle->colour == RED）不满足
			int sign = 0;
			RBNode<T>* gff = grandpa->parent;
			//标记数据sign判断祖父节点与曾祖父节点的关系
			if (gff != nullptr)
			{
				if (gff->lchild = grandpa)
					sign = 1;
				else
					sign = 2;
			}
			//插入数据的父亲是爷爷的左节点
			if (parent->parent->lchild==parent)
			{
				//插入数据是父亲的左节点
				if (parent->lchild = point)
				{
					RotateRight(grandpa);
					grandpa->colour = BLACK;
					grandpa->rchild->colour = RED;
				}
				//插入数据是父亲的右节点
				else
				{
					RotateLeftRight(grandpa);
					grandpa->lchild = RED;
				}
			}
			else
			{
				if (parent->lchild = point)
				{
					Rotateleft(grandpa);
					grandpa->colour = BLACK;
					grandpa->lchild->colour = RED;
				}
				//插入数据是父亲的右节点
				else
				{
					RotateRightLeft(grandpa);
					grandpa->lchild = RED;
				}
			}
			if (parent->colour == BLACK)
				break;
			if (gff == nullptr)
				root = grandpa;
			else if (sign == 1)
				gff->lchild = grandpa;
			else if (sign == 2)
				gff->rchild = grandpa;

			break;
		}
		//无论如何根节点颜色为黑色
		root->colour = BLACK;
	}
private:
	//删除节点，释放内存
	void ReleaseNode(RBNode<T>* pnode)
	{
		if (pnode != nullptr)
		{
			ReleaseNode(pnode->lchild);
			ReleaseNode(pnode->rchild);
		}
		delete pnode;
	}

	//获取叔叔节点
	RBNode<T>* getuncle(RBNode<T>* p)
	{
		if (p->parent->lchild == p)
			return p->parent->rchild;
		else
			return p->parent->rchild;
	}

	//右旋节点
	void RotateRight(RBNode<T>*& pointer)
	{
		//         6      -----右旋----             4
		//     /      \                          /     \
		//    4        7                        3       6
		//  /   \                                      /  \
		// 3     5                                    5    7   
		RBNode<T>* node_1 = pointer;
		pointer = pointer->lchild;
		pointer->parent = node_1->parent;
		node_1->lchild = pointer->rchild;
		if (pointer->rchild)
			pointer->rchild->parent = node_1;
		pointer->rchild = node_1;
		node_1->parent = pointer;
	}

	//左旋节点
	void RotateLeft(RBNode<T>*& pointer)
	{
		//     4      -----左旋----             6
		//  /      \                         /     \
		// 3        6                     4         7
		//         /   \                 /  \
		//        5     7              3     5   
		RBNode<T>* node_1 = pointer;
		pointer = pointer->rchild;
		pointer->parent = node_1->parent;
		node_1->rchild = pointer->lchild;
		if (pointer->lchild)
			pointer->lchild->parent = node_1;
		pointer->lchild = node_1;
		node_1->parent = pointer;

	}
	//先左后右
	void RotateLeftRight(RBNode<T>*& pointer)
	{
		//如下图不全，只是示意，不要按照这个图写代码否则会造成代码出现bug
		//      6      -----先左旋----    6       -----再右旋----    5
		//   /      \                   /   \                      /    \
		//  4        7                 5     7                    4      6 
		//    \                       /                                    \
		//     5                     4                                      7
		RBNode<T>* noderoot = pointer;
		RBNode<T>* noderoot_left = pointer->lchild;
		RBNode<T>* noderoot_right = pointer->rchild;
		RotateLeft(noderoot_left);
		pointer->lchild = noderoot;
		RotateRight(noderoot_right);
	}
	//先右后左
	void RotateRightLeft(RBNode<T>*& pointer)
	{
		//      6     -----先右旋----     6       -----再左旋----     7
		//   /     \                   /     \                      /    \
		//  4        8                4       7                    6      8 
		//          /                           \                 /                   
		//         7                             8               4      
		RBNode<T>* noderoot = pointer;
		RBNode<T>* noderoot_left = pointer->lchild;
		RBNode<T>* noderoot_right = pointer->rchild;
		RotateRight(noderoot_right);
		pointer->rchild = noderoot;
		RotateLeft(noderoot_left);
	}



private:
	//根节点
	RBNode <T>* root;
};
template<typename T>
int main()
{
	RBNode<T>* root;
	RBTree();
	//还没有到定义的时候
	printf("OK");
	return 0;
}

总结

这四节课主要学了什么是红黑树，以及如何进行红黑树进行平衡性调整

学习了这四节你可以更加得心应手的去理解指针以及树的概念

并且在学习其他类型的树时会非常非常的得心应手

最后，恭喜你看到这里。