红黑树的C++实现–根据《算法导论》中的算法实现

  红黑树是一种有序的平衡二叉树,STL中的map和set容器的底层实现就是红黑树,在《STL源码剖析》中有另一种实现方式。不过STL中的实现相对来说晦涩难懂,而《算法导论》中的算法则比较清晰易懂。这里的这份实现就是《算法导论》中STL算法的一种C++实现。关于红色树的特性以及规则这里还有这里都有详细描述。下面就是我的实现代码:

1 #ifndef __RBTREE_H__
2 #define __RBTREE_H__
3
4 #include <iostream>
5 const int RED = 0;
6 const int BLACK = 1;
7
8 struct RBTreeNode
9 {
10 RBTreeNode* left;
11 RBTreeNode* right;
12 RBTreeNode* parent;
13 int nData;
14 int color;//RED=0,BLACK=1
15 };
16
17 class RBTree
18 {
19
20 public:
21 RBTree();
22 ~RBTree();
23 public:
24 bool Insert(const int nData);
25 bool Delete(const int nData);
26 RBTreeNode* Find(const int nData);
27 void Display()
28 {
29 PrintTree(root);
30 }
31 private:
32 void RotateLeft(RBTreeNode* pNode);
33 void RotateRight(RBTreeNode* pNode);
34 void InsertFixup(RBTreeNode* pNode);
35 void DeleteFixup(RBTreeNode* pNode);
36
37 RBTreeNode* CreateNode(int nData);
38 RBTreeNode* DeleteNode(RBTreeNode* pNode);
39 RBTreeNode* FindNode(const int nData);
40 RBTreeNode* Maximum(RBTreeNode* pNode);
41 RBTreeNode* Minimum(RBTreeNode* pNode);
42 RBTreeNode* Successor(RBTreeNode* pNode);
43
44 void DeleteTree(RBTreeNode* pNode);
45 void PrintTree(RBTreeNode* pNode) const;
46 private:
47 RBTreeNode* root;
48 RBTreeNode* nil;
49 int node_count;
50 };
51
52 RBTree::RBTree()
53 {
54 nil = new RBTreeNode();
55
56 nil->left = NULL;
57 nil->right = NULL;
58 nil->parent = NULL;
59 nil->nData = 0;
60 nil->color = BLACK;
61
62 root = nil;
63 }
64
65 RBTree::~RBTree()
66 {
67 DeleteTree(root);
68 delete nil;
69 root = NULL;
70 nil = NULL;
71 }
72
73 RBTreeNode* RBTree::CreateNode(int nData)
74 {
75 RBTreeNode* pTempNode = new RBTreeNode();
76
77 pTempNode->left = nil;
78 pTempNode->right = nil;
79 pTempNode->parent = nil;
80 pTempNode->nData = nData;
81 pTempNode->color = RED;
82
83 return pTempNode;
84 }
85
86 void RBTree::DeleteTree(RBTreeNode* pNode)
87 {
88 if(pNode == nil)
89 return;
90
91 DeleteTree(pNode->left);
92 DeleteTree(pNode->right);
93
94 delete pNode;
95 pNode = NULL;
96 }
97
98 //左旋转
99 void RBTree::RotateLeft(RBTreeNode* pNode)
100 {
101 RBTreeNode* pRNode = pNode->right;
102 pNode->right = pRNode->left;
103
104 if(pRNode->left != nil)
105 {
106 pRNode->left->parent = pNode;
107 pRNode->parent = pNode->parent;
108 }
109
110 if(pNode->parent == nil)
111 {
112 root = pRNode;
113 }
114 else if(pNode->parent->left == pNode)
115 {
116 pNode->parent->left = pRNode;
117 }
118 else
119 {
120 pNode->parent->right = pRNode;
121 }
122
123 pRNode->left = pNode;
124 pNode->parent = pRNode;
125 }
126
127 //右旋转
128 void RBTree::RotateRight(RBTreeNode* pNode)
129 {
130 RBTreeNode* pLNode = pNode->left;
131 pNode->left = pLNode->right;
132
133 if(pLNode->right != nil)
134 {
135 pLNode->right->parent = pNode;
136 pLNode->parent = pNode->parent;
137 }
138
139 if(pNode->parent == nil)
140 {
141 root = pLNode;
142 }
143 else if(pNode->parent->left == pNode)
144 {
145 pNode->parent->left = pLNode;
146 }
147 else
148 {
149 pNode->parent->right = pLNode;
150 }
151
152 pLNode->right = pNode;
153 pNode->parent = pLNode;
154 }
155
156 RBTreeNode* RBTree::Maximum(RBTreeNode* pNode)
157 {
158 while(pNode->right != nil)
159 pNode = pNode->right;
160
161 return pNode;
162 }
163
164 RBTreeNode* RBTree::Minimum(RBTreeNode* pNode)
165 {
166 while(pNode->left != nil)
167 pNode = pNode->left;
168
169 return pNode;
170 }
171
172 RBTreeNode* RBTree::Successor(RBTreeNode* pNode)
173 {
174 if(pNode->right != nil)
175 return Minimum(pNode->right);
176
177 RBTreeNode* pPNode = pNode->parent;
178 while(pPNode != nil && pNode == pPNode->right)
179 {
180 pNode = pPNode;
181 pPNode = pNode->parent;
182 }
183
184 return pPNode;
185 }
186
187 bool RBTree::Insert(const int nData)
188 {
189 RBTreeNode* pNewNode = CreateNode(nData);
190 RBTreeNode* pPNewNode = nil;
191 RBTreeNode* pTemp = root;
192
193 while( pTemp != nil)
194 {
195 pPNewNode = pTemp;
196
197 if(nData < pTemp->nData)
198 pTemp = pTemp->left;
199 else
200 pTemp = pTemp->right;
201 }
202
203 pNewNode->parent = pPNewNode;
204
205 if(pPNewNode == nil)
206 root = pNewNode;
207 else if(nData < pPNewNode->nData)
208 pPNewNode->left = pNewNode;
209 else
210 pPNewNode->right = pNewNode;
211
212 InsertFixup(pNewNode);
213
214 return true;
215 }
216
217 void RBTree::InsertFixup(RBTreeNode* pNode)
218 {
219 while(pNode->parent->color == RED)
220 {
221 if(pNode->parent == pNode->parent->parent->left)
222 {
223 RBTreeNode* pUNode = pNode->parent->parent->right;//pNode的叔父节点
224
225 if(pUNode->color == RED)//case 1
226 {
227 pNode->parent->color = BLACK;
228 pUNode->color = BLACK;
229 pNode->parent->parent->color = RED;
230
231 pNode = pNode->parent->parent;
232 }
233 else if(pNode == pNode->parent->right)//case 2
234 {
235 pNode = pNode->parent;
236 RotateLeft(pNode);
237 }
238 else//case 3
239 {
240 pNode->parent->color = BLACK;
241 pNode->parent->parent->color = RED;
242 RotateRight(pNode->parent->parent);
243 }
244 }//pNode的父节点是其父节点的左子节点
245 else
246 {
247 RBTreeNode* pUNode = pNode->parent->parent->left;//pNode的叔父节点
248
249 if(pUNode->color == RED)//case 1
250 {
251 pNode->parent->color = BLACK;
252 pUNode->color = BLACK;
253 pNode->parent->parent->color = RED;
254
255 pNode = pNode->parent->parent;
256 }
257 else if(pNode == pNode->parent->left)//case 2
258 {
259 pNode = pNode->parent;
260 RotateRight(pNode);
261 }
262 else//case 3
263 {
264 pNode->parent->color = BLACK;
265 pNode->parent->parent->color = RED;
266 RotateLeft(pNode->parent->parent);
267 }
268 }//pNode的父节点是其父节点的右子节点
269 }//while(pNode->parent->color == RED)
270
271 root->color = BLACK;
272 }
273
274 bool RBTree::Delete(const int nData)
275 {
276 RBTreeNode* pDeleteNode = FindNode(nData);
277
278 if(pDeleteNode == nil)
279 {
280 std::cout << no data << std::endl;
281 return false;
282 }
283
284 DeleteNode(pDeleteNode);
285
286 return true;
287 }
288
289 RBTreeNode* RBTree::FindNode(const int nData)
290 {
291 RBTreeNode* pTemp = root;
292
293 while(pTemp != nil)
294 {
295 if(nData < pTemp->nData)
296 pTemp = pTemp->left;
297 else if(nData > pTemp->nData)
298 pTemp = pTemp->right;
299 else
300 return pTemp;
301 }
302
303 return nil;
304 }
305
306 RBTreeNode* RBTree::DeleteNode(RBTreeNode* pNode)
307 {
308 RBTreeNode* pDeleteNode = nil;//删除节点
309 RBTreeNode* pCDeleteNode = nil;//删除节点的子节点
310
311 if(pNode->left == nil || pNode->right == nil)
312 pDeleteNode = pNode;
313 else
314 pDeleteNode = Successor(pNode);
315
316 if(pDeleteNode->left != nil)
317 pCDeleteNode = pDeleteNode->left;
318 else
319 pCDeleteNode = pDeleteNode->right;
320
321 if(pDeleteNode->parent == nil)
322 root = pCDeleteNode;
323 else if(pDeleteNode == pDeleteNode->parent->left)
324 pDeleteNode->parent->left = pCDeleteNode;
325 else
326 pDeleteNode->parent->right = pCDeleteNode;
327
328 if(pDeleteNode != pNode)
329 pNode->nData = pDeleteNode->nData;
330
331 pCDeleteNode->parent = pDeleteNode->parent;
332
333 if(pDeleteNode->color == BLACK)
334 DeleteFixup(pCDeleteNode);
335
336 return pDeleteNode;
337 }
338
339 void RBTree::DeleteFixup(RBTreeNode* pNode)
340 {
341 while(pNode != root && pNode->color == BLACK)
342 {
343 if(pNode == pNode->parent->left)
344 {
345 RBTreeNode* pBNode = pNode->parent->right;//pNode的兄弟节点
346
347 if(pBNode->color = RED)//case 1
348 {
349 pBNode->color = BLACK;
350 pNode->parent->color = RED;
351
352 RotateLeft(pNode->parent);
353 pBNode = pNode->parent->right;
354 }
355
356 if(pBNode->left->color == BLACK && pBNode->right->color == BLACK)//case 2
357 {
358 pBNode->color = RED;
359 pNode = pNode->parent;
360 }
361 else if(pBNode->right->color == BLACK)//case 3
362 {
363 pBNode->left->color = BLACK;
364 pBNode->color = RED;
365
366 RotateRight(pBNode);
367 pBNode = pNode->parent->right;
368 }
369 else//case 4
370 {
371 pBNode->color = pNode->parent->color;
372 pNode->parent->color = BLACK;
373 pBNode->right->color = BLACK;
374
375 RotateLeft(pNode->parent);
376 pNode = root;
377 }
378 }
379 else
380 {
381 RBTreeNode* pBNode = pNode->parent->left;//pNode的兄弟节点
382
383 if(pBNode->color = RED)//case 1
384 {
385 pBNode->color = BLACK;
386 pNode->parent->color = RED;
387
388 RotateLeft(pNode->parent);
389 pBNode = pNode->parent->left;
390 }
391
392 if(pBNode->left->color == BLACK && pBNode->right->color == BLACK)//case 2
393 {
394 pBNode->color = RED;
395 pNode = pNode->parent;
396 }
397 else if(pBNode->left->color == BLACK)//case 3
398 {
399 pBNode->right->color = BLACK;
400 pBNode->color = RED;
401
402 RotateRight(pBNode);
403 pBNode = pNode->parent->left;
404 }
405 else//case 4
406 {
407 pBNode->color = pNode->parent->color;
408 pNode->parent->color = BLACK;
409 pBNode->left->color = BLACK;
410
411 RotateLeft(pNode->parent);
412 pNode = root;
413 }
414 }//if(pNode == pNode->parent->left)
415 }//while(pNode != root && pNode->color == BLACK)
416
417 pNode->color = BLACK;
418 }
419
420 void RBTree::PrintTree(RBTreeNode* pNode) const
421 {
422 if (NULL == root)
423 return;
424
425 if (nil == pNode)
426 {
427 return;
428 }
429
430 static int n = 0;
431
432 if(pNode == root)
433 {
434 std::cout << [ << ++n << ]nData = << pNode->nData << ,nParentData= 0 ,;
435
436 if(pNode->left)
437 std::cout << nLeftData= << pNode->left->nData << ,;
438 if(pNode->right)
439 std::cout << nRightData= << pNode->right->nData << ,;
440
441 std::cout << color = << pNode->color << std::endl;
442 }
443 else
444 {
445 std::cout << [ << ++n << ]nData = << pNode->nData << ,nParentData= << pNode->parent->nData << ,;
446
447 if(pNode->left)
448 std::cout << nLeftData= << pNode->left->nData << ,;
449 if(pNode->right)
450 std::cout << nRightData= << pNode->right->nData << ,;
451
452 std::cout << color = << pNode->color << std::endl;
453 }
454 PrintTree(pNode->left);
455 PrintTree(pNode->right);
456 }
457
458 #endif //__RBTREE_H__

  将上面的代码复制粘贴到同一个文件中,文件名RBTree.h。下面是测试程序复制到文件Test.cpp中。

