目录
回顾
情况
解决办法
右旋
变色
接上一章的问题
代码讲解
判断爷爷是左节点还是右节点
右旋函数代码
选择情况并且执行右旋函数代码
连接到原来的树上
注意事项
总代码
总结
回顾
上期的博客
C++红黑树（2/4）_木木em哈哈的博客-CSDN博客
https://blog.csdn.net/mumuemhaha/article/details/131159253?spm=1001.2014.3001.5501下期博客
c++红黑树（4/4）_木木em哈哈的博客-CSDN博客https://blog.csdn.net/mumuemhaha/article/details/131296981?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22131296981%22%2C%22source%22%3A%22mumuemhaha%22%7D
在上一期的博客中我们学到了第一种情况红黑树如何进行平衡性调整
接下来我们要试试第二种情况，红黑树如何进行平衡性调整
情况
第二种情况就是父亲节点为红色，叔叔节点没有或者为黑色，父亲节点为爷爷的左节点，且爷爷节点为曾祖父（爷爷的父亲）节点的左节点。
就是这么一个图
解决办法
这里要把节点进行右旋
在这里可能听起来会比较难以理解
但是记住你需要做的步骤，代码就可以很简单的进行实现
右旋
把曾祖父的左孩子指针从祖父那里断开（同时也断开祖父的父亲指针）
然后曾祖父的左孩子指针指向父亲节点
同时把父亲节点得到右指针指向祖父节点，如果父亲节点有右孩子节点需要把他提取出来放到原曾祖父的左孩子（同时连接祖父的父亲指针，后面都记得变，不说了）
就完成了右旋的操作
结果图为
变色
这个时候只需要变色就行了
把你的父亲节点变为黑色，同时把原爷爷节点变为红色
就为下图
这时候红黑树就进行了平衡
接上一章的问题
上一章的图片为
还记得我们上一回记住的吗？
把篮圈内的部分看为一个整体（因为他已经平衡了）
这时候他就是新的红色节点
他的父亲为"50"，他的祖父为"80"
可能看起来会比较复杂
我们只需要记住操作
由于没有曾祖父所以不需要改曾祖父的节点
把父亲的节点的右孩子连接到祖父节点，再把原父亲右孩子节点连接到祖父的左节点
这样宏观的结果就是相当于把爷爷节点"拽"了下来
最后的图为
最后进行变色
一个红黑树到达平衡
代码讲解
首先接在上一章情况之后
代码
判断爷爷是左节点还是右节点
1
2
3
4
5
6
7
8
9
10
11
|
int sign = 0;
RBNode<T>* gff = grandpa->parent;
if (gff != nullptr)
{
if (gff->lchild = grandpa)
sign = 1;
else
sign = 2;
}
|
这是为了判断祖父是曾祖父的左节点还是右节点方便连接
右旋函数代码
现在我们要创建一个右旋函数
我以函数是传递爷爷节点参数为例
除去曾祖父链接其他代码都按照说明写上去，按照逻辑来，不会那么难理解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| void RotateRight(RBNode<T>*& pointer)
{
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;
}
|
选择情况并且执行右旋函数代码
选择祖父为为左节点，父亲也为左节点的情况并执行代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
if (parent->parent->lchild==parent)
{
if (parent->lchild = point)
{
RotateRight(grandpa);
}
else
{
}
}
else
{
}
|
连接到原来的树上
最后就要把原父亲节点连接到曾祖父节点上（也就是连接到原来树上）
1
2
3
4
5
6
7
8
| if (parent->colour == BLACK)
break;
if (gff == nullptr)
root = grandpa;
else if (sign == 1)
gff->lchild = grandpa;
else if (sign == 2)
gff->rchild = grandpa;
|
注意事项
在每次平衡性调整时，需要注意新节点的颜色最好不要变，因为它可能会是一个整体
比如这个
这里新节点的颜色被整体看为红色
如果后续新节点要变化颜色，这个整体就要变化为黑色（也就是30这个节点变为黑色），一般情况下要篮圈内进行平衡性调整，这是复杂化且不合理的。
注意——可以改变，只需要将所有颜色互换就行了！！
总代码
附上现在更新的总代码
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
| #include <iostream>
using namespace std;
enum Colour
{
RED,
BLACK,
};
template<typename T>
struct RBNode
{
RBNode* lchild,
* rchild,
* parent;
T data;
Colour colour=RED;
};
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;
}
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;
}
int sign = 0;
RBNode<T>* gff = grandpa->parent;
if (gff != nullptr)
{
if (gff->lchild = grandpa)
sign = 1;
else
sign = 2;
}
if (parent->parent->lchild==parent)
{
if (parent->lchild = point)
{
RotateRight(grandpa);
}
else
{
}
}
else
{
}
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)
{
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;
}
private:
RBNode <T>* root;
};
template<typename T>
int main()
{
RBNode<T>* root;
RBTree();
printf("OK");
return 0;
}
|
总结
再次恭喜你，了解了红黑树的第二种情况的处理方法，接下来的最后一章的要讲剩下来的三种情况——因为设计左旋的代码和右旋其实相差不多，我们理解了右旋代码可以很快的理解并且使用左旋代码。
https://blog.csdn.net/mumuemhaha/article/details/131159253?spm=1001.2014.3001.5501
https://blog.csdn.net/mumuemhaha/article/details/131296981?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22131296981%22%2C%22source%22%3A%22mumuemhaha%22%7D
