-
Notifications
You must be signed in to change notification settings - Fork 0
/
9-2.cpp
320 lines (303 loc) · 7 KB
/
9-2.cpp
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
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
#include<iostream>
#include"BinaryTree.h"
#include"myExceptions.h"
using namespace std;
#define BLACK 1
#define RED 0
template<class T>
class redBlackTree :public BinaryTree<T> {
public:
BinaryTreeNode<T>* LL(BinaryTreeNode<T>* t);
BinaryTreeNode<T>* RR(BinaryTreeNode<T>* t);
BinaryTreeNode<T>* LR(BinaryTreeNode<T>* t);
BinaryTreeNode<T>* RL(BinaryTreeNode<T>* t);
void Change(BinaryTreeNode<T>* t);
bool Search(const T& t)const;
redBlackTree<T>& Insert(const T& t);
redBlackTree<T>& Delete(const T& t);
void Delete(const T& t, bool yes);
void Ascend() { redBlackTree<T>::InOrderOutput(); }
};
template<class T>
BinaryTreeNode<T>* redBlackTree<T>::LL(BinaryTreeNode<T>* t)
{
BinaryTreeNode<T>* temp = t->LeftChild;
if (!t->father)
{
temp->father = NULL;
}
else
{
if (t == t->father->LeftChild)
{
t->father->LeftChild = temp;
temp->father = t->father;
}
else
{
t->father->RightChild = temp;
temp->father = t->father;
}
}
t->LeftChild = temp->RightChild;
temp->RightChild->father = t;
temp->RightChild = t;
t->father = temp;
t->color = RED;
temp->color = BLACK;
return temp;
}
template<class T>
BinaryTreeNode<T>* redBlackTree<T>::RR(BinaryTreeNode<T>* t)
{
BinaryTreeNode<T>* temp = t->RightChild;
if (!t->father)
{
temp->father = NULL;
}
else
{
if (t == t->father->RightChild)
{
t->father->RightChild = temp;
temp->father = t->father;
}
else
{
t->father->LeftChild = temp;
temp->father = t->father;
}
}
t->RightChild = temp->LeftChild;
temp->LeftChild->father = t;
temp->LeftChild = t;
t->father = temp;
t->color = RED;
temp->color = BLACK;
return temp;
}
template<class T>
BinaryTreeNode<T>* redBlackTree<T>::LR(BinaryTreeNode<T>* t)
{
BinaryTreeNode<T>* temp = t->LeftChild;
t->LeftChild = RR(temp);
return LL(t);
}
template<class T>
BinaryTreeNode<T>* redBlackTree<T>::RL(BinaryTreeNode<T>* t)
{
BinaryTreeNode<T>* temp = t->RightChild;
t->RightChild = LL(temp);
return RR(t);
}
template<class T>
void redBlackTree<T>::Change(BinaryTreeNode<T>* t)
{
if (!t->father || !t->father->father)
return;
BinaryTreeNode<T>* p = t->father->father;
if (!p->LeftChild || !p->RightChild || p->LeftChild->color == 1 || p->RightChild->color == 1)
{
if (p->LeftChild && p->LeftChild->color == 0)
{
if (t->father == p->LeftChild)
p = LL(p);
else
p = LR(p);
}
if (p->RightChild && p->RightChild->color == 0)
{
if (t->father == p->LeftChild)
p = RL(p);
else
p = RR(p);
}
}
if (p->LeftChild && p->RightChild)
{
if (p->LeftChild->color == 0 && p->RightChild->color == 0)
{
p->LeftChild->color = 1;
p->RightChild->color = 1;
if (!p->father)
p->color = 1;
else
{
p->color = 0;
Change(p);
}
}
}
}
template<class T>
bool redBlackTree<T>::Search(const T& t)const
{
//首先使p指向跟节点
BinaryTreeNode<T>* p = redBlackTree<T>::root;
while (p)
{
//两层if-else,三选一,k小于根节点时指向左子树,k大于根节点时指向右子树,等于根节点时返回true
if (t < p->data)
p = p->LeftChild;
else
{
if (t > p->data)
p = p->RightChild;
else
return true;
}
}
//没有找到关键值为k的元素,此时p为空,直接返回false
return false;
}
template<class T>
redBlackTree<T>& redBlackTree<T>::Insert(const T& t)
{
//p指向根节点,pp指向根节点的根节点(非初始时)
BinaryTreeNode<T>* p = redBlackTree<T>::root, * pp = 0;
while (p)
{
//pp指向上一个while循环结束的p节点的位置
pp = p;
//两层if-else,三选一,k小于根节点时指向左子树,
//k大于根节点时指向右子树,等于根节点时说明已经含有e这个元素,无法插入
if (t <= p->data)
p = p->LeftChild;
else
p = p->RightChild;
}
//现在已经找到了合适的插入位置
BinaryTreeNode<T>* r = new BinaryTreeNode<T>(t);
//当根节点存在时,判断插入其左子树还是插入其右子树
if (redBlackTree<T>::root)
{
if (t <= pp->data)
{
pp->LeftChild = r;
r->father = pp;
}
else
{
pp->RightChild = r;
r->father = pp;
}
Change(r);
}
//根节点不存在是e就是根节点
else
redBlackTree<T>::root = r;
return *this;
}
//删除函数,删除关键值为t的元素
template<class T>
redBlackTree<T>& redBlackTree<T>::Delete(const T& t)
{
//p指向根节点,pp指向根节点的根节点(非初始时)
BinaryTreeNode<T>* p = redBlackTree<T>::root, * pp = 0;
while (p && p->data != t)
{
pp = p;
if (t < p->data)
p = p->LeftChild;
else
p = p->RightChild;
}
//当p不存在的时候说明关键值为k的元素不存在,抛出异常即可
if (!p)
throw BadInput();
//要删除节点的左右节点都存在的情况下
if (p->LeftChild && p->RightChild)
{
//使s指向p的左孩子,ps指向p
BinaryTreeNode<T>* s = p->LeftChild, * ps = p;
//找到左孩子这一条线上最后一个右孩子用s来表示,ps表示s的父节点
while (s->RightChild)
{
ps = s;
s = s->RightChild;
}
//s为最大前驱,ps为其父节点
//s的数据来替代要删除的节点,至此,左右子树都存在的情况下大体完成
p->data = s->data;
//如果s有左节点,还要将s删除后左节点移上来,移动p和pp位置为下面的代码铺垫
//p为左孩子这一条线上最后一个右孩子s
p = s;
//pp为s的父节点
pp = ps;
}
//当p有左子树时(进入了上一个if循环),或p有左子树或右子树的一棵时(没进入上个if循环)
if (!p->LeftChild && !p->RightChild)
{
delete p;
return *this;
}
BinaryTreeNode<T>* c;
if (p->LeftChild)
{
p->LeftChild->color = BLACK;
c = p->LeftChild;
}
else
{
p->RightChild->color = BLACK;
c = p->RightChild;
}
//如果p是根节点直接把c赋值给根节点
if (p == redBlackTree<T>::root)
redBlackTree<T>::root = c;
//p不是根节点的话回找pp与p的关系,从而建立pp和c的关系
else
{
if (p == pp->LeftChild)
{
pp->LeftChild = c;
c->father = pp;
}
else
{
pp->RightChild = c;
c->father = pp;
}
if (c->color == 0 && pp->color == 0)
Change(c);
}
delete p;
return *this;
}
template<class T>
void redBlackTree<T>::Delete(const T& t, bool yes)
{
while (Search(t))
{
Delete(t);
}
}
int main()
{
redBlackTree<int> A;
int tmp;
cout << "-----insert datas-----" << endl << endl;
for (int i = 19; i > 0; i--)
{
tmp = i + 1;
cout << tmp << " ";
A.Insert(tmp);
}
tmp = 15;
cout << tmp << " ";
A.Insert(tmp);
tmp = 15;
cout << tmp << " ";
A.Insert(tmp);
tmp = 5;
cout << tmp << " ";
A.Insert(tmp);
cout << endl << "-----input-----" << endl << endl;
A.Ascend();
cout << endl << "-----delete 3,8,12-----" << endl << endl;
A.Delete(3);
A.Delete(8);
A.Delete(15);
A.Ascend();
return 0;
}