当前位置:   article > 正文

红黑树的C++完整实现源码_c++源码

c++源码

红黑树的C++完整实现源码


作者:July、saturnman。
时间:二零一一年三月二十九日。
出处:http://blog.csdn.net/v_JULY_v
声明:版权所有,侵权必究。
-------------------------------------------

前言:
    红黑树系列文章已经写到第5篇了。虽然第三篇文章:红黑树的c源码实现与剖析,用c语言完整实现过红黑树,但个人感觉,代码还是不够清晰。特此,再奉献出一份c++的完整实现源码,以飨读者。

    此份c++实现源码,代码紧凑了许多,也清晰了不少,同时采取c++类实现的方式,代码也更容易维护以及重用。ok,有任何问题,欢迎指正。


第一部分、红黑树的c++完整实现源码

    本文包含红黑树c++实现的完整源码,所有的解释都含在注释中,所有的有关红黑树的原理及各种插入、删除操作的情况,都已在本人的红黑树系列的前4篇文章中,一一阐述。且在此红黑树系列第五篇文章中:红黑树从头至尾插入和删除结点的全程演示图,把所有的插入、删除情况都一一展示尽了。
    因此,有关红黑树的全部原理,请参考其它文章,重点可参考此文:红黑树算法的实现与剖析。因此,相关原理,本文不再赘述。

    ok,以下,即是红黑树c++实现的全部源码,先是RBTree.h,然后是RBTree.cpp。

