编程练习——红黑树（RedBlackTree）

Posted on Edited on Word count in article: 10k Reading time ≈ 9 mins.

在网上搜索了很多红黑树的资源，发现自己看代码的能力还是有些欠缺。很多都看不懂，后来找到一篇英文红黑树文献，终于弄明白了红黑树的删除插入是怎么做的。但是那片文
献好像还有些漏洞，其中有一种删除情况，他并没有考虑到。如果大家想看的话可以搜索下 “red-black trees” ,由 prof. Lyn
Turbak所写。因为时间关系，插入算法只是实现了非CLR算法。删除算法我也不知道叫什么名字(文献里没有讲)。但是删除结果依旧符合红黑树。

建立红黑树节点的时候，考虑到因为经常要和一个节点的父亲节点打交道，所以采用了在节点里添加父亲节点的指针的方法。这样即方便也提高效率。另外也好调试。如果一味采
用递归…估计人会看疯掉的。插入的时候，采用的是先插入删除的时候红色节点，然后在判断是否违反红红条件。违反的话就左旋右旋进行调整。否则就插入成功。删除的时候
先删除节点，这个过程和删除二叉查找树节点一致。删除时要看真正要删除的节点是否是根节点，是否是黑色节点。因为红色节点和根节点删除不会调整树形。如果删除的是黑色
节点，那么要看替换他的节点（这里的替换一定是左子树树根，因为如果有右子树，那么被删除的也不会是这个节点，记住二叉查找树的删除过程）是否是黑色节点（这里如果左
子树为空，那他也是黑色节点）。如果是黑色节点，那么一定要调整树的结构，否则就直接染色。调整树结构时要考虑的情况就非常多了。一共有9种情况需要考虑。

下面是代码部分，删除时如何调整在代码注释中。至于insert操作，看看文献就应该会做了。

  1. /*
  2. * create RBNode class for construction RBTree
  3. * create by chico chen
  4. * date: 2008/09/04
  5. * 如需转载注明出处
  6. */
    1. template< class T>
  8. #define RED 0
  9. #define BLACK 1
  10. class RBNode
  11. {
  12. public :
    1. T data;
  14. RBNode* left;
  15. RBNode* right;
  16. RBNode* parent;
  17. int color;
    1. RBNode(T& data)
  19. {
  20. this ->data = data;
  21. left = NULL;
  22. right = NULL;
  23. parent = NULL;
  24. color = RED;
  25. }
  26. RBNode(T& data, RBNode* left, RBNode* right, RBNode* parent)
  27. {
  28. this ->data = data;
  29. this ->left = left;
  30. this ->right = right;
  31. this ->parent = parent;
  32. color = RED;
  33. }
    1. ~RBNode()
  35. {
  36. this ->left = this ->right = this ->parent = NULL;
  37. color = RED;
  38. }
  39. };

