编程练习——红黑树(RedBlackTree)

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

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

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

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

下面是红黑树代码

  1. /*
    • this is red-black-tree code
    • this code is not efficent in inserting
  2. *
    • create by chico chen
    • date: 2008/09/04
    • 如需转载注明出处
  3. */
    1. #include “RBNode.h”
    1. template< class T>
  4. class RBTree
  5. {
    1. private :
  6. RBNode* root;
  7. public :
  8. RBTree()
  9. {
  10. this ->root = NULL;
  11. }
  12. ~RBTree()
  13. {
  14. clearTree( this ->root);
  15. }
        1. void print()
  16. {
  17. print( this ->root,0);
  18. }
            1. void insert(T& data)
  19. {
    1. RBNode* node = new RBNode(data);
  20. insertNode(node);
  21. }
    1. void deleteKey(T& data)
  22. {
  23. deleteNode(data);
  24. }
      1. bool RBTreeTest()
  25. {
  26. try
  27. {
  28. getBlackNum( this ->root);
    1. }
  29. catch (…)
  30. {
  31. return false ;
  32. }
  33. return true ;
  34. }
    1. private :
      1. void print(RBNode* subRoot, int num)
  35. {
  36. if (subRoot != NULL)
  37. {
  38. print(subRoot->right,num+3);
  39. for ( int i = 0; i < num; i++)
  40. {
  41. cout << “ “ ;
  42. }
  43. cout << subRoot->data<< “(“ <color<< “)” <<endl;
  44. print(subRoot->left,num+3);
  45. }
  46. }
    1. void clearTree(RBNode* subRoot)
  47. {
  48. if (subRoot == NULL)
  49. return ;
  50. clearTree(subRoot->left);
  51. clearTree(subRoot->right);
  52. delete subRoot;
  53. }
    1. RBNode deleteMin(RBNode subRoot,RBNode** parent)
  54. {
    1. while (subRoot != NULL)
  55. {
  56. parent = &subRoot;
  57. if (subRoot->right != NULL)
  58. {
  59. subRoot = subRoot->right;
  60. }
  61. else
  62. {
  63. break ;
  64. }
  65. }
  66. return subRoot;
  67. }
    1. void deleteNode(T& data)
  68. {
  69. if (root == NULL)
  70. {
  71. throw “Empty tree” ;
  72. }
  73. RBNode* subRoot = root;
  74. while (subRoot != NULL)
  75. {
  76. if (subRoot->data > data)
  77. {
  78. subRoot = subRoot->left;
  79. }
  80. else if (subRoot->data < data)
  81. {
  82. subRoot = subRoot->right;
  83. }
  84. else
  85. {
  86. // find the data
  87. // use the midOrder last one which is before the data node to replace
  88. RBNode* inParent = subRoot;
  89. RBNode* deleteNode = deleteMin(subRoot->left,&inParent);
  90. RBNode* realDelete = NULL;
  91. if (deleteNode != NULL)
  92. {
  93. subRoot->data = deleteNode->data; // copy
  94. realDelete = deleteNode;
  95. //real delete
  96. }
  97. else
  98. {
  99. realDelete = subRoot;
  100. //real delete
  101. }
  102. if (realDelete->parent == NULL)
  103. {
  104. // delete root
  105. delete realDelete;
  106. }
  107. else
  108. {
  109. // nothing at realDelete->right
  110. RBNode* parent = realDelete->parent;
  111. RBNode* subATree = NULL;
  112. if (parent->left == realDelete)
  113. {
  114. parent->left = realDelete->left;
  115. }
  116. else
  117. {
  118. parent->right = realDelete->left;
  119. }
  120. subATree = realDelete->left;
  121. if (realDelete->left != NULL)
  122. {
  123. realDelete->left->parent = parent;
  124. }
  125. int color = realDelete->color;
  126. delete realDelete;
  127. if (color == BLACK &&
  128. (subATree == NULL || subATree->color == BLACK))
  129. {
      1. deleteRebuild(subATree,parent);
  130. }
  131. else if (color == BLACK && subATree->color == RED)
  132. {
  133. subATree->color = BLACK;
  134. }
  135. else
  136. {
  137. // do nothing
  138. }
  139. break ;
  140. }
    1. }
  141. }
  142. }
      1. /* delete them if you want
  143. *
  144. // x(r) c(r)
  145. // / / / /
  146. // `a(b) b(b) –> x(b) b(b)
  147. // / /
  148. // c(r) a(b)
  149. // LRL means L-> double black is at left, and rotate is RL
  150. RBNode LRLCaseA(RBNode x)
  151. {
  152. RLRotate(x,x->right,x->right->left);
  153. x->color = BLACK;
  154. return x->parent;
    1. }
      1. // x(r) b(r)
  155. // / / / /
  156. // `a(b) b(b) –> x(b) c(b)
  157. // / /
  158. // c(r) a(b)
  159. RBNode LLLCaseA(RBNode x)
  160. {
  161. RRRotate(x,x->right);
  162. x->color = BLACK;
  163. x->parent->color = RED;
  164. x->parent->right->color = BLACK;
  165. return x->parent;
  166. }
    1. // x(r) b(r)
  167. // / / / /
  168. // b(b) `a(b)–> c(b) x(b)
  169. // / /
  170. // c(r) a(b)
  171. RBNode RLLCaseA(RBNode x)
  172. {
  173. LLRotate(x,x->left);
  174. x->color = BLACK;
  175. x->parent->color = RED;
  176. x->parent->left->color = BLACK;
  177. return x->parent;
  178. }
      1. // x(r) c(r)
  179. // / / / /
  180. // b(b) `a(b)–> b(b) x(b)
  181. // / /
  182. // c(r) a(b)
  183. RBNode RLRCaseA(RBNode x)
  184. {
  185. LRRotate(x,x->left,x->left->right);
  186. x->color = BLACK;
    1. return x->parent;
  187. }
      1. // x(r) x(b)
  188. // / / / /
  189. // `a(b) c(b) -> a(b) c(r)
  190. // / / / /
  191. // d(b) e(b) d(b) e(b)
  192. RBNode LCaseB(RBNode x)
  193. {
  194. x->color = BLACK;
  195. x->right->color = RED;
  196. }
    1. // x(r) x(b)
  197. // / / / /
  198. // c(b) `a(b) -> c(r) a(b)
  199. // / / / /
  200. // d(b) e(b) d(b) e(b)
  201. RBNode RCaseB(RBNode x)
  202. {
  203. x->color = BLACK;
  204. x->left->color = RED;
  205. }
    1. // x(b) c(b)
  206. // / / / /
  207. // `a(b) c(r) -> x(r) e(b)
  208. // / / / /
  209. // d(b) e(b) `a(b) d(b)
  210. RBNode LCaseC(RBNode x)
  211. {
  212. RRRotate(x,x->right);
  213. x->color = RED;
  214. x->parent->color = BLACK;
  215. return x->parent;
  216. }
    1. // x(b) c(b)
  217. // / / / /
  218. // c(r) `a(b) -> d(b) x(r)
  219. // / / / /
  220. // d(b) e(b) e(b) `a(b)
  221. RBNode RCaseC(RBNode x)
  222. {
  223. LLRotate(x,x->left);
  224. x->color = RED;
  225. x->parent->color = BLACK;
  226. return x->parent;
  227. }
  228. *
  229. */
    1. bool isBlack(RBNode* node)
  230. {
    1. if (node == NULL || node->color == BLACK)
  231. return true ;
  232. return false ;
  233. }
    1. void rebuild(RBNode* node)
  234. {
  235. if (node->parent->data > node->data)
  236. {
  237. node->parent->left = node;
  238. }
  239. else
  240. {
  241. node->parent->right = node;
  242. }
  243. }
      1. /*
    • There are 9 cases we will meet. The cases of the double black node at the right is ignored.
    • (b) means black node, (db) means double black node, (r) means red node
      1. (b) 2 (b) 3 (b)
    • / / / / / /
    • (db) (b) (db) (b) (db) (b)
    • / / / / / /
    • (b) (b) (r) (b) (b) (r)
  244. *
      1. (b) 5 (b) 6 (r)
    • / / / / / /
    • (db) (b) (db) (r) (db) (b)
    • / / / / / /
    • (r) (r) (b) (b) (b) (b)
  245. *
      1. (r) 8 (r) 9 (r)
    • / / / / / /
    • (db) (b) (db) (b) (db) (b)
    • / / / / / /
    • (r) (b) (b) (r) (r) (r)
  246. *
    • case 1,6: up the black, if the parent is black then call the function again until the
    • double black node is root, else blacken the parent.
    • case 2,4,7,9: call the RLRotate, if the parent of the double
    • node is black, up the black and call the function again, else
    • blacken the parent.
    • case 3,8: call the LLRotate, the same as case 2.
    • case 5: call LLRotate, change as (b) then end.
    • / /
    • (b) (b)
    • / /
    • (b) (r)
  247. *
  248. */
  249. void deleteRebuild(RBNode node,RBNode parent)
  250. {
  251. if (parent == NULL)
  252. {
  253. // root, delete the black
  254. return ;
  255. }
  256. if (parent->left == node)
  257. {
  258. RBNode* brother = parent->right;
  259. RBNode* nephewA = brother->left;
  260. RBNode* nephewB = brother->right;
    1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
  261. {
  262. // case 1,6
  263. brother->color = RED;
  264. if (parent->color == BLACK)
  265. {
  266. deleteRebuild(parent,parent->parent);
  267. }
  268. else
  269. {
  270. parent->color = BLACK;
  271. return ;
  272. }
    1. }
    1. else if (!isBlack(nephewA))
  273. {
  274. // case 2,4,7,9
  275. RBNode* tempRoot = RLRotate(parent,brother,nephewA);
  276. // rebuild
  277. rebuild(tempRoot);
    1. }
  278. else if (!isBlack(nephewB))
  279. {
  280. // case 3,8
  281. RBNode* tempRoot = RRRotate(parent,brother);
  282. rebuild(tempRoot);
  283. nephewB->color = BLACK;
  284. brother->color = RED;
  285. }
  286. else if (!isBlack(brother))
  287. {
  288. // case 5
  289. RBNode* tempRoot = RRRotate(parent,brother);
  290. rebuild(tempRoot);
  291. brother->color = BLACK;
  292. nephewA->color = RED;
  293. return ;
  294. }
  295. else
  296. {
  297. // unknown
  298. throw “none excption, about there is no red or black” ;
  299. }
    1. if (parent->color == BLACK)
  300. {
  301. // case 2,3,4
  302. deleteRebuild(parent,parent->parent);
  303. }
  304. else
  305. {
  306. // case 7,8,9
  307. parent->color = BLACK;
  308. }
    1. }
  309. else
  310. {
  311. RBNode* brother = parent->left;
  312. RBNode* nephewA = brother->right;
  313. RBNode* nephewB = brother->left;
    1. if (isBlack(nephewA) && isBlack(nephewB) && isBlack(brother))
  314. {
  315. brother->color = RED;
  316. if (parent->color == BLACK)
  317. {
  318. deleteRebuild(parent,parent->parent);
  319. }
  320. else
  321. {
  322. parent->color = BLACK;
  323. return ;
  324. }
  325. }
  326. else if (!isBlack(nephewA))
  327. {
  328. RBNode* tempRoot = LRRotate(parent,brother,nephewA);
  329. // rebuild
  330. rebuild(tempRoot);
    1. }
  331. else if (!isBlack(nephewB))
  332. {
  333. RBNode* tempRoot = LLRotate(parent,brother);
  334. rebuild(tempRoot);
  335. nephewB->color = BLACK;
  336. brother->color = RED;
  337. }
  338. else if (!isBlack(brother))
  339. {
  340. RBNode* tempRoot = LLRotate(parent,brother);
  341. rebuild(tempRoot);
  342. nephewA->color = RED;
  343. brother->color = BLACK;
  344. return ;
  345. }
  346. else
  347. {
  348. throw “none excption, about there is no red or black” ;
  349. }
    1. if (parent->color == BLACK)
  350. {
  351. deleteRebuild(parent,parent->parent);
  352. }
  353. else
  354. {
  355. parent->color = BLACK;
  356. }
    1. }
    1. }
      1. void insertNode(RBNode* node)
  357. {
    1. if (root == NULL)
  358. {
  359. root = node;
  360. node->color = BLACK;
  361. return ;
  362. }
  363. RBNode* subRoot = root;
  364. RBNode* insertPoint = NULL;
  365. while (subRoot!=NULL)
  366. {
  367. insertPoint = subRoot;
  368. if (subRoot->data > node->data)
  369. {
  370. // insert left
  371. subRoot = subRoot->left;
    1. }
  372. else if (subRoot->data < node->data)
  373. {
  374. subRoot = subRoot->right;
  375. }
  376. else
  377. {
  378. throw “same key” ;
  379. }
  380. }
      1. if (insertPoint->data > node->data)
  381. {
  382. insertPoint->left = node;
  383. }
  384. else
  385. {
  386. insertPoint->right = node;
  387. }
  388. node->parent = insertPoint;
      1. insertRebuild(node);
    1. }
    1. // return the subRoot
  389. // a b
  390. // / / /
  391. // b -> c a
  392. // /
  393. // c
  394. RBNode LLRotate(RBNode a, RBNode* b)
  395. {
  396. if (b->right != NULL)
  397. {
  398. b->right->parent = a;
    1. }
  399. a->left = b->right;
  400. b->right = a;
  401. b->parent = a->parent;
  402. a->parent = b;
  403. return b;
  404. }
    1. // return the subRoot
  405. // a b
  406. // / / /
  407. // b -> a c
  408. // /
  409. // c
  410. RBNode RRRotate(RBNode a, RBNode* b)
  411. {
  412. if (b->left != NULL)
  413. {
  414. b->left->parent = a;
    1. }
  415. a->right = b->left;
  416. b->left = a;
  417. b->parent = a->parent;
  418. a->parent = b;
      1. return b;
  419. }
      1. // return the subRoot
  420. // a c
  421. // / / /
  422. // b -> a b
  423. // / /
  424. // c d
  425. // /
  426. // d
  427. RBNode RLRotate(RBNode a, RBNode b, RBNode c)
  428. {
    1. if (c->right != NULL)
  429. {
  430. c->right->parent = b;
    1. }
  431. b->left = c->right;
  432. c->right = b;
  433. b->parent = c;
  434. if (c->left != NULL)
  435. {
  436. c->left->parent = a;
    1. }
  437. a->right = c->left;
  438. c->left = a;
  439. c->parent = a->parent;
  440. a->parent = c;
    1. return c;
  441. }
    1. // return the subRoot
  442. // a c
  443. // / / /
  444. // b -> b a
  445. // / /
  446. // c d
  447. // /
  448. // d
  449. RBNode LRRotate(RBNode a, RBNode b, RBNode c)
  450. {
  451. if (c->left != NULL)
  452. {
  453. c->left->parent = b;
      1. }
  454. b->right = c->left;
  455. c->left = b;
  456. b->parent = c;
  457. if (c->right!= NULL)
  458. {
  459. c->right->parent = a;
    1. }
  460. a->left = c->right;
  461. c->right = a;
  462. c->parent = a->parent;
  463. a->parent = c;
    1. return c;
  464. }
    1. // node is not the root
  465. void insertRebuild(RBNode* node)
  466. {
  467. RBNode* parent = NULL;
  468. RBNode* grandParent = NULL;
  469. while (node->parent != NULL)
  470. {
  471. parent = node->parent;
    1. if (parent->color == RED) // here means there must be a grandparent
  472. {
  473. grandParent = parent->parent;
  474. grandParent->color = BLACK;
    1. if (grandParent->left == parent)
  475. {
  476. if (parent->left == node)
  477. {
  478. //LLRotate
  479. node->color = BLACK;
  480. node = LLRotate(grandParent,parent);
    1. }
  481. else
  482. {
  483. //LRRotate
  484. parent->color = BLACK;
  485. node = LRRotate(grandParent,parent,node);
    1. }
    1. }
  486. else
  487. {
    1. if (parent->left == node)
  488. {
  489. //RLRotate
  490. parent->color = BLACK;
  491. node = RLRotate(grandParent,parent,node);
  492. }
  493. else
  494. {
  495. //RRRotate
  496. node->color = BLACK;
  497. node = RRRotate(grandParent,parent);
  498. }
  499. }
  500. }
  501. else
  502. {
  503. break ;
  504. }
  505. }
    1. if (node->parent == NULL)
  506. {
  507. node->color = BLACK;
  508. this ->root = node;
  509. }
  510. else
  511. {
  512. rebuild(node);
  513. /*if(node->parent->data > node->data)
  514. {
  515. node->parent->left = node;
  516. }
  517. else
  518. {
  519. node->parent->right = node;
  520. }*/
  521. }
  522. }
          1. int getBlackNum(RBNode* subRoot)
  523. {
  524. if (subRoot == NULL)
  525. {
  526. return 1;
  527. }
  528. int left = getBlackNum(subRoot->left);
  529. int right = getBlackNum(subRoot->right);
  530. if (left != right)
  531. {
  532. throw “wrong” ;
  533. }
  534. if (subRoot->color == BLACK)
  535. {
    1. return 1+left;
  536. }
  537. else
  538. {
  539. return left;
  540. }
    1. }
  541. };
  • 本文作者: 帐前卒
  • 本文链接: http://chillyc.info/2008/2905246/
  • 版权声明: 本博客所有文章除特别声明外,只能复制超链接地址,且必须注明出处!