RBTree.h

  1. //file RBTree.h
  2. //written by saturnman,20101008。
  3. //updated by July,20110329。
  4. /*-----------------------------------------------
  5. 版权声明:
  6. July和saturnman对此份红黑树的c++实现代码享有全部的版权,
  7. 谢绝转载,侵权必究。
  8. ------------------------------------------------*/
  9. #ifndef _RB_TREE_H_
  10. #define _RB_TREE_H_
  11. #include<iostream>
  12. #include<string>
  13. #include<sstream>
  14. #include<fstream>
  15. using namespace std;
  16. template<class KEY, class U>
  17. class RB_Tree
  18. {
  19. private:
  20. RB_Tree(const RB_Tree& input){}
  21. const RB_Tree& operator=(const RB_Tree& input){}
  22. private:
  23. enum COLOR{ RED, BLACK };
  24. class RB_Node
  25. {
  26. public:
  27. RB_Node()
  28. {
  29. //RB_COLOR = BLACK;
  30. right = NULL;
  31. left = NULL;
  32. parent = NULL;
  33. }
  34. COLOR RB_COLOR;
  35. RB_Node* right;
  36. RB_Node* left;
  37. RB_Node* parent;
  38. KEY key;
  39. U data;
  40. };
  41. public:
  42. RB_Tree()
  43. {
  44. this->m_nullNode = new RB_Node();
  45. this->m_root = m_nullNode;
  46. this->m_nullNode->right = this->m_root;
  47. this->m_nullNode->left = this->m_root;
  48. this->m_nullNode->parent = this->m_root;
  49. this->m_nullNode->RB_COLOR = BLACK;
  50. }
  51. bool Empty()
  52. {
  53. if (this->m_root == this->m_nullNode)
  54. {
  55. return true;
  56. }
  57. else
  58. {
  59. return false;
  60. }
  61. }
  62. //查找key
  63. RB_Node* find(KEY key)
  64. {
  65. RB_Node* index = m_root;
  66. while (index != m_nullNode)
  67. {
  68. if (key<index->key)
  69. {
  70. index = index->left; //比当前的小,往左
  71. }
  72. else if (key>index->key)
  73. {
  74. index = index->right; //比当前的大,往右
  75. }
  76. else
  77. {
  78. break;
  79. }
  80. }
  81. return index;
  82. }
  83. //--------------------------插入结点总操作----------------------------------
  84. //全部的工作,都在下述伪代码中:
  85. /*RB-INSERT(T, z)
  86. 1 y ← nil[T] // y 始终指向 x 的父结点。
  87. 2 x ← root[T] // x 指向当前树的根结点,
  88. 3 while x ≠ nil[T]
  89. 4 do y ← x
  90. 5 if key[z] < key[x] //向左,向右..
  91. 6 then x ← left[x]
  92. 7 else x ← right[x] //为了找到合适的插入点,x探路跟踪路径,直到x成为NIL 为止。
  93. 8 p[z] ← y //y置为 插入结点z 的父结点。
  94. 9 if y = nil[T]
  95. 10 then root[T] ← z
  96. 11 else if key[z] < key[y]
  97. 12 then left[y] ← z
  98. 13 else right[y] ← z //此 8-13行,置z 相关的指针。
  99. 14 left[z] ← nil[T]
  100. 15 right[z] ← nil[T] //设为空,
  101. 16 color[z] ← RED //将新插入的结点z作为红色
  102. 17 RB-INSERT-FIXUP(T, z)
  103. */
  104. //因为将z着为红色,可能会违反某一红黑性质,
  105. //所以需要调用下面的RB-INSERT-FIXUP(T, z)来保持红黑性质。
  106. bool Insert(KEY key, U data)
  107. {
  108. RB_Node* insert_point = m_nullNode;
  109. RB_Node* index = m_root;
  110. while (index != m_nullNode)
  111. {
  112. insert_point = index;
  113. if (key<index->key)
  114. {
  115. index = index->left;
  116. }
  117. else if (key>index->key)
  118. {
  119. index = index->right;
  120. }
  121. else
  122. {
  123. return false;
  124. }
  125. }
  126. RB_Node* insert_node = new RB_Node();
  127. insert_node->key = key;
  128. insert_node->data = data;
  129. insert_node->RB_COLOR = RED;
  130. insert_node->right = m_nullNode;
  131. insert_node->left = m_nullNode;
  132. if (insert_point == m_nullNode) //如果插入的是一颗空树
  133. {
  134. m_root = insert_node;
  135. m_root->parent = m_nullNode;
  136. m_nullNode->left = m_root;
  137. m_nullNode->right = m_root;
  138. m_nullNode->parent = m_root;
  139. }
  140. else
  141. {
  142. if (key < insert_point->key)
  143. {
  144. insert_point->left = insert_node;
  145. }
  146. else
  147. {
  148. insert_point->right = insert_node;
  149. }
  150. insert_node->parent = insert_point;
  151. }
  152. InsertFixUp(insert_node); //调用InsertFixUp修复红黑树性质。
  153. }
  154. //---------------------插入结点性质修复--------------------------------
  155. //3种插入情况,都在下面的伪代码中(未涉及到所有全部的插入情况)。
  156. /*
  157. RB-INSERT-FIXUP(T, z)
  158. 1 while color[p[z]] = RED
  159. 2 do if p[z] = left[p[p[z]]]
  160. 3 then y ← right[p[p[z]]]
  161. 4 if color[y] = RED
  162. 5 then color[p[z]] ← BLACK ? Case 1
  163. 6 color[y] ← BLACK ? Case 1
  164. 7 color[p[p[z]]] ← RED ? Case 1
  165. 8 z ← p[p[z]] ? Case 1
  166. 9 else if z = right[p[z]]
  167. 10 then z ← p[z] ? Case 2
  168. 11 LEFT-ROTATE(T, z) ? Case 2
  169. 12 color[p[z]] ← BLACK ? Case 3
  170. 13 color[p[p[z]]] ← RED ? Case 3
  171. 14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
  172. 15 else (same as then clause with "right" and "left" exchanged)
  173. 16 color[root[T]] ← BLACK
  174. */
  175. //然后的工作,就非常简单了,即把上述伪代码改写为下述的c++代码:
  176. void InsertFixUp(RB_Node* node)
  177. {
  178. while (node->parent->RB_COLOR == RED)
  179. {
  180. if (node->parent == node->parent->parent->left) //
  181. {
  182. RB_Node* uncle = node->parent->parent->right;
  183. if (uncle->RB_COLOR == RED) //插入情况1,z的叔叔y是红色的。
  184. {
  185. node->parent->RB_COLOR = BLACK;
  186. uncle->RB_COLOR = BLACK;
  187. node->parent->parent->RB_COLOR = RED;
  188. node = node->parent->parent;
  189. }
  190. else if (uncle->RB_COLOR == BLACK) //插入情况2:z的叔叔y是黑色的,。
  191. {
  192. if (node == node->parent->right) //且z是右孩子
  193. {
  194. node = node->parent;
  195. RotateLeft(node);
  196. }
  197. //else //插入情况3:z的叔叔y是黑色的,但z是左孩子。
  198. //{
  199. node->parent->RB_COLOR = BLACK;
  200. node->parent->parent->RB_COLOR = RED;
  201. RotateRight(node->parent->parent);
  202. //}
  203. }
  204. }
  205. else //这部分是针对为插入情况1中,z的父亲现在作为祖父的右孩子了的情况,而写的。
  206. //15 else (same as then clause with "right" and "left" exchanged)
  207. {
  208. RB_Node* uncle = node->parent->parent->left;
  209. if (uncle->RB_COLOR == RED)
  210. {
  211. node->parent->RB_COLOR = BLACK;
  212. uncle->RB_COLOR = BLACK;
  213. uncle->parent->RB_COLOR = RED;
  214. node = node->parent->parent;
  215. }
  216. else if (uncle->RB_COLOR == BLACK)
  217. {
  218. if (node == node->parent->left)
  219. {
  220. node = node->parent;
  221. RotateRight(node); //与上述代码相比,左旋改为右旋
  222. }
  223. //else
  224. //{
  225. node->parent->RB_COLOR = BLACK;
  226. node->parent->parent->RB_COLOR = RED;
  227. RotateLeft(node->parent->parent); //右旋改为左旋,即可。
  228. //}
  229. }
  230. }
  231. }
  232. m_root->RB_COLOR = BLACK;
  233. }
  234. //左旋代码实现
  235. bool RotateLeft(RB_Node* node)
  236. {
  237. if (node == m_nullNode || node->right == m_nullNode)
  238. {
  239. return false;//can't rotate
  240. }
  241. RB_Node* lower_right = node->right;
  242. lower_right->parent = node->parent;
  243. node->right = lower_right->left;
  244. if (lower_right->left != m_nullNode)
  245. {
  246. lower_right->left->parent = node;
  247. }
  248. if (node->parent == m_nullNode) //rotate node is root
  249. {
  250. m_root = lower_right;
  251. m_nullNode->left = m_root;
  252. m_nullNode->right = m_root;
  253. //m_nullNode->parent = m_root;
  254. }
  255. else
  256. {
  257. if (node == node->parent->left)
  258. {
  259. node->parent->left = lower_right;
  260. }
  261. else
  262. {
  263. node->parent->right = lower_right;
  264. }
  265. }
  266. node->parent = lower_right;
  267. lower_right->left = node;
  268. }
  269. //右旋代码实现
  270. bool RotateRight(RB_Node* node)
  271. {
  272. if (node == m_nullNode || node->left == m_nullNode)
  273. {
  274. return false;//can't rotate
  275. }
  276. RB_Node* lower_left = node->left;
  277. node->left = lower_left->right;
  278. lower_left->parent = node->parent;
  279. if (lower_left->right != m_nullNode)
  280. {
  281. lower_left->right->parent = node;
  282. }
  283. if (node->parent == m_nullNode) //node is root
  284. {
  285. m_root = lower_left;
  286. m_nullNode->left = m_root;
  287. m_nullNode->right = m_root;
  288. //m_nullNode->parent = m_root;
  289. }
  290. else
  291. {
  292. if (node == node->parent->right)
  293. {
  294. node->parent->right = lower_left;
  295. }
  296. else
  297. {
  298. node->parent->left = lower_left;
  299. }
  300. }
  301. node->parent = lower_left;
  302. lower_left->right = node;
  303. }
  304. //--------------------------删除结点总操作----------------------------------
  305. //伪代码,不再贴出,详情,请参考此红黑树系列第二篇文章:
  306. //经典算法研究系列:五、红黑树算法的实现与剖析:
  307. //http://blog.csdn.net/v_JULY_v/archive/2010/12/31/6109153.aspx。
  308. bool Delete(KEY key)
  309. {
  310. RB_Node* delete_point = find(key);
  311. if (delete_point == m_nullNode)
  312. {
  313. return false;
  314. }
  315. if (delete_point->left != m_nullNode && delete_point->right != m_nullNode)
  316. {
  317. RB_Node* successor = InOrderSuccessor(delete_point);
  318. delete_point->data = successor->data;
  319. delete_point->key = successor->key;
  320. delete_point = successor;
  321. }
  322. RB_Node* delete_point_child;
  323. if (delete_point->right != m_nullNode)
  324. {
  325. delete_point_child = delete_point->right;
  326. }
  327. else if (delete_point->left != m_nullNode)
  328. {
  329. delete_point_child = delete_point->left;
  330. }
  331. else
  332. {
  333. delete_point_child = m_nullNode;
  334. }
  335. delete_point_child->parent = delete_point->parent;
  336. if (delete_point->parent == m_nullNode)//delete root node
  337. {
  338. m_root = delete_point_child;
  339. m_nullNode->parent = m_root;
  340. m_nullNode->left = m_root;
  341. m_nullNode->right = m_root;
  342. }
  343. else if (delete_point == delete_point->parent->right)
  344. {
  345. delete_point->parent->right = delete_point_child;
  346. }
  347. else
  348. {
  349. delete_point->parent->left = delete_point_child;
  350. }
  351. if (delete_point->RB_COLOR == BLACK && !(delete_point_child == m_nullNode && delete_point_child->parent == m_nullNode))
  352. {
  353. DeleteFixUp(delete_point_child);
  354. }
  355. delete delete_point;
  356. return true;
  357. }
  358. //---------------------删除结点性质修复-----------------------------------
  359. //所有的工作,都在下述23行伪代码中:
  360. /*
  361. RB-DELETE-FIXUP(T, x)
  362. 1 while x ≠ root[T] and color[x] = BLACK
  363. 2 do if x = left[p[x]]
  364. 3 then w ← right[p[x]]
  365. 4 if color[w] = RED
  366. 5 then color[w] ← BLACK ? Case 1
  367. 6 color[p[x]] ← RED ? Case 1
  368. 7 LEFT-ROTATE(T, p[x]) ? Case 1
  369. 8 w ← right[p[x]] ? Case 1
  370. 9 if color[left[w]] = BLACK and color[right[w]] = BLACK
  371. 10 then color[w] ← RED ? Case 2
  372. 11 x p[x] ? Case 2
  373. 12 else if color[right[w]] = BLACK
  374. 13 then color[left[w]] ← BLACK ? Case 3
  375. 14 color[w] ← RED ? Case 3
  376. 15 RIGHT-ROTATE(T, w) ? Case 3
  377. 16 w ← right[p[x]] ? Case 3
  378. 17 color[w] ← color[p[x]] ? Case 4
  379. 18 color[p[x]] ← BLACK ? Case 4
  380. 19 color[right[w]] ← BLACK ? Case 4
  381. 20 LEFT-ROTATE(T, p[x]) ? Case 4
  382. 21 x ← root[T] ? Case 4
  383. 22 else (same as then clause with "right" and "left" exchanged)
  384. 23 color[x] ← BLACK
  385. */
  386. //接下来的工作,很简单,即把上述伪代码改写成c++代码即可。
  387. void DeleteFixUp(RB_Node* node)
  388. {
  389. while (node != m_root && node->RB_COLOR == BLACK)
  390. {
  391. if (node == node->parent->left)
  392. {
  393. RB_Node* brother = node->parent->right;
  394. if (brother->RB_COLOR == RED) //情况1:x的兄弟w是红色的。
  395. {
  396. brother->RB_COLOR = BLACK;
  397. node->parent->RB_COLOR = RED;
  398. RotateLeft(node->parent);
  399. }
  400. else //情况2:x的兄弟w是黑色的,
  401. {
  402. if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)
  403. //且w的俩个孩子都是黑色的。
  404. {
  405. brother->RB_COLOR = RED;
  406. node = node->parent;
  407. }
  408. else if (brother->right->RB_COLOR == BLACK)
  409. //情况3:x的兄弟w是黑色的,w的右孩子是黑色(w的左孩子是红色)。
  410. {
  411. brother->RB_COLOR = RED;
  412. brother->left->RB_COLOR = BLACK;
  413. RotateRight(brother);
  414. }
  415. //else if(brother->right->RB_COLOR == RED)
  416. //情况4:x的兄弟w是黑色的,且w的右孩子时红色的。
  417. //{
  418. brother->RB_COLOR = node->parent->RB_COLOR;
  419. node->parent->RB_COLOR = BLACK;
  420. brother->right->RB_COLOR = BLACK;
  421. RotateLeft(node->parent);
  422. node = m_root;
  423. //}
  424. }
  425. }
  426. else //下述情况针对上面的情况1中,node作为右孩子而阐述的。
  427. //22 else (same as then clause with "right" and "left" exchanged)
  428. //同样,原理一致,只是遇到左旋改为右旋,遇到右旋改为左旋,即可。其它代码不变。
  429. {
  430. RB_Node* brother = node->parent->left;
  431. if (brother->RB_COLOR == RED)
  432. {
  433. brother->RB_COLOR = BLACK;
  434. node->parent->RB_COLOR = RED;
  435. RotateRight(node->parent);
  436. }
  437. else
  438. {
  439. if (brother->left->RB_COLOR == BLACK && brother->right->RB_COLOR == BLACK)
  440. {
  441. brother->RB_COLOR = RED;
  442. node = node->parent;
  443. }
  444. else if (brother->left->RB_COLOR == BLACK)
  445. {
  446. brother->RB_COLOR = RED;
  447. brother->right->RB_COLOR = BLACK;
  448. RotateLeft(brother);
  449. }
  450. //else if(brother->left->RB_COLOR==RED)
  451. //{
  452. brother->RB_COLOR = node->parent->RB_COLOR;
  453. node->parent->RB_COLOR = BLACK;
  454. brother->left->RB_COLOR = BLACK;
  455. RotateRight(node->parent);
  456. node = m_root;
  457. //}
  458. }
  459. }
  460. }
  461. m_nullNode->parent = m_root; //最后将node置为根结点,
  462. node->RB_COLOR = BLACK; //并改为黑色。
  463. }
  464. //
  465. inline RB_Node* InOrderPredecessor(RB_Node* node)
  466. {
  467. if (node == m_nullNode) //null node has no predecessor
  468. {
  469. return m_nullNode;
  470. }
  471. RB_Node* result = node->left; //get node's left child
  472. while (result != m_nullNode) //try to find node's left subtree's right most node
  473. {
  474. if (result->right != m_nullNode)
  475. {
  476. result = result->right;
  477. }
  478. else
  479. {
  480. break;
  481. }
  482. } //after while loop result==null or result's right child is null
  483. if (result == m_nullNode)
  484. {
  485. RB_Node* index = node->parent;
  486. result = node;
  487. while (index != m_nullNode && result == index->left)
  488. {
  489. result = index;
  490. index = index->parent;
  491. }
  492. result = index; // first right parent or null
  493. }
  494. return result;
  495. }
  496. //
  497. inline RB_Node* InOrderSuccessor(RB_Node* node)
  498. {
  499. if (node == m_nullNode) //null node has no successor
  500. {
  501. return m_nullNode;
  502. }
  503. RB_Node* result = node->right; //get node's right node
  504. while (result != m_nullNode) //try to find node's right subtree's left most node
  505. {
  506. if (result->left != m_nullNode)
  507. {
  508. result = result->left;
  509. }
  510. else
  511. {
  512. break;
  513. }
  514. } //after while loop result==null or result's left child is null
  515. if (result == m_nullNode)
  516. {
  517. RB_Node* index = node->parent;
  518. result = node;
  519. while (index != m_nullNode && result == index->right)
  520. {
  521. result = index;
  522. index = index->parent;
  523. }
  524. result = index; //first parent's left or null
  525. }
  526. return result;
  527. }
  528. //debug
  529. void InOrderTraverse()
  530. {
  531. InOrderTraverse(m_root);
  532. }
  533. void CreateGraph(string filename)
  534. {
  535. //delete
  536. }
  537. void InOrderCreate(ofstream& file, RB_Node* node)
  538. {
  539. //delete
  540. }
  541. void InOrderTraverse(RB_Node* node)
  542. {
  543. if (node == m_nullNode)
  544. {
  545. return;
  546. }
  547. else
  548. {
  549. InOrderTraverse(node->left);
  550. cout << node->key << endl;
  551. InOrderTraverse(node->right);
  552. }
  553. }
  554. ~RB_Tree()
  555. {
  556. clear(m_root);
  557. delete m_nullNode;
  558. }
  559. private:
  560. // utility function for destructor to destruct object;
  561. void clear(RB_Node* node)
  562. {
  563. if (node == m_nullNode)
  564. {
  565. return;
  566. }
  567. else
  568. {
  569. clear(node->left);
  570. clear(node->right);
  571. delete node;
  572. }
  573. }
  574. private:
  575. RB_Node *m_nullNode;
  576. RB_Node *m_root;
  577. };
  578. #endif /*_RB_TREE_H_*/