下面是红黑树代码

  1. /*
  2. * this is red-black-tree code
  3. * this code is not efficent in inserting
  5. * create by chico chen
  6. * date: 2008/09/04
  7. * 如需转载注明出处
  8. */
    1. #include “RBNode.h”
    1. template< class T>
  11. class RBTree
  12. {
    1. private :
  14. RBNode* root;
  15. public :
  16. RBTree()
  17. {
  18. this ->root = NULL;
  19. }
  20. ~RBTree()
  21. {
  22. clearTree( this ->root);
  23. }
        1. void print()
  25. {
  26. print( this ->root,0);
  27. }
            1. void insert(T& data)
  29. {
    1. RBNode* node = new RBNode(data);
  31. insertNode(node);
  32. }
    1. void deleteKey(T& data)
  34. {
  35. deleteNode(data);
  36. }
      1. bool RBTreeTest()
  38. {
  39. try
  40. {
  41. getBlackNum( this ->root);
    1. }
  43. catch (…)
  44. {
  45. return false ;
  46. }
  47. return true ;
  48. }
    1. private :
      1. void print(RBNode* subRoot, int num)
  51. {
  52. if (subRoot != NULL)
  53. {
  54. print(subRoot->right,num+3);
  55. for ( int i = 0; i < num; i++)
  56. {
  57. cout << " " ;
  58. }
  59. cout << subRoot->data<< “(” <color<< “)” <<endl;
  60. print(subRoot->left,num+3);
  61. }
  62. }
    1. void clearTree(RBNode* subRoot)
  64. {
  65. if (subRoot == NULL)
  66. return ;
  67. clearTree(subRoot->left);
  68. clearTree(subRoot->right);
  69. delete subRoot;
  70. }
    1. RBNode* deleteMin(RBNode* subRoot,RBNode** parent)
  72. {
    1. while (subRoot != NULL)
  74. {
  75. parent = &subRoot;
  76. if (subRoot->right != NULL)
  77. {
  78. subRoot = subRoot->right;
  79. }
  80. else
  81. {
  82. break ;
  83. }
  84. }
  85. return subRoot;
  86. }
    1. void deleteNode(T& data)
  88. {
  89. if (root == NULL)
  90. {
  91. throw “Empty tree” ;
  92. }
  93. RBNode* subRoot = root;
  94. while (subRoot != NULL)
  95. {
  96. if (subRoot->data > data)
  97. {
  98. subRoot = subRoot->left;
  99. }
  100. else if (subRoot->data < data)
  101. {
  102. subRoot = subRoot->right;
  103. }
  104. else
  105. {
  106. // find the data
  107. // use the midOrder last one which is before the data node to replace
  108. RBNode* inParent = subRoot;
  109. RBNode* deleteNode = deleteMin(subRoot->left,&inParent);
  110. RBNode* realDelete = NULL;
  111. if (deleteNode != NULL)
  112. {
  113. subRoot->data = deleteNode->data; // copy
  114. realDelete = deleteNode;
  115. //real delete
  116. }
  117. else
  118. {
  119. realDelete = subRoot;
  120. //real delete
  121. }
  122. if (realDelete->parent == NULL)
  123. {
  124. // delete root
  125. delete realDelete;
  126. }
  127. else
  128. {
  129. // nothing at realDelete->right
  130. RBNode* parent = realDelete->parent;
  131. RBNode* subATree = NULL;
  132. if (parent->left == realDelete)
  133. {
  134. parent->left = realDelete->left;
  135. }
  136. else
  137. {
  138. parent->right = realDelete->left;
  139. }
  140. subATree = realDelete->left;
  141. if (realDelete->left != NULL)
  142. {
  143. realDelete->left->parent = parent;
  144. }
  145. int color = realDelete->color;
  146. delete realDelete;
  147. if (color == BLACK &&
  148. (subATree == NULL || subATree->color == BLACK))
  149. {
      1. deleteRebuild(subATree,parent);
  151. }
  152. else if (color == BLACK && subATree->color == RED)
  153. {
  154. subATree->color = BLACK;
  155. }
  156. else
  157. {
  158. // do nothing
  159. }
  160. break ;
  161. }
    1. }
  163. }
  164. }
      1. /* delete them if you want
  167. //     x®                c®
  168. //     /  /                /  /
  169. //   `a(b) b(b) -->     x(b)   b(b)
  170. //         /            /
  171. //        c®         a(b)
  172. // LRL means L-> double black is at left, and rotate is RL
  173. RBNode* LRLCaseA(RBNode* x)
  174. {
  175. RLRotate(x,x->right,x->right->left);
  176. x->color = BLACK;
  177. return x->parent;
    1. }
      1. //     x®                 b®
  180. //     /  /                 /  /
  181. //   `a(b) b(b)   -->    x(b)   c(b)
  182. //          /             /
  183. //           c®       a(b)
  184. RBNode* LLLCaseA(RBNode* x)
  185. {
  186. RRRotate(x,x->right);
  187. x->color = BLACK;
  188. x->parent->color = RED;
  189. x->parent->right->color = BLACK;
  190. return x->parent;
  191. }
    1. //     x®                b®
  193. //     /  /                /  /
  194. //   b(b) `a(b)–>       c(b) x(b)
  195. //    /                         /
  196. //  c®                        a(b)
  197. RBNode* RLLCaseA(RBNode* x)
  198. {
  199. LLRotate(x,x->left);
  200. x->color = BLACK;
  201. x->parent->color = RED;
  202. x->parent->left->color = BLACK;
  203. return x->parent;
  204. }
      1. //     x®                c®
  206. //     /  /                /  /
  207. //   b(b) `a(b)–>       b(b) x(b)
  208. //    /                         /
  209. //    c®                        a(b)
  210. RBNode* RLRCaseA(RBNode* x)
  211. {
  212. LRRotate(x,x->left,x->left->right);
  213. x->color = BLACK;
    1. return x->parent;
  215. }
      1. //     x®                     x(b)
  217. //     /  /                     /  /
  218. //   `a(b) c(b)        ->     a(b) c®
  219. //         /   /                  /   /
  220. //        d(b)  e(b)            d(b)  e(b)
  221. RBNode* LCaseB(RBNode* x)
  222. {
  223. x->color = BLACK;
  224. x->right->color = RED;
  225. }
    1. //     x®                     x(b)
  227. //     /  /                     /  /
  228. //    c(b) `a(b)       ->     c® a(b)
  229. //   /   /                   /   /
  230. // d(b)  e(b)              d(b)  e(b)
  231. RBNode* RCaseB(RBNode* x)
  232. {
  233. x->color = BLACK;
  234. x->left->color = RED;
  235. }
    1. //     x(b)                    c(b)
  237. //     /  /                    /  /
  238. //  `a(b)  c®      ->     x®  e(b)
  239. //        /   /             /  /
  240. //       d(b)  e(b)      `a(b)  d(b)
  241. RBNode* LCaseC(RBNode* x)
  242. {
  243. RRRotate(x,x->right);
  244. x->color = RED;
  245. x->parent->color = BLACK;
  246. return  x->parent;
  247. }
    1. //     x(b)                    c(b)
  249. //     /  /                    /  /
  250. //   c® `a(b)     ->       d(b) x®
  251. //   /   /                        /  /
  252. //  d(b)  e(b)                  e(b) `a(b)
  253. RBNode* RCaseC(RBNode* x)
  254. {
  255. LLRotate(x,x->left);
  256. x->color = RED;
  257. x->parent->color = BLACK;
  258. return  x->parent;
  259. }
  261. */
    1. bool isBlack(RBNode* node)
  263. {
    1. if (node == NULL || node->color == BLACK)
  265. return true ;
  266. return false ;
  267. }
    1. void rebuild(RBNode* node)
  269. {
  270. if (node->parent->data > node->data)
  271. {
  272. node->parent->left = node;
  273. }
  274. else
  275. {
  276. node->parent->right = node;
  277. }
  278. }
      1. /*
  280. * There are 9 cases we will meet. The cases of the double black node at the right is ignored.
  281. * (b) means black node, (db) means double black node, ® means red node
  282. * 1.    (b)              2   (b)           3 (b)
  283. *      /   /                 /  /            /  /
  284. *    (db)  (b)             (db)  (b)       (db)  (b)
  285. *          /  /                  / /             / /
  286. *         (b)  (b)             ®  (b)        (b)  ®
  288. * 4.    (b)              5   (b)           6 ®
  289. *      /   /                 /  /            /  /
  290. *    (db)  (b)             (db)  ®       (db)  (b)
  291. *          /  /                  / /             / /
  292. *         ®  ®             (b)  (b)        (b)  (b)
  294. * 7.    ®              8   ®           9 ®
  295. *      /   /                 /  /            /  /
  296. *    (db)  (b)             (db)  (b)       (db)  (b)
  297. *          /  /                  / /             / /
  298. *         ®  (b)             (b)  ®        ®  ®
  300. * case 1,6: up the black, if the parent is black then call the function again until the
  301. * double black node is root, else blacken the parent.
  302. * case 2,4,7,9: call the RLRotate, if the parent of the double
  303. * node is black, up the black and call the function again, else
  304. * blacken the parent.
  305. * case 3,8: call the LLRotate, the same as case 2.
  306. * case 5: call LLRotate, change as    (b)   then end.
  307. *                                    /   /
  308. *                                  (b)    (b)
  309. *                                  / /
  310. *                                (b)  ®
  312. */
  313. void deleteRebuild(RBNode* node,RBNode* parent)
  314. {
  315. if (parent == NULL)
  316. {
  317. // root, delete the black
  318. return ;
  319. }
  320. if (parent->left == node)
  321. {
  322. RBNode* brother = parent->right;
  323. RBNode* nephewA = brother->left;
  324. RBNode* nephewB = brother->right;
    1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
  326. {
  327. // case 1,6
  328. brother->color = RED;
  329. if (parent->color == BLACK)
  330. {
  331. deleteRebuild(parent,parent->parent);
  332. }
  333. else
  334. {
  335. parent->color = BLACK;
  336. return ;
  337. }
    1. }
    1. else if (!isBlack(nephewA))
  340. {
  341. // case 2,4,7,9
  342. RBNode* tempRoot = RLRotate(parent,brother,nephewA);
  343. // rebuild
  344. rebuild(tempRoot);
    1. }
  346. else if (!isBlack(nephewB))
  347. {
  348. // case 3,8
  349. RBNode* tempRoot = RRRotate(parent,brother);
  350. rebuild(tempRoot);
  351. nephewB->color = BLACK;
  352. brother->color = RED;
  353. }
  354. else if (!isBlack(brother))
  355. {
  356. // case 5
  357. RBNode* tempRoot = RRRotate(parent,brother);
  358. rebuild(tempRoot);
  359. brother->color = BLACK;
  360. nephewA->color = RED;
  361. return ;
  362. }
  363. else
  364. {
  365. // unknown
  366. throw “none excption, about there is no red or black” ;
  367. }
    1. if (parent->color == BLACK)
  369. {
  370. // case 2,3,4
  371. deleteRebuild(parent,parent->parent);
  372. }
  373. else
  374. {
  375. // case 7,8,9
  376. parent->color = BLACK;
  377. }
    1. }
  379. else
  380. {
  381. RBNode* brother = parent->left;
  382. RBNode* nephewA = brother->right;
  383. RBNode* nephewB = brother->left;
    1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
  385. {
  386. brother->color = RED;
  387. if (parent->color == BLACK)
  388. {
  389. deleteRebuild(parent,parent->parent);
  390. }
  391. else
  392. {
  393. parent->color = BLACK;
  394. return ;
  395. }
  396. }
  397. else if (!isBlack(nephewA))
  398. {
  399. RBNode* tempRoot = LRRotate(parent,brother,nephewA);
  400. // rebuild
  401. rebuild(tempRoot);
    1. }
  403. else if (!isBlack(nephewB))
  404. {
  405. RBNode* tempRoot = LLRotate(parent,brother);
  406. rebuild(tempRoot);
  407. nephewB->color = BLACK;
  408. brother->color = RED;
  409. }
  410. else if (!isBlack(brother))
  411. {
  412. RBNode* tempRoot = LLRotate(parent,brother);
  413. rebuild(tempRoot);
  414. nephewA->color = RED;
  415. brother->color = BLACK;
  416. return ;
  417. }
  418. else
  419. {
  420. throw “none excption, about there is no red or black” ;
  421. }
    1. if (parent->color == BLACK)
  423. {
  424. deleteRebuild(parent,parent->parent);
  425. }
  426. else
  427. {
  428. parent->color = BLACK;
  429. }
    1. }
    1. }
      1. void insertNode(RBNode* node)
  433. {
    1. if (root == NULL)
  435. {
  436. root = node;
  437. node->color = BLACK;
  438. return ;
  439. }
  440. RBNode* subRoot = root;
  441. RBNode* insertPoint = NULL;
  442. while (subRoot!=NULL)
  443. {
  444. insertPoint = subRoot;
  445. if (subRoot->data > node->data)
  446. {
  447. // insert left
  448. subRoot = subRoot->left;
    1. }
  450. else if (subRoot->data < node->data)
  451. {
  452. subRoot = subRoot->right;
  453. }
  454. else
  455. {
  456. throw “same key” ;
  457. }
  458. }
      1. if (insertPoint->data > node->data)
  460. {
  461. insertPoint->left = node;
  462. }
  463. else
  464. {
  465. insertPoint->right = node;
  466. }
  467. node->parent = insertPoint;
      1. insertRebuild(node);
    1. }
    1. // return the subRoot
  471. //        a                   b
  472. //       /                  /   /
  473. //      b        ->        c     a
  474. //     /
  475. //    c
  476. RBNode* LLRotate(RBNode* a, RBNode* b)
  477. {
  478. if (b->right != NULL)
  479. {
  480. b->right->parent = a;
    1. }
  482. a->left = b->right;
  483. b->right = a;
  484. b->parent = a->parent;
  485. a->parent = b;
  486. return b;
  487. }
    1. // return the subRoot
  489. //        a                      b
  490. //          /                  /   /
  491. //            b        ->     a     c
  492. //              /
  493. //                c
  494. RBNode* RRRotate(RBNode* a, RBNode* b)
  495. {
  496. if (b->left != NULL)
  497. {
  498. b->left->parent = a;
    1. }
  500. a->right = b->left;
  501. b->left = a;
  502. b->parent = a->parent;
  503. a->parent = b;
      1. return b;
  505. }
      1. // return the subRoot
  507. //        a                      c
  508. //          /                  /   /
  509. //            b        ->     a     b
  510. //           /                 /
  511. //          c                   d
  512. //         /
  513. //        d
  514. RBNode* RLRotate(RBNode* a, RBNode* b, RBNode* c)
  515. {
    1. if (c->right != NULL)
  517. {
  518. c->right->parent = b;
    1. }
  520. b->left = c->right;
  521. c->right = b;
  522. b->parent = c;
  523. if (c->left != NULL)
  524. {
  525. c->left->parent = a;
    1. }
  527. a->right = c->left;
  528. c->left = a;
  529. c->parent = a->parent;
  530. a->parent = c;
    1. return c;
  532. }
    1. // return the subRoot
  534. //        a                      c
  535. //       /                     /   /
  536. //      b              ->     b     a
  537. //       /                         /
  538. //        c                       d
  539. //         /
  540. //          d
  541. RBNode* LRRotate(RBNode* a, RBNode* b, RBNode* c)
  542. {
  543. if (c->left != NULL)
  544. {
  545. c->left->parent = b;
      1. }
  547. b->right = c->left;
  548. c->left = b;
  549. b->parent = c;
  550. if (c->right!= NULL)
  551. {
  552. c->right->parent = a;
    1. }
  554. a->left = c->right;
  555. c->right = a;
  556. c->parent = a->parent;
  557. a->parent = c;
    1. return c;
  559. }
    1. // node is not the root
  561. void insertRebuild(RBNode* node)
  562. {
  563. RBNode* parent = NULL;
  564. RBNode* grandParent = NULL;
  565. while (node->parent != NULL)
  566. {
  567. parent = node->parent;
    1. if (parent->color == RED) // here means there must be a grandparent
  569. {
  570. grandParent = parent->parent;
  571. grandParent->color = BLACK;
    1. if (grandParent->left == parent)
  573. {
  574. if (parent->left == node)
  575. {
  576. //LLRotate
  577. node->color = BLACK;
  578. node = LLRotate(grandParent,parent);
    1. }
  580. else
  581. {
  582. //LRRotate
  583. parent->color = BLACK;
  584. node = LRRotate(grandParent,parent,node);
    1. }
    1. }
  587. else
  588. {
    1. if (parent->left == node)
  590. {
  591. //RLRotate
  592. parent->color = BLACK;
  593. node = RLRotate(grandParent,parent,node);
  594. }
  595. else
  596. {
  597. //RRRotate
  598. node->color = BLACK;
  599. node = RRRotate(grandParent,parent);
  600. }
  601. }
  602. }
  603. else
  604. {
  605. break ;
  606. }
  607. }
    1. if (node->parent == NULL)
  609. {
  610. node->color = BLACK;
  611. this ->root = node;
  612. }
  613. else
  614. {
  615. rebuild(node);
  616. /*if(node->parent->data > node->data)
  617. {
  618. node->parent->left = node;
  619. }
  620. else
  621. {
  622. node->parent->right = node;
  623. }*/
  624. }
  625. }
          1. int getBlackNum(RBNode* subRoot)
  627. {
  628. if (subRoot == NULL)
  629. {
  630. return 1;
  631. }
  632. int left = getBlackNum(subRoot->left);
  633. int right = getBlackNum(subRoot->right);
  634. if (left != right)
  635. {
  636. throw “wrong” ;
  637. }
  638. if (subRoot->color == BLACK)
  639. {
    1. return 1+left;
  641. }
  642. else
  643. {
  644. return left;
  645. }
    1. }
  647. };