1 #include RBTree.h
2 #include <iostream>
3 #include <exception>
4
5 int main()
6 {
7 try
8 {
9 RBTree rbt;
10 for(int i = 1; i < 10; i++)
11 {
12 rbt.Insert(i);
13 }
14 rbt.Delete(4);
15 rbt.Display();
16 }
17 catch (std::exception& e)
18 {
19 std::cout << e.what() << std::endl;
20 }
21 }

  然后用g++ -o Test Test.cpp该命令进行编译。执行结果如下:

1 [kiven@localhost Test]$ g++ –o Test Test.cpp
2 [kiven@localhost Test]$ ls
3 RBTree.h Test Test.cpp
4 [kiven@localhost Test]$ ./Test
5 [1]nData = 2,nParentData= 0 ,nLeftData= 1 ,nRightData= 5 ,color = 1
6 [2]nData = 1,nParentData= 2 ,nLeftData= 0 ,nRightData= 0 ,color = 1
7 [3]nData = 5,nParentData= 3 ,nLeftData= 3 ,nRightData= 6 ,color = 0
8 [4]nData = 3,nParentData= 5 ,nLeftData= 0 ,nRightData= 0 ,color = 1
9 [5]nData = 6,nParentData= 8 ,nLeftData= 0 ,nRightData= 7 ,color = 1
10 [6]nData = 7,nParentData= 6 ,nLeftData= 0 ,nRightData= 0 ,color = 0
11 [kiven@localhost Test]$

  上面的实现也仅仅是实现了数据结构本身,所以整个都比较粗糙,节点中的数据也用最简单的整形来代替,但是基本功能不缺。

本文链接



You must enable javascript to see captcha here!

Copyright © All Rights Reserved · Green Hope Theme by Sivan & schiy · Proudly powered by WordPress

无觅相关文章插件,快速提升流量