RBTree.cpp
  1. //file RBTree.cpp
  2. //written by saturnman,20101008。
  3. //updated by July,20110329。
  4. //所有的头文件都已补齐,现在您可以直接复制此份源码上机验证了(版权所有,侵权必究)。
  5. //July、updated,2011.05.06。
  6. #include<iostream>
  7. #include<algorithm>
  8. #include<iterator>
  9. #include<vector>
  10. #include<sstream>
  11. #include"RBTree.h" //如果.h文件,和cpp文件放在一个文件里,此句去掉
  12. using namespace std;
  13. int main()
  14. {
  15. RB_Tree<int,int> tree;
  16. vector<int> v;
  17. for(int i=0;i<20;++i)
  18. {
  19. v.push_back(i);
  20. }
  21. random_shuffle(v.begin(),v.end());
  22. copy(v.begin(),v.end(),ostream_iterator<int>(cout," "));
  23. cout<<endl;
  24. stringstream sstr;
  25. for(i=0;i<v.size();++i)
  26. {
  27. tree.Insert(v[i],i);
  28. cout<<"insert:"<<v[i]<<endl; //添加结点
  29. }
  30. for(i=0;i<v.size();++i)
  31. {
  32. cout<<"Delete:"<<v[i]<<endl;
  33. tree.Delete(v[i]); //删除结点
  34. tree.InOrderTraverse();
  35. }
  36. cout<<endl;
  37. tree.InOrderTraverse();
  38. return 0;
  39. }

