red_black_tree.c 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567
  1. /**********************************************************
  2. * See the LICENSE file for copyright information. *
  3. **********************************************************/
  4. #include "config.h"
  5. #include <assert.h>
  6. #include <rbtree/red_black_tree.h>
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. /***********************************************************************/
  10. /* FUNCTION: RBTreeCreate */
  11. /**/
  12. /* INPUTS: All the inputs are names of functions. CompFunc takes to */
  13. /* void pointers to keys and returns 1 if the first argument is */
  14. /* "greater than" the second. DestFunc takes a pointer to a key and */
  15. /* destroys it in the appropriate manner when the node containing that */
  16. /* key is deleted. */
  17. /**/
  18. /* OUTPUT: This function returns a pointer to the newly created */
  19. /* red-black tree. */
  20. /**/
  21. /* Modifies Input: none */
  22. /***********************************************************************/
  23. rb_red_blk_tree* RBTreeCreate( int (*CompFunc) (const void*,const void*),
  24. void (*DestFunc)(void *)) {
  25. rb_red_blk_tree* newTree = NULL;
  26. rb_red_blk_node* temp;
  27. newTree= malloc(sizeof(rb_red_blk_tree));
  28. if (newTree == NULL) {
  29. return NULL;
  30. }
  31. newTree->nil = newTree->root = NULL;
  32. newTree->Compare= CompFunc;
  33. newTree->DestroyKey= DestFunc;
  34. /* see the comment in the rb_red_blk_tree structure in red_black_tree.h */
  35. /* for information on nil and root */
  36. temp=newTree->nil= malloc(sizeof(rb_red_blk_node));
  37. if (temp == NULL) {
  38. free(newTree);
  39. return NULL;
  40. }
  41. temp->parent=temp->left=temp->right=temp;
  42. temp->red=0;
  43. temp->key=0;
  44. temp=newTree->root= malloc(sizeof(rb_red_blk_node));
  45. if (temp == NULL) {
  46. free(newTree->nil);
  47. free(newTree);
  48. return NULL;
  49. }
  50. temp->parent=temp->left=temp->right=newTree->nil;
  51. temp->key=0;
  52. temp->red=0;
  53. return newTree;
  54. }
  55. /***********************************************************************/
  56. /* FUNCTION: LeftRotate */
  57. /**/
  58. /* INPUTS: This takes a tree so that it can access the appropriate */
  59. /* root and nil pointers, and the node to rotate on. */
  60. /**/
  61. /* OUTPUT: None */
  62. /**/
  63. /* Modifies Input: tree, x */
  64. /**/
  65. /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
  66. /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
  67. /* makes the parent of x be to the left of x, x the parent of */
  68. /* its parent before the rotation and fixes other pointers */
  69. /* accordingly. */
  70. /***********************************************************************/
  71. static void LeftRotate(rb_red_blk_tree* tree, rb_red_blk_node* x) {
  72. rb_red_blk_node* y;
  73. rb_red_blk_node* nil=tree->nil;
  74. /* I originally wrote this function to use the sentinel for */
  75. /* nil to avoid checking for nil. However this introduces a */
  76. /* very subtle bug because sometimes this function modifies */
  77. /* the parent pointer of nil. This can be a problem if a */
  78. /* function which calls LeftRotate also uses the nil sentinel */
  79. /* and expects the nil sentinel's parent pointer to be unchanged */
  80. /* after calling this function. For example, when RBDeleteFixUP */
  81. /* calls LeftRotate it expects the parent pointer of nil to be */
  82. /* unchanged. */
  83. y=x->right;
  84. x->right=y->left;
  85. if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
  86. /* and do an unconditional assignment instead of testing for nil */
  87. y->parent=x->parent;
  88. /* instead of checking if x->parent is the root as in the book, we */
  89. /* count on the root sentinel to implicitly take care of this case */
  90. if( x == x->parent->left) {
  91. x->parent->left=y;
  92. } else {
  93. x->parent->right=y;
  94. }
  95. y->left=x;
  96. x->parent=y;
  97. assert(!tree->nil->red && "nil not red in LeftRotate");
  98. }
  99. /***********************************************************************/
  100. /* FUNCTION: RighttRotate */
  101. /**/
  102. /* INPUTS: This takes a tree so that it can access the appropriate */
  103. /* root and nil pointers, and the node to rotate on. */
  104. /**/
  105. /* OUTPUT: None */
  106. /**/
  107. /* Modifies Input?: tree, y */
  108. /**/
  109. /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
  110. /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
  111. /* makes the parent of x be to the left of x, x the parent of */
  112. /* its parent before the rotation and fixes other pointers */
  113. /* accordingly. */
  114. /***********************************************************************/
  115. static void RightRotate(rb_red_blk_tree* tree, rb_red_blk_node* y) {
  116. rb_red_blk_node* x;
  117. rb_red_blk_node* nil=tree->nil;
  118. /* I originally wrote this function to use the sentinel for */
  119. /* nil to avoid checking for nil. However this introduces a */
  120. /* very subtle bug because sometimes this function modifies */
  121. /* the parent pointer of nil. This can be a problem if a */
  122. /* function which calls LeftRotate also uses the nil sentinel */
  123. /* and expects the nil sentinel's parent pointer to be unchanged */
  124. /* after calling this function. For example, when RBDeleteFixUP */
  125. /* calls LeftRotate it expects the parent pointer of nil to be */
  126. /* unchanged. */
  127. x=y->left;
  128. y->left=x->right;
  129. if (nil != x->right) x->right->parent=y; /*used to use sentinel here */
  130. /* and do an unconditional assignment instead of testing for nil */
  131. /* instead of checking if x->parent is the root as in the book, we */
  132. /* count on the root sentinel to implicitly take care of this case */
  133. x->parent=y->parent;
  134. if( y == y->parent->left) {
  135. y->parent->left=x;
  136. } else {
  137. y->parent->right=x;
  138. }
  139. x->right=y;
  140. y->parent=x;
  141. assert(!tree->nil->red && "nil not red in RightRotate");
  142. }
  143. /***********************************************************************/
  144. /* FUNCTION: TreeInsertHelp */
  145. /**/
  146. /* INPUTS: tree is the tree to insert into and z is the node to insert */
  147. /**/
  148. /* OUTPUT: none */
  149. /**/
  150. /* Modifies Input: tree, z */
  151. /**/
  152. /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
  153. /* using the algorithm described in _Introduction_To_Algorithms_ */
  154. /* by Cormen et al. This function is only intended to be called */
  155. /* by the RBTreeInsert function and not by the user */
  156. /***********************************************************************/
  157. static void TreeInsertHelp(rb_red_blk_tree* tree, rb_red_blk_node* z) {
  158. /* This function should only be called by InsertRBTree (see above) */
  159. rb_red_blk_node* x;
  160. rb_red_blk_node* y;
  161. rb_red_blk_node* nil=tree->nil;
  162. z->left=z->right=nil;
  163. y=tree->root;
  164. x=tree->root->left;
  165. while( x != nil) {
  166. y=x;
  167. if (1 == tree->Compare(x->key,z->key)) { /* x.key > z.key */
  168. x=x->left;
  169. } else { /* x,key <= z.key */
  170. x=x->right;
  171. }
  172. }
  173. z->parent=y;
  174. if ( (y == tree->root) ||
  175. (1 == tree->Compare(y->key,z->key))) { /* y.key > z.key */
  176. y->left=z;
  177. } else {
  178. y->right=z;
  179. }
  180. assert(!tree->nil->red && "nil not red in TreeInsertHelp");
  181. }
  182. /* Before calling Insert RBTree the node x should have its key set */
  183. /***********************************************************************/
  184. /* FUNCTION: RBTreeInsert */
  185. /**/
  186. /* INPUTS: tree is the red-black tree to insert a node which has a key */
  187. /* pointed to by key. */
  188. /**/
  189. /* OUTPUT: This function returns a pointer to the newly inserted node */
  190. /* which is guarunteed to be valid until this node is deleted. */
  191. /* What this means is if another data structure stores this */
  192. /* pointer then the tree does not need to be searched when this */
  193. /* is to be deleted. */
  194. /**/
  195. /* Modifies Input: tree */
  196. /**/
  197. /* EFFECTS: Creates a node node which contains the appropriate key */
  198. /* pointer and inserts it into the tree. */
  199. /***********************************************************************/
  200. rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key) {
  201. rb_red_blk_node * y;
  202. rb_red_blk_node * x;
  203. rb_red_blk_node * newNode;
  204. x= malloc(sizeof(rb_red_blk_node));
  205. if (x == NULL) {
  206. return NULL;
  207. }
  208. x->key=key;
  209. TreeInsertHelp(tree,x);
  210. newNode=x;
  211. x->red=1;
  212. while(x->parent->red) { /* use sentinel instead of checking for root */
  213. if (x->parent == x->parent->parent->left) {
  214. y=x->parent->parent->right;
  215. if (y->red) {
  216. x->parent->red=0;
  217. y->red=0;
  218. x->parent->parent->red=1;
  219. x=x->parent->parent;
  220. } else {
  221. if (x == x->parent->right) {
  222. x=x->parent;
  223. LeftRotate(tree,x);
  224. }
  225. x->parent->red=0;
  226. x->parent->parent->red=1;
  227. RightRotate(tree,x->parent->parent);
  228. }
  229. } else { /* case for x->parent == x->parent->parent->right */
  230. y=x->parent->parent->left;
  231. if (y->red) {
  232. x->parent->red=0;
  233. y->red=0;
  234. x->parent->parent->red=1;
  235. x=x->parent->parent;
  236. } else {
  237. if (x == x->parent->left) {
  238. x=x->parent;
  239. RightRotate(tree,x);
  240. }
  241. x->parent->red=0;
  242. x->parent->parent->red=1;
  243. LeftRotate(tree,x->parent->parent);
  244. }
  245. }
  246. }
  247. tree->root->left->red=0;
  248. return newNode;
  249. }
  250. /***********************************************************************/
  251. /* FUNCTION: TreeSuccessor */
  252. /**/
  253. /* INPUTS: tree is the tree in question, and x is the node we want the */
  254. /* the successor of. */
  255. /**/
  256. /* OUTPUT: This function returns the successor of x or NULL if no */
  257. /* successor exists. */
  258. /**/
  259. /* Modifies Input: none */
  260. /**/
  261. /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
  262. /***********************************************************************/
  263. rb_red_blk_node* TreeSuccessor(rb_red_blk_tree* tree,rb_red_blk_node* x) {
  264. rb_red_blk_node* y;
  265. rb_red_blk_node* nil=tree->nil;
  266. rb_red_blk_node* root=tree->root;
  267. if (nil != (y = x->right)) { /* assignment to y is intentional */
  268. while(y->left != nil) { /* returns the minium of the right subtree of x */
  269. y=y->left;
  270. }
  271. return y;
  272. } else {
  273. y=x->parent;
  274. while(x == y->right) { /* sentinel used instead of checking for nil */
  275. x=y;
  276. y=y->parent;
  277. }
  278. if (y == root) return nil;
  279. return y;
  280. }
  281. }
  282. /***********************************************************************/
  283. /* FUNCTION: Treepredecessor */
  284. /**/
  285. /* INPUTS: tree is the tree in question, and x is the node we want the */
  286. /* the predecessor of. */
  287. /**/
  288. /* OUTPUT: This function returns the predecessor of x or NULL if no */
  289. /* predecessor exists. */
  290. /**/
  291. /* Modifies Input: none */
  292. /**/
  293. /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
  294. /***********************************************************************/
  295. rb_red_blk_node* TreePredecessor(rb_red_blk_tree* tree, rb_red_blk_node* x) {
  296. rb_red_blk_node* y;
  297. rb_red_blk_node* nil=tree->nil;
  298. rb_red_blk_node* root=tree->root;
  299. if (nil != (y = x->left)) { /* assignment to y is intentional */
  300. while(y->right != nil) { /* returns the maximum of the left subtree of x */
  301. y=y->right;
  302. }
  303. return y;
  304. } else {
  305. y=x->parent;
  306. while(x == y->left) {
  307. if (y == root) return nil;
  308. x=y;
  309. y=y->parent;
  310. }
  311. return y;
  312. }
  313. }
  314. /***********************************************************************/
  315. /* FUNCTION: TreeDestHelper */
  316. /**/
  317. /* INPUTS: tree is the tree to destroy and x is the current node */
  318. /**/
  319. /* OUTPUT: none */
  320. /**/
  321. /* EFFECTS: This function recursively destroys the nodes of the tree */
  322. /* postorder using the DestroyKey and DestroyInfo functions. */
  323. /**/
  324. /* Modifies Input: tree, x */
  325. /**/
  326. /* Note: This function should only be called by RBTreeDestroy */
  327. /***********************************************************************/
  328. static void TreeDestHelper(rb_red_blk_tree* tree, rb_red_blk_node* x) {
  329. rb_red_blk_node* nil=tree->nil;
  330. if (x != nil) {
  331. TreeDestHelper(tree,x->left);
  332. TreeDestHelper(tree,x->right);
  333. tree->DestroyKey(x->key);
  334. free(x);
  335. }
  336. }
  337. /***********************************************************************/
  338. /* FUNCTION: RBTreeDestroy */
  339. /**/
  340. /* INPUTS: tree is the tree to destroy */
  341. /**/
  342. /* OUTPUT: none */
  343. /**/
  344. /* EFFECT: Destroys the key and frees memory */
  345. /**/
  346. /* Modifies Input: tree */
  347. /**/
  348. /***********************************************************************/
  349. void RBTreeDestroy(rb_red_blk_tree* tree) {
  350. TreeDestHelper(tree,tree->root->left);
  351. free(tree->root);
  352. free(tree->nil);
  353. free(tree);
  354. }
  355. /***********************************************************************/
  356. /* FUNCTION: RBExactQuery */
  357. /**/
  358. /* INPUTS: tree is the tree to print and q is a pointer to the key */
  359. /* we are searching for */
  360. /**/
  361. /* OUTPUT: returns the a node with key equal to q. If there are */
  362. /* multiple nodes with key equal to q this function returns */
  363. /* the one highest in the tree */
  364. /**/
  365. /* Modifies Input: none */
  366. /**/
  367. /***********************************************************************/
  368. rb_red_blk_node* RBExactQuery(rb_red_blk_tree* tree, void* q) {
  369. rb_red_blk_node* x=tree->root->left;
  370. rb_red_blk_node* nil=tree->nil;
  371. int compVal;
  372. if (x == nil) return 0;
  373. compVal = tree->Compare(x->key, q);
  374. while(0 != compVal) {/*assignemnt*/
  375. if (1 == compVal) { /* x->key > q */
  376. x=x->left;
  377. } else {
  378. x=x->right;
  379. }
  380. if ( x == nil) return 0;
  381. compVal = tree->Compare(x->key, q);
  382. }
  383. return x;
  384. }
  385. /***********************************************************************/
  386. /* FUNCTION: RBDeleteFixUp */
  387. /**/
  388. /* INPUTS: tree is the tree to fix and x is the child of the spliced */
  389. /* out node in RBTreeDelete. */
  390. /**/
  391. /* OUTPUT: none */
  392. /**/
  393. /* EFFECT: Performs rotations and changes colors to restore red-black */
  394. /* properties after a node is deleted */
  395. /**/
  396. /* Modifies Input: tree, x */
  397. /**/
  398. /* The algorithm from this function is from _Introduction_To_Algorithms_ */
  399. /***********************************************************************/
  400. static void RBDeleteFixUp(rb_red_blk_tree* tree, rb_red_blk_node* x) {
  401. rb_red_blk_node* root=tree->root->left;
  402. rb_red_blk_node* w;
  403. while( (!x->red) && (root != x)) {
  404. if (x == x->parent->left) {
  405. w=x->parent->right;
  406. if (w->red) {
  407. w->red=0;
  408. x->parent->red=1;
  409. LeftRotate(tree,x->parent);
  410. w=x->parent->right;
  411. }
  412. if ( (!w->right->red) && (!w->left->red) ) {
  413. w->red=1;
  414. x=x->parent;
  415. } else {
  416. if (!w->right->red) {
  417. w->left->red=0;
  418. w->red=1;
  419. RightRotate(tree,w);
  420. w=x->parent->right;
  421. }
  422. w->red=x->parent->red;
  423. x->parent->red=0;
  424. w->right->red=0;
  425. LeftRotate(tree,x->parent);
  426. x=root; /* this is to exit while loop */
  427. }
  428. } else { // the code below has left and right switched from above
  429. w=x->parent->left;
  430. if (w->red) {
  431. w->red=0;
  432. x->parent->red=1;
  433. RightRotate(tree,x->parent);
  434. w=x->parent->left;
  435. }
  436. if ( (!w->right->red) && (!w->left->red) ) {
  437. w->red=1;
  438. x=x->parent;
  439. } else {
  440. if (!w->left->red) {
  441. w->right->red=0;
  442. w->red=1;
  443. LeftRotate(tree,w);
  444. w=x->parent->left;
  445. }
  446. w->red=x->parent->red;
  447. x->parent->red=0;
  448. w->left->red=0;
  449. RightRotate(tree,x->parent);
  450. x=root; /* this is to exit while loop */
  451. }
  452. }
  453. }
  454. x->red=0;
  455. assert(!tree->nil->red && "nil not black in RBDeleteFixUp");
  456. }
  457. /***********************************************************************/
  458. /* FUNCTION: RBDelete */
  459. /**/
  460. /* INPUTS: tree is the tree to delete node z from */
  461. /**/
  462. /* OUTPUT: none */
  463. /**/
  464. /* EFFECT: Deletes z from tree and frees the key of z */
  465. /* using DestroyKey. Then calls */
  466. /* RBDeleteFixUp to restore red-black properties */
  467. /**/
  468. /* Modifies Input: tree, z */
  469. /**/
  470. /* The algorithm from this function is from _Introduction_To_Algorithms_ */
  471. /***********************************************************************/
  472. void RBDelete(rb_red_blk_tree* tree, rb_red_blk_node* z){
  473. rb_red_blk_node* y;
  474. rb_red_blk_node* x;
  475. rb_red_blk_node* nil=tree->nil;
  476. rb_red_blk_node* root=tree->root;
  477. y= ((z->left == nil) || (z->right == nil)) ? z : TreeSuccessor(tree,z);
  478. x= (y->left == nil) ? y->right : y->left;
  479. if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
  480. root->left=x;
  481. } else {
  482. if (y == y->parent->left) {
  483. y->parent->left=x;
  484. } else {
  485. y->parent->right=x;
  486. }
  487. }
  488. if (y != z) { /* y should not be nil in this case */
  489. assert(y!=tree->nil && "y is nil in RBDelete");
  490. /* y is the node to splice out and x is its child */
  491. if (!(y->red)) RBDeleteFixUp(tree,x);
  492. tree->DestroyKey(z->key);
  493. y->left=z->left;
  494. y->right=z->right;
  495. y->parent=z->parent;
  496. y->red=z->red;
  497. z->left->parent=z->right->parent=y;
  498. if (z == z->parent->left) {
  499. z->parent->left=y;
  500. } else {
  501. z->parent->right=y;
  502. }
  503. free(z);
  504. } else {
  505. tree->DestroyKey(y->key);
  506. if (!(y->red)) RBDeleteFixUp(tree,x);
  507. free(y);
  508. }
  509. assert(!tree->nil->red && "nil not black in RBDelete");
  510. }