Graphviz  2.41.20170921.2350
red_black_tree.c
Go to the documentation of this file.
1 /* $Id$Revision: */
2 /* vim:set shiftwidth=4 ts=8: */
3 
4 /**********************************************************
5 * See the LICENSE file for copyright information. *
6 **********************************************************/
7 
8 #include "config.h"
9 
10 #include "red_black_tree.h"
11 #include "stdio.h"
12 
13 /***********************************************************************/
14 /* FUNCTION: RBTreeCreate */
15 
16 /* INPUTS: All the inputs are names of functions. CompFunc takes to */
17 /* void pointers to keys and returns 1 if the first argument is */
18 /* "greater than" the second. DestFunc takes a pointer to a key and */
19 /* destroys it in the appropriate manner when the node containing that */
20 /* key is deleted. InfoDestFunc is similar to DestFunc except it */
21 /* receives a pointer to the info of a node and destroys it. */
22 /* PrintFunc receives a pointer to the key of a node and prints it. */
23 /* PrintInfo receives a pointer to the info of a node and prints it. */
24 /* If RBTreePrint is never called the print functions don't have to be */
25 /* defined and NullFunction can be used. */
26 
27 /* OUTPUT: This function returns a pointer to the newly created */
28 /* red-black tree. */
29 
30 /* Modifies Input: none */
31 /***********************************************************************/
32 
33 rb_red_blk_tree* RBTreeCreate( int (*CompFunc) (const void*,const void*),
34  void (*DestFunc) (void*),
35  void (*InfoDestFunc) (void*),
36  void (*PrintFunc) (const void*),
37  void (*PrintInfo)(void*)) {
38  rb_red_blk_tree* newTree = NULL;
39  rb_red_blk_node* temp;
40 
41  if (setjmp(rb_jbuf)) {
42  if (newTree) {
43  if (newTree->nil) free (newTree->nil);
44  free (newTree);
45  }
46  return NULL;
47  }
48  newTree=(rb_red_blk_tree*) SafeMalloc(sizeof(rb_red_blk_tree));
49  newTree->nil = newTree->root = NULL;
50  newTree->Compare= CompFunc;
51  newTree->DestroyKey= DestFunc;
52  newTree->PrintKey= PrintFunc;
53  newTree->PrintInfo= PrintInfo;
54  newTree->DestroyInfo= InfoDestFunc;
55 
56  /* see the comment in the rb_red_blk_tree structure in red_black_tree.h */
57  /* for information on nil and root */
58  temp=newTree->nil= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
59  temp->parent=temp->left=temp->right=temp;
60  temp->red=0;
61  temp->key=0;
62  temp=newTree->root= (rb_red_blk_node*) SafeMalloc(sizeof(rb_red_blk_node));
63  temp->parent=temp->left=temp->right=newTree->nil;
64  temp->key=0;
65  temp->red=0;
66  return(newTree);
67 }
68 
69 /***********************************************************************/
70 /* FUNCTION: LeftRotate */
71 
72 /* INPUTS: This takes a tree so that it can access the appropriate */
73 /* root and nil pointers, and the node to rotate on. */
74 
75 /* OUTPUT: None */
76 
77 /* Modifies Input: tree, x */
78 
79 /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
80 /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
81 /* makes the parent of x be to the left of x, x the parent of */
82 /* its parent before the rotation and fixes other pointers */
83 /* accordingly. */
84 /***********************************************************************/
85 
87  rb_red_blk_node* y;
88  rb_red_blk_node* nil=tree->nil;
89 
90  /* I originally wrote this function to use the sentinel for */
91  /* nil to avoid checking for nil. However this introduces a */
92  /* very subtle bug because sometimes this function modifies */
93  /* the parent pointer of nil. This can be a problem if a */
94  /* function which calls LeftRotate also uses the nil sentinel */
95  /* and expects the nil sentinel's parent pointer to be unchanged */
96  /* after calling this function. For example, when RBDeleteFixUP */
97  /* calls LeftRotate it expects the parent pointer of nil to be */
98  /* unchanged. */
99 
100  y=x->right;
101  x->right=y->left;
102 
103  if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
104  /* and do an unconditional assignment instead of testing for nil */
105 
106  y->parent=x->parent;
107 
108  /* instead of checking if x->parent is the root as in the book, we */
109  /* count on the root sentinel to implicitly take care of this case */
110  if( x == x->parent->left) {
111  x->parent->left=y;
112  } else {
113  x->parent->right=y;
114  }
115  y->left=x;
116  x->parent=y;
117 
118 #ifdef DEBUG_ASSERT
119  Assert(!tree->nil->red,"nil not red in LeftRotate");
120 #endif
121 }
122 
123 
124 /***********************************************************************/
125 /* FUNCTION: RighttRotate */
126 
127 /* INPUTS: This takes a tree so that it can access the appropriate */
128 /* root and nil pointers, and the node to rotate on. */
129 
130 /* OUTPUT: None */
131 
132 /* Modifies Input?: tree, y */
133 
134 /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
135 /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
136 /* makes the parent of x be to the left of x, x the parent of */
137 /* its parent before the rotation and fixes other pointers */
138 /* accordingly. */
139 /***********************************************************************/
140 
142  rb_red_blk_node* x;
143  rb_red_blk_node* nil=tree->nil;
144 
145  /* I originally wrote this function to use the sentinel for */
146  /* nil to avoid checking for nil. However this introduces a */
147  /* very subtle bug because sometimes this function modifies */
148  /* the parent pointer of nil. This can be a problem if a */
149  /* function which calls LeftRotate also uses the nil sentinel */
150  /* and expects the nil sentinel's parent pointer to be unchanged */
151  /* after calling this function. For example, when RBDeleteFixUP */
152  /* calls LeftRotate it expects the parent pointer of nil to be */
153  /* unchanged. */
154 
155  x=y->left;
156  y->left=x->right;
157 
158  if (nil != x->right) x->right->parent=y; /*used to use sentinel here */
159  /* and do an unconditional assignment instead of testing for nil */
160 
161  /* instead of checking if x->parent is the root as in the book, we */
162  /* count on the root sentinel to implicitly take care of this case */
163  x->parent=y->parent;
164  if( y == y->parent->left) {
165  y->parent->left=x;
166  } else {
167  y->parent->right=x;
168  }
169  x->right=y;
170  y->parent=x;
171 
172 #ifdef DEBUG_ASSERT
173  Assert(!tree->nil->red,"nil not red in RightRotate");
174 #endif
175 }
176 
177 /***********************************************************************/
178 /* FUNCTION: TreeInsertHelp */
179 
180 /* INPUTS: tree is the tree to insert into and z is the node to insert */
181 
182 /* OUTPUT: none */
183 
184 /* Modifies Input: tree, z */
185 
186 /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
187 /* using the algorithm described in _Introduction_To_Algorithms_ */
188 /* by Cormen et al. This function is only intended to be called */
189 /* by the RBTreeInsert function and not by the user */
190 /***********************************************************************/
191 
193  /* This function should only be called by InsertRBTree (see above) */
194  rb_red_blk_node* x;
195  rb_red_blk_node* y;
196  rb_red_blk_node* nil=tree->nil;
197 
198  z->left=z->right=nil;
199  y=tree->root;
200  x=tree->root->left;
201  while( x != nil) {
202  y=x;
203  if (1 == tree->Compare(x->key,z->key)) { /* x.key > z.key */
204  x=x->left;
205  } else { /* x,key <= z.key */
206  x=x->right;
207  }
208  }
209  z->parent=y;
210  if ( (y == tree->root) ||
211  (1 == tree->Compare(y->key,z->key))) { /* y.key > z.key */
212  y->left=z;
213  } else {
214  y->right=z;
215  }
216 
217 #ifdef DEBUG_ASSERT
218  Assert(!tree->nil->red,"nil not red in TreeInsertHelp");
219 #endif
220 }
221 
222 /* Before calling Insert RBTree the node x should have its key set */
223 
224 /***********************************************************************/
225 /* FUNCTION: RBTreeInsert */
226 
227 /* INPUTS: tree is the red-black tree to insert a node which has a key */
228 /* pointed to by key and info pointed to by info. */
229 
230 /* OUTPUT: This function returns a pointer to the newly inserted node */
231 /* which is guarunteed to be valid until this node is deleted. */
232 /* What this means is if another data structure stores this */
233 /* pointer then the tree does not need to be searched when this */
234 /* is to be deleted. */
235 
236 /* Modifies Input: tree */
237 
238 /* EFFECTS: Creates a node node which contains the appropriate key and */
239 /* info pointers and inserts it into the tree. */
240 /***********************************************************************/
241 
242 rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key, void* info) {
243  rb_red_blk_node * y;
244  rb_red_blk_node * x;
245  rb_red_blk_node * newNode;
246 
247  if (setjmp(rb_jbuf))
248  return NULL;
250  x->key=key;
251  x->info=info;
252 
253  TreeInsertHelp(tree,x);
254  newNode=x;
255  x->red=1;
256  while(x->parent->red) { /* use sentinel instead of checking for root */
257  if (x->parent == x->parent->parent->left) {
258  y=x->parent->parent->right;
259  if (y->red) {
260  x->parent->red=0;
261  y->red=0;
262  x->parent->parent->red=1;
263  x=x->parent->parent;
264  } else {
265  if (x == x->parent->right) {
266  x=x->parent;
267  LeftRotate(tree,x);
268  }
269  x->parent->red=0;
270  x->parent->parent->red=1;
271  RightRotate(tree,x->parent->parent);
272  }
273  } else { /* case for x->parent == x->parent->parent->right */
274  y=x->parent->parent->left;
275  if (y->red) {
276  x->parent->red=0;
277  y->red=0;
278  x->parent->parent->red=1;
279  x=x->parent->parent;
280  } else {
281  if (x == x->parent->left) {
282  x=x->parent;
283  RightRotate(tree,x);
284  }
285  x->parent->red=0;
286  x->parent->parent->red=1;
287  LeftRotate(tree,x->parent->parent);
288  }
289  }
290  }
291  tree->root->left->red=0;
292  return(newNode);
293 
294 #ifdef DEBUG_ASSERT
295  Assert(!tree->nil->red,"nil not red in RBTreeInsert");
296  Assert(!tree->root->red,"root not red in RBTreeInsert");
297 #endif
298 }
299 
300 /***********************************************************************/
301 /* FUNCTION: TreeSuccessor */
302 
303 /* INPUTS: tree is the tree in question, and x is the node we want the */
304 /* the successor of. */
305 
306 /* OUTPUT: This function returns the successor of x or NULL if no */
307 /* successor exists. */
308 
309 /* Modifies Input: none */
310 
311 /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
312 /***********************************************************************/
313 
315  rb_red_blk_node* y;
316  rb_red_blk_node* nil=tree->nil;
317  rb_red_blk_node* root=tree->root;
318 
319  if (nil != (y = x->right)) { /* assignment to y is intentional */
320  while(y->left != nil) { /* returns the minium of the right subtree of x */
321  y=y->left;
322  }
323  return(y);
324  } else {
325  y=x->parent;
326  while(x == y->right) { /* sentinel used instead of checking for nil */
327  x=y;
328  y=y->parent;
329  }
330  if (y == root) return(nil);
331  return(y);
332  }
333 }
334 
335 /***********************************************************************/
336 /* FUNCTION: Treepredecessor */
337 
338 /* INPUTS: tree is the tree in question, and x is the node we want the */
339 /* the predecessor of. */
340 
341 /* OUTPUT: This function returns the predecessor of x or NULL if no */
342 /* predecessor exists. */
343 
344 /* Modifies Input: none */
345 
346 /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
347 /***********************************************************************/
348 
350  rb_red_blk_node* y;
351  rb_red_blk_node* nil=tree->nil;
352  rb_red_blk_node* root=tree->root;
353 
354  if (nil != (y = x->left)) { /* assignment to y is intentional */
355  while(y->right != nil) { /* returns the maximum of the left subtree of x */
356  y=y->right;
357  }
358  return(y);
359  } else {
360  y=x->parent;
361  while(x == y->left) {
362  if (y == root) return(nil);
363  x=y;
364  y=y->parent;
365  }
366  return(y);
367  }
368 }
369 
370 /***********************************************************************/
371 /* FUNCTION: InorderTreePrint */
372 
373 /* INPUTS: tree is the tree to print and x is the current inorder node */
374 
375 /* OUTPUT: none */
376 
377 /* EFFECTS: This function recursively prints the nodes of the tree */
378 /* inorder using the PrintKey and PrintInfo functions. */
379 
380 /* Modifies Input: none */
381 
382 /* Note: This function should only be called from RBTreePrint */
383 /***********************************************************************/
384 
386  rb_red_blk_node* nil=tree->nil;
387  rb_red_blk_node* root=tree->root;
388  if (x != tree->nil) {
389  InorderTreePrint(tree,x->left);
390  printf("info=");
391  tree->PrintInfo(x->info);
392  printf(" key=");
393  tree->PrintKey(x->key);
394  printf(" l->key=");
395  if( x->left == nil) printf("NULL"); else tree->PrintKey(x->left->key);
396  printf(" r->key=");
397  if( x->right == nil) printf("NULL"); else tree->PrintKey(x->right->key);
398  printf(" p->key=");
399  if( x->parent == root) printf("NULL"); else tree->PrintKey(x->parent->key);
400  printf(" red=%i\n",x->red);
401  InorderTreePrint(tree,x->right);
402  }
403 }
404 
405 
406 /***********************************************************************/
407 /* FUNCTION: TreeDestHelper */
408 
409 /* INPUTS: tree is the tree to destroy and x is the current node */
410 
411 /* OUTPUT: none */
412 
413 /* EFFECTS: This function recursively destroys the nodes of the tree */
414 /* postorder using the DestroyKey and DestroyInfo functions. */
415 
416 /* Modifies Input: tree, x */
417 
418 /* Note: This function should only be called by RBTreeDestroy */
419 /***********************************************************************/
420 
422  rb_red_blk_node* nil=tree->nil;
423  if (x != nil) {
424  TreeDestHelper(tree,x->left);
425  TreeDestHelper(tree,x->right);
426  tree->DestroyKey(x->key);
427  tree->DestroyInfo(x->info);
428  free(x);
429  }
430 }
431 
432 
433 /***********************************************************************/
434 /* FUNCTION: RBTreeDestroy */
435 
436 /* INPUTS: tree is the tree to destroy */
437 
438 /* OUTPUT: none */
439 
440 /* EFFECT: Destroys the key and frees memory */
441 
442 /* Modifies Input: tree */
443 
444 /***********************************************************************/
445 
447  TreeDestHelper(tree,tree->root->left);
448  free(tree->root);
449  free(tree->nil);
450  free(tree);
451 }
452 
453 
454 /***********************************************************************/
455 /* FUNCTION: RBTreePrint */
456 
457 /* INPUTS: tree is the tree to print */
458 
459 /* OUTPUT: none */
460 
461 /* EFFECT: This function recursively prints the nodes of the tree */
462 /* inorder using the PrintKey and PrintInfo functions. */
463 
464 /* Modifies Input: none */
465 
466 /***********************************************************************/
467 
469  InorderTreePrint(tree,tree->root->left);
470 }
471 
472 
473 /***********************************************************************/
474 /* FUNCTION: RBExactQuery */
475 
476 /* INPUTS: tree is the tree to print and q is a pointer to the key */
477 /* we are searching for */
478 
479 /* OUTPUT: returns the a node with key equal to q. If there are */
480 /* multiple nodes with key equal to q this function returns */
481 /* the one highest in the tree */
482 
483 /* Modifies Input: none */
484 
485 /***********************************************************************/
486 
488  rb_red_blk_node* x=tree->root->left;
489  rb_red_blk_node* nil=tree->nil;
490  int compVal;
491  if (x == nil) return(0);
492  compVal=tree->Compare(x->key,(int*) q);
493  while(0 != compVal) {/*assignemnt*/
494  if (1 == compVal) { /* x->key > q */
495  x=x->left;
496  } else {
497  x=x->right;
498  }
499  if ( x == nil) return(0);
500  compVal=tree->Compare(x->key,(int*) q);
501  }
502  return(x);
503 }
504 
505 
506 /***********************************************************************/
507 /* FUNCTION: RBDeleteFixUp */
508 
509 /* INPUTS: tree is the tree to fix and x is the child of the spliced */
510 /* out node in RBTreeDelete. */
511 
512 /* OUTPUT: none */
513 
514 /* EFFECT: Performs rotations and changes colors to restore red-black */
515 /* properties after a node is deleted */
516 
517 /* Modifies Input: tree, x */
518 
519 /* The algorithm from this function is from _Introduction_To_Algorithms_ */
520 /***********************************************************************/
521 
523  rb_red_blk_node* root=tree->root->left;
524  rb_red_blk_node* w;
525 
526  while( (!x->red) && (root != x)) {
527  if (x == x->parent->left) {
528  w=x->parent->right;
529  if (w->red) {
530  w->red=0;
531  x->parent->red=1;
532  LeftRotate(tree,x->parent);
533  w=x->parent->right;
534  }
535  if ( (!w->right->red) && (!w->left->red) ) {
536  w->red=1;
537  x=x->parent;
538  } else {
539  if (!w->right->red) {
540  w->left->red=0;
541  w->red=1;
542  RightRotate(tree,w);
543  w=x->parent->right;
544  }
545  w->red=x->parent->red;
546  x->parent->red=0;
547  w->right->red=0;
548  LeftRotate(tree,x->parent);
549  x=root; /* this is to exit while loop */
550  }
551  } else { /* the code below is has left and right switched from above */
552  w=x->parent->left;
553  if (w->red) {
554  w->red=0;
555  x->parent->red=1;
556  RightRotate(tree,x->parent);
557  w=x->parent->left;
558  }
559  if ( (!w->right->red) && (!w->left->red) ) {
560  w->red=1;
561  x=x->parent;
562  } else {
563  if (!w->left->red) {
564  w->right->red=0;
565  w->red=1;
566  LeftRotate(tree,w);
567  w=x->parent->left;
568  }
569  w->red=x->parent->red;
570  x->parent->red=0;
571  w->left->red=0;
572  RightRotate(tree,x->parent);
573  x=root; /* this is to exit while loop */
574  }
575  }
576  }
577  x->red=0;
578 
579 #ifdef DEBUG_ASSERT
580  Assert(!tree->nil->red,"nil not black in RBDeleteFixUp");
581 #endif
582 }
583 
584 
585 /***********************************************************************/
586 /* FUNCTION: RBDelete */
587 
588 /* INPUTS: tree is the tree to delete node z from */
589 
590 /* OUTPUT: none */
591 
592 /* EFFECT: Deletes z from tree and frees the key and info of z */
593 /* using DestoryKey and DestoryInfo. Then calls */
594 /* RBDeleteFixUp to restore red-black properties */
595 
596 /* Modifies Input: tree, z */
597 
598 /* The algorithm from this function is from _Introduction_To_Algorithms_ */
599 /***********************************************************************/
600 
602  rb_red_blk_node* y;
603  rb_red_blk_node* x;
604  rb_red_blk_node* nil=tree->nil;
605  rb_red_blk_node* root=tree->root;
606 
607  y= ((z->left == nil) || (z->right == nil)) ? z : TreeSuccessor(tree,z);
608  x= (y->left == nil) ? y->right : y->left;
609  if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
610  root->left=x;
611  } else {
612  if (y == y->parent->left) {
613  y->parent->left=x;
614  } else {
615  y->parent->right=x;
616  }
617  }
618  if (y != z) { /* y should not be nil in this case */
619 
620 #ifdef DEBUG_ASSERT
621  Assert( (y!=tree->nil),"y is nil in RBDelete\n");
622 #endif
623  /* y is the node to splice out and x is its child */
624 
625  if (!(y->red)) RBDeleteFixUp(tree,x);
626 
627  tree->DestroyKey(z->key);
628  tree->DestroyInfo(z->info);
629  y->left=z->left;
630  y->right=z->right;
631  y->parent=z->parent;
632  y->red=z->red;
633  z->left->parent=z->right->parent=y;
634  if (z == z->parent->left) {
635  z->parent->left=y;
636  } else {
637  z->parent->right=y;
638  }
639  free(z);
640  } else {
641  tree->DestroyKey(y->key);
642  tree->DestroyInfo(y->info);
643  if (!(y->red)) RBDeleteFixUp(tree,x);
644  free(y);
645  }
646 
647 #ifdef DEBUG_ASSERT
648  Assert(!tree->nil->red,"nil not black in RBDelete");
649 #endif
650 }
651 
652 
653 /***********************************************************************/
654 /* FUNCTION: RBEnumerate */
655 
656 /* INPUTS: tree is the tree to look for keys >= low */
657 /* and <= high with respect to the Compare function */
658 
659 /* OUTPUT: stack containing pointers to the nodes between [low,high] */
660 
661 /* Modifies Input: none */
662 /***********************************************************************/
663 
664 stk_stack* RBEnumerate(rb_red_blk_tree* tree, void* low, void* high) {
665  stk_stack* enumResultStack;
666  rb_red_blk_node* nil=tree->nil;
667  rb_red_blk_node* x=tree->root->left;
668  rb_red_blk_node* lastBest=nil;
669 
670  if (setjmp(rb_jbuf)) {
671  return NULL;
672  }
673  enumResultStack=StackCreate();
674  while(nil != x) {
675  if ( 1 == (tree->Compare(x->key,high)) ) { /* x->key > high */
676  x=x->left;
677  } else {
678  lastBest=x;
679  x=x->right;
680  }
681  }
682  while ( (lastBest != nil) && (1 != tree->Compare(low,lastBest->key))) {
683  StackPush(enumResultStack,lastBest);
684  lastBest=TreePredecessor(tree,lastBest);
685  }
686  return(enumResultStack);
687 }
688 
689 
690 
691 
692 
693 
694 
void(* DestroyKey)(void *a)
struct rb_red_blk_node * parent
jmp_buf rb_jbuf
Definition: misc.c:13
void RightRotate(rb_red_blk_tree *tree, rb_red_blk_node *y)
rb_red_blk_node * nil
rb_red_blk_node * RBTreeInsert(rb_red_blk_tree *tree, void *key, void *info)
void TreeInsertHelp(rb_red_blk_tree *tree, rb_red_blk_node *z)
void StackPush(stk_stack *theStack, DATA_TYPE newInfoPointer)
Definition: stack.c:37
void LeftRotate(rb_red_blk_tree *tree, rb_red_blk_node *x)
void(* PrintKey)(const void *a)
rb_red_blk_node * TreeSuccessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
void Assert(int assertion, char *error)
Definition: misc.c:33
int(* Compare)(const void *a, const void *b)
void RBDelete(rb_red_blk_tree *tree, rb_red_blk_node *z)
void(* DestroyInfo)(void *a)
stk_stack * RBEnumerate(rb_red_blk_tree *tree, void *low, void *high)
void RBDeleteFixUp(rb_red_blk_tree *tree, rb_red_blk_node *x)
if(aagss+aagstacksize-1<=aagssp)
Definition: grammar.c:1332
void TreeDestHelper(rb_red_blk_tree *tree, rb_red_blk_node *x)
#define NULL
Definition: logic.h:39
void InorderTreePrint(rb_red_blk_tree *tree, rb_red_blk_node *x)
rb_red_blk_tree * RBTreeCreate(int(*CompFunc)(const void *, const void *), void(*DestFunc)(void *), void(*InfoDestFunc)(void *), void(*PrintFunc)(const void *), void(*PrintInfo)(void *))
void RBTreePrint(rb_red_blk_tree *tree)
rb_red_blk_node * TreePredecessor(rb_red_blk_tree *tree, rb_red_blk_node *x)
void(* PrintInfo)(void *a)
void RBTreeDestroy(rb_red_blk_tree *tree)
rb_red_blk_node * RBExactQuery(rb_red_blk_tree *tree, void *q)
stk_stack * StackCreate()
Definition: stack.c:28
struct rb_red_blk_node * right
struct rb_red_blk_node * left
rb_red_blk_node * root
void * SafeMalloc(size_t size)
Definition: misc.c:56