运行效果图(先是一一插入各结点,然后再删除所有的结点):

第二部分、程序有bug?

2.1、红黑树要求绝对平衡么?   

    据网友鑫反馈,上述c++源码虽说从上面的测试结果来看,没有问题。但程序还是有隐藏的bug,下面,分两个步骤再来测试下此段源码:

    1、首先在RBTree.h的最后里添加下述代码:

    2、改写RBTree.cpp文件,如下:

    后经测试,结果,的确有误,即依次插入以下节点,12,1,9,0,2,11,7后,红黑树变为如下:

然后删除根节点9,经过上述程序运行后,运行结果,如下:

即上述运行结果,所对应的红黑树的状态如下(此时,红黑树已经不再平衡,存在的问题确实已经很明显了):

    是的,如你所见,上述程序删除根节点9之后,正确的红黑树的状态应该为7代替根节点9,7成为新的根节点,且节点7着为黑色,而上述结果则是完全错误,红黑树已经完全不平衡。至此,终于发现,此c++程序存在隐藏bug了。至于修正,则还得等一段时间。

 

    说明:此程序的bug是经网友鑫指出的,同时,他还发现,网上不少的程序,都存在这个问题,比如这里:http://sd.csdn.net/a/20110506/297285.html的红黑树的flash演示版本,也存在此类的问题。已在原文下发表了以下评论:

很遗憾,经反复测试,红黑树的flash版本有问题(其它的暂还没发现问题):http://www.cs.usfca.edu/~galles/visualization/flash.html。
如依次往插入这个序列,15,1,9,2,0,12,16,7,11,13,17,14,然后再删除根节点9,严重的错误就出来了。上面的版本只是简单的一个步骤用7代替9,成为根节点,然后把7节点着为黑色。树却没有后续调整,完全不平衡。
特此,把问题指出来,希望,这个红黑树的错误flash版本不致误导更多的人,同时,问题是朋友鑫提出的)。
我会记住这个问题,如果解决了,再发布在博客里。
后续:鑫指出:avl树也有问题。
July、结构之法 算法之道 博主。
2011.05.07。

    但事实是,果真如此么?请看下文2.1节的修正。

2.1、红黑树不要求严格平衡

   修正:本程序没有任何问题。有一点非常之重要,之前就是因为未意识到而造成上述错觉,即:红黑树并非严格意义上的二叉查找树,它只要满足它本身的五点性质即可,不要求严格平衡。所以,上面的例子中,12,1,9,0,2,11,7,然后删除根结点9,只要着色适当,同样不违反红黑树的五点性质。所以,结论是,我庸人自扰了,sorry。

   还是这句话,有任何问题,欢迎任何人提出或指正。

 

第三部分、读者反馈

关于RB_Tree插入删除操作的讨论

July

你好!关于RB_Tree的完整实现代码,你已经在你的博客中写出了。但我认为,你的代码中有需要改正的地方。

起 因

       我这段时间正好在学习RB_Tree,由于我忽略了RB_Tree的性质(3):每个叶子结点都是黑色的,导致我对RB_Tree的操作纠结了好几天。在我还没意识到的时候,偶然间看到你的博客,想从中获得答案。然后就发现其中有值得商榷的地方。

错 误

       下图是你写的插入修正函数InsertFixUp的部分截图:

 你的文章地址:http://blog.csdn.net/v_july_v/article/details/6285620

 

                                                           1

    正如《算法导论》所言,InsertFixUp 中每一次while循环都要面对3种情况:

case 1z的叔叔y是红色的;

case 2z的叔叔y是黑色的,且z是右孩子;

case 3z的叔叔y是黑色的,且z是左孩子.

并且case 2是落在case 3内的,所以这两种情况不是相互排斥的!而在你的代码中,将case 2case 3分别放在ifelse中,导致它们相互独立。这是不对的。

 

修 正

       所以,在图1中“标记①”处的else是不能加的,应将其删除。

       遗憾的是,我认为你的RB_Tree的删除修正操作DeleteFixUp也出现了类似的错误:对于DeleteFixUp所处理的4种情况也同样不是相互排斥的,而你用一组if…else if…else if…case 2, 3, 4全部独立开来。

       以上便是鄙人的一点拙见,如果你认为有错误的地方,欢迎再讨论!

                                    杨 

                                                               CSDN ID: crisischaos

                                                               2011.10.06

    考证:非常感谢杨兄来信指导。从算法导论一书原来的插入情况的修复伪代码来看:

  1. //---------------------插入结点性质修复--------------------------------
  2. //3种插入情况,都在下面的伪代码中(未涉及到所有全部的插入情况)。
  3. /*
  4. RB-INSERT-FIXUP(T, z)
  5. 1 while color[p[z]] = RED
  6. 2 do if p[z] = left[p[p[z]]]
  7. 3 then y ← right[p[p[z]]]
  8. 4 if color[y] = RED
  9. 5 then color[p[z]] ← BLACK ? Case 1
  10. 6 color[y] ← BLACK ? Case 1
  11. 7 color[p[p[z]]] ← RED ? Case 1
  12. 8 z ← p[p[z]] ? Case 1
  13. 9 else if z = right[p[z]]
  14. 10 then z ← p[z] ? Case 2
  15. 11 LEFT-ROTATE(T, z) ? Case 2
  16. 12 color[p[z]] ← BLACK ? Case 3
  17. 13 color[p[p[z]]] ← RED ? Case 3
  18. 14 RIGHT-ROTATE(T, p[p[z]]) ? Case 3
  19. 15 else (same as then clause with "right" and "left" exchanged)
  20. 16 color[root[T]] ← BLACK
  21. */
  22. //然后的工作,就非常简单了,即把上述伪代码改写为下述的c++代码: ....

    确实如杨兄所说,理应如此(包括其后的对删除情况的修复)。日后,再做统一修改,再次谢谢。July、2011.10.06更新。

红黑树系列的前五篇文章:

4、 一步一图一代码,R-B Tree
1、 教你透彻了解红黑树
5、 红黑树插入和删除结点的全程演示
3、 红黑树的c源码实现与剖析
2、 红黑树算法的实现与剖析
6、致谢: http://saturnman.blog.163.com/

完。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/小丑西瓜9/article/detail/246035
推荐阅读
相关标签
  

闽ICP备14008679号