123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567 |
- /**********************************************************
- * See the LICENSE file for copyright information. *
- **********************************************************/
- #include "config.h"
- #include <assert.h>
- #include <rbtree/red_black_tree.h>
- #include <stdio.h>
- #include <stdlib.h>
- /***********************************************************************/
- /* FUNCTION: RBTreeCreate */
- /**/
- /* INPUTS: All the inputs are names of functions. CompFunc takes to */
- /* void pointers to keys and returns 1 if the first argument is */
- /* "greater than" the second. DestFunc takes a pointer to a key and */
- /* destroys it in the appropriate manner when the node containing that */
- /* key is deleted. */
- /**/
- /* OUTPUT: This function returns a pointer to the newly created */
- /* red-black tree. */
- /**/
- /* Modifies Input: none */
- /***********************************************************************/
- rb_red_blk_tree* RBTreeCreate( int (*CompFunc) (const void*,const void*),
- void (*DestFunc)(void *)) {
- rb_red_blk_tree* newTree = NULL;
- rb_red_blk_node* temp;
- newTree= malloc(sizeof(rb_red_blk_tree));
- if (newTree == NULL) {
- return NULL;
- }
- newTree->nil = newTree->root = NULL;
- newTree->Compare= CompFunc;
- newTree->DestroyKey= DestFunc;
- /* see the comment in the rb_red_blk_tree structure in red_black_tree.h */
- /* for information on nil and root */
- temp=newTree->nil= malloc(sizeof(rb_red_blk_node));
- if (temp == NULL) {
- free(newTree);
- return NULL;
- }
- temp->parent=temp->left=temp->right=temp;
- temp->red=0;
- temp->key=0;
- temp=newTree->root= malloc(sizeof(rb_red_blk_node));
- if (temp == NULL) {
- free(newTree->nil);
- free(newTree);
- return NULL;
- }
- temp->parent=temp->left=temp->right=newTree->nil;
- temp->key=0;
- temp->red=0;
- return newTree;
- }
- /***********************************************************************/
- /* FUNCTION: LeftRotate */
- /**/
- /* INPUTS: This takes a tree so that it can access the appropriate */
- /* root and nil pointers, and the node to rotate on. */
- /**/
- /* OUTPUT: None */
- /**/
- /* Modifies Input: tree, x */
- /**/
- /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
- /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
- /* makes the parent of x be to the left of x, x the parent of */
- /* its parent before the rotation and fixes other pointers */
- /* accordingly. */
- /***********************************************************************/
- static void LeftRotate(rb_red_blk_tree* tree, rb_red_blk_node* x) {
- rb_red_blk_node* y;
- rb_red_blk_node* nil=tree->nil;
- /* I originally wrote this function to use the sentinel for */
- /* nil to avoid checking for nil. However this introduces a */
- /* very subtle bug because sometimes this function modifies */
- /* the parent pointer of nil. This can be a problem if a */
- /* function which calls LeftRotate also uses the nil sentinel */
- /* and expects the nil sentinel's parent pointer to be unchanged */
- /* after calling this function. For example, when RBDeleteFixUP */
- /* calls LeftRotate it expects the parent pointer of nil to be */
- /* unchanged. */
- y=x->right;
- x->right=y->left;
- if (y->left != nil) y->left->parent=x; /* used to use sentinel here */
- /* and do an unconditional assignment instead of testing for nil */
-
- y->parent=x->parent;
- /* instead of checking if x->parent is the root as in the book, we */
- /* count on the root sentinel to implicitly take care of this case */
- if( x == x->parent->left) {
- x->parent->left=y;
- } else {
- x->parent->right=y;
- }
- y->left=x;
- x->parent=y;
- assert(!tree->nil->red && "nil not red in LeftRotate");
- }
- /***********************************************************************/
- /* FUNCTION: RighttRotate */
- /**/
- /* INPUTS: This takes a tree so that it can access the appropriate */
- /* root and nil pointers, and the node to rotate on. */
- /**/
- /* OUTPUT: None */
- /**/
- /* Modifies Input?: tree, y */
- /**/
- /* EFFECTS: Rotates as described in _Introduction_To_Algorithms by */
- /* Cormen, Leiserson, Rivest (Chapter 14). Basically this */
- /* makes the parent of x be to the left of x, x the parent of */
- /* its parent before the rotation and fixes other pointers */
- /* accordingly. */
- /***********************************************************************/
- static void RightRotate(rb_red_blk_tree* tree, rb_red_blk_node* y) {
- rb_red_blk_node* x;
- rb_red_blk_node* nil=tree->nil;
- /* I originally wrote this function to use the sentinel for */
- /* nil to avoid checking for nil. However this introduces a */
- /* very subtle bug because sometimes this function modifies */
- /* the parent pointer of nil. This can be a problem if a */
- /* function which calls LeftRotate also uses the nil sentinel */
- /* and expects the nil sentinel's parent pointer to be unchanged */
- /* after calling this function. For example, when RBDeleteFixUP */
- /* calls LeftRotate it expects the parent pointer of nil to be */
- /* unchanged. */
- x=y->left;
- y->left=x->right;
- if (nil != x->right) x->right->parent=y; /*used to use sentinel here */
- /* and do an unconditional assignment instead of testing for nil */
- /* instead of checking if x->parent is the root as in the book, we */
- /* count on the root sentinel to implicitly take care of this case */
- x->parent=y->parent;
- if( y == y->parent->left) {
- y->parent->left=x;
- } else {
- y->parent->right=x;
- }
- x->right=y;
- y->parent=x;
- assert(!tree->nil->red && "nil not red in RightRotate");
- }
- /***********************************************************************/
- /* FUNCTION: TreeInsertHelp */
- /**/
- /* INPUTS: tree is the tree to insert into and z is the node to insert */
- /**/
- /* OUTPUT: none */
- /**/
- /* Modifies Input: tree, z */
- /**/
- /* EFFECTS: Inserts z into the tree as if it were a regular binary tree */
- /* using the algorithm described in _Introduction_To_Algorithms_ */
- /* by Cormen et al. This function is only intended to be called */
- /* by the RBTreeInsert function and not by the user */
- /***********************************************************************/
- static void TreeInsertHelp(rb_red_blk_tree* tree, rb_red_blk_node* z) {
- /* This function should only be called by InsertRBTree (see above) */
- rb_red_blk_node* x;
- rb_red_blk_node* y;
- rb_red_blk_node* nil=tree->nil;
-
- z->left=z->right=nil;
- y=tree->root;
- x=tree->root->left;
- while( x != nil) {
- y=x;
- if (1 == tree->Compare(x->key,z->key)) { /* x.key > z.key */
- x=x->left;
- } else { /* x,key <= z.key */
- x=x->right;
- }
- }
- z->parent=y;
- if ( (y == tree->root) ||
- (1 == tree->Compare(y->key,z->key))) { /* y.key > z.key */
- y->left=z;
- } else {
- y->right=z;
- }
- assert(!tree->nil->red && "nil not red in TreeInsertHelp");
- }
- /* Before calling Insert RBTree the node x should have its key set */
- /***********************************************************************/
- /* FUNCTION: RBTreeInsert */
- /**/
- /* INPUTS: tree is the red-black tree to insert a node which has a key */
- /* pointed to by key. */
- /**/
- /* OUTPUT: This function returns a pointer to the newly inserted node */
- /* which is guarunteed to be valid until this node is deleted. */
- /* What this means is if another data structure stores this */
- /* pointer then the tree does not need to be searched when this */
- /* is to be deleted. */
- /**/
- /* Modifies Input: tree */
- /**/
- /* EFFECTS: Creates a node node which contains the appropriate key */
- /* pointer and inserts it into the tree. */
- /***********************************************************************/
- rb_red_blk_node * RBTreeInsert(rb_red_blk_tree* tree, void* key) {
- rb_red_blk_node * y;
- rb_red_blk_node * x;
- rb_red_blk_node * newNode;
- x= malloc(sizeof(rb_red_blk_node));
- if (x == NULL) {
- return NULL;
- }
- x->key=key;
- TreeInsertHelp(tree,x);
- newNode=x;
- x->red=1;
- while(x->parent->red) { /* use sentinel instead of checking for root */
- if (x->parent == x->parent->parent->left) {
- y=x->parent->parent->right;
- if (y->red) {
- x->parent->red=0;
- y->red=0;
- x->parent->parent->red=1;
- x=x->parent->parent;
- } else {
- if (x == x->parent->right) {
- x=x->parent;
- LeftRotate(tree,x);
- }
- x->parent->red=0;
- x->parent->parent->red=1;
- RightRotate(tree,x->parent->parent);
- }
- } else { /* case for x->parent == x->parent->parent->right */
- y=x->parent->parent->left;
- if (y->red) {
- x->parent->red=0;
- y->red=0;
- x->parent->parent->red=1;
- x=x->parent->parent;
- } else {
- if (x == x->parent->left) {
- x=x->parent;
- RightRotate(tree,x);
- }
- x->parent->red=0;
- x->parent->parent->red=1;
- LeftRotate(tree,x->parent->parent);
- }
- }
- }
- tree->root->left->red=0;
- return newNode;
- }
- /***********************************************************************/
- /* FUNCTION: TreeSuccessor */
- /**/
- /* INPUTS: tree is the tree in question, and x is the node we want the */
- /* the successor of. */
- /**/
- /* OUTPUT: This function returns the successor of x or NULL if no */
- /* successor exists. */
- /**/
- /* Modifies Input: none */
- /**/
- /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
- /***********************************************************************/
-
- rb_red_blk_node* TreeSuccessor(rb_red_blk_tree* tree,rb_red_blk_node* x) {
- rb_red_blk_node* y;
- rb_red_blk_node* nil=tree->nil;
- rb_red_blk_node* root=tree->root;
- if (nil != (y = x->right)) { /* assignment to y is intentional */
- while(y->left != nil) { /* returns the minium of the right subtree of x */
- y=y->left;
- }
- return y;
- } else {
- y=x->parent;
- while(x == y->right) { /* sentinel used instead of checking for nil */
- x=y;
- y=y->parent;
- }
- if (y == root) return nil;
- return y;
- }
- }
- /***********************************************************************/
- /* FUNCTION: Treepredecessor */
- /**/
- /* INPUTS: tree is the tree in question, and x is the node we want the */
- /* the predecessor of. */
- /**/
- /* OUTPUT: This function returns the predecessor of x or NULL if no */
- /* predecessor exists. */
- /**/
- /* Modifies Input: none */
- /**/
- /* Note: uses the algorithm in _Introduction_To_Algorithms_ */
- /***********************************************************************/
- rb_red_blk_node* TreePredecessor(rb_red_blk_tree* tree, rb_red_blk_node* x) {
- rb_red_blk_node* y;
- rb_red_blk_node* nil=tree->nil;
- rb_red_blk_node* root=tree->root;
- if (nil != (y = x->left)) { /* assignment to y is intentional */
- while(y->right != nil) { /* returns the maximum of the left subtree of x */
- y=y->right;
- }
- return y;
- } else {
- y=x->parent;
- while(x == y->left) {
- if (y == root) return nil;
- x=y;
- y=y->parent;
- }
- return y;
- }
- }
- /***********************************************************************/
- /* FUNCTION: TreeDestHelper */
- /**/
- /* INPUTS: tree is the tree to destroy and x is the current node */
- /**/
- /* OUTPUT: none */
- /**/
- /* EFFECTS: This function recursively destroys the nodes of the tree */
- /* postorder using the DestroyKey and DestroyInfo functions. */
- /**/
- /* Modifies Input: tree, x */
- /**/
- /* Note: This function should only be called by RBTreeDestroy */
- /***********************************************************************/
- static void TreeDestHelper(rb_red_blk_tree* tree, rb_red_blk_node* x) {
- rb_red_blk_node* nil=tree->nil;
- if (x != nil) {
- TreeDestHelper(tree,x->left);
- TreeDestHelper(tree,x->right);
- tree->DestroyKey(x->key);
- free(x);
- }
- }
- /***********************************************************************/
- /* FUNCTION: RBTreeDestroy */
- /**/
- /* INPUTS: tree is the tree to destroy */
- /**/
- /* OUTPUT: none */
- /**/
- /* EFFECT: Destroys the key and frees memory */
- /**/
- /* Modifies Input: tree */
- /**/
- /***********************************************************************/
- void RBTreeDestroy(rb_red_blk_tree* tree) {
- TreeDestHelper(tree,tree->root->left);
- free(tree->root);
- free(tree->nil);
- free(tree);
- }
- /***********************************************************************/
- /* FUNCTION: RBExactQuery */
- /**/
- /* INPUTS: tree is the tree to print and q is a pointer to the key */
- /* we are searching for */
- /**/
- /* OUTPUT: returns the a node with key equal to q. If there are */
- /* multiple nodes with key equal to q this function returns */
- /* the one highest in the tree */
- /**/
- /* Modifies Input: none */
- /**/
- /***********************************************************************/
-
- rb_red_blk_node* RBExactQuery(rb_red_blk_tree* tree, void* q) {
- rb_red_blk_node* x=tree->root->left;
- rb_red_blk_node* nil=tree->nil;
- int compVal;
- if (x == nil) return 0;
- compVal = tree->Compare(x->key, q);
- while(0 != compVal) {/*assignemnt*/
- if (1 == compVal) { /* x->key > q */
- x=x->left;
- } else {
- x=x->right;
- }
- if ( x == nil) return 0;
- compVal = tree->Compare(x->key, q);
- }
- return x;
- }
- /***********************************************************************/
- /* FUNCTION: RBDeleteFixUp */
- /**/
- /* INPUTS: tree is the tree to fix and x is the child of the spliced */
- /* out node in RBTreeDelete. */
- /**/
- /* OUTPUT: none */
- /**/
- /* EFFECT: Performs rotations and changes colors to restore red-black */
- /* properties after a node is deleted */
- /**/
- /* Modifies Input: tree, x */
- /**/
- /* The algorithm from this function is from _Introduction_To_Algorithms_ */
- /***********************************************************************/
- static void RBDeleteFixUp(rb_red_blk_tree* tree, rb_red_blk_node* x) {
- rb_red_blk_node* root=tree->root->left;
- rb_red_blk_node* w;
- while( (!x->red) && (root != x)) {
- if (x == x->parent->left) {
- w=x->parent->right;
- if (w->red) {
- w->red=0;
- x->parent->red=1;
- LeftRotate(tree,x->parent);
- w=x->parent->right;
- }
- if ( (!w->right->red) && (!w->left->red) ) {
- w->red=1;
- x=x->parent;
- } else {
- if (!w->right->red) {
- w->left->red=0;
- w->red=1;
- RightRotate(tree,w);
- w=x->parent->right;
- }
- w->red=x->parent->red;
- x->parent->red=0;
- w->right->red=0;
- LeftRotate(tree,x->parent);
- x=root; /* this is to exit while loop */
- }
- } else { // the code below has left and right switched from above
- w=x->parent->left;
- if (w->red) {
- w->red=0;
- x->parent->red=1;
- RightRotate(tree,x->parent);
- w=x->parent->left;
- }
- if ( (!w->right->red) && (!w->left->red) ) {
- w->red=1;
- x=x->parent;
- } else {
- if (!w->left->red) {
- w->right->red=0;
- w->red=1;
- LeftRotate(tree,w);
- w=x->parent->left;
- }
- w->red=x->parent->red;
- x->parent->red=0;
- w->left->red=0;
- RightRotate(tree,x->parent);
- x=root; /* this is to exit while loop */
- }
- }
- }
- x->red=0;
- assert(!tree->nil->red && "nil not black in RBDeleteFixUp");
- }
- /***********************************************************************/
- /* FUNCTION: RBDelete */
- /**/
- /* INPUTS: tree is the tree to delete node z from */
- /**/
- /* OUTPUT: none */
- /**/
- /* EFFECT: Deletes z from tree and frees the key of z */
- /* using DestroyKey. Then calls */
- /* RBDeleteFixUp to restore red-black properties */
- /**/
- /* Modifies Input: tree, z */
- /**/
- /* The algorithm from this function is from _Introduction_To_Algorithms_ */
- /***********************************************************************/
- void RBDelete(rb_red_blk_tree* tree, rb_red_blk_node* z){
- rb_red_blk_node* y;
- rb_red_blk_node* x;
- rb_red_blk_node* nil=tree->nil;
- rb_red_blk_node* root=tree->root;
- y= ((z->left == nil) || (z->right == nil)) ? z : TreeSuccessor(tree,z);
- x= (y->left == nil) ? y->right : y->left;
- if (root == (x->parent = y->parent)) { /* assignment of y->p to x->p is intentional */
- root->left=x;
- } else {
- if (y == y->parent->left) {
- y->parent->left=x;
- } else {
- y->parent->right=x;
- }
- }
- if (y != z) { /* y should not be nil in this case */
- assert(y!=tree->nil && "y is nil in RBDelete");
- /* y is the node to splice out and x is its child */
- if (!(y->red)) RBDeleteFixUp(tree,x);
-
- tree->DestroyKey(z->key);
- y->left=z->left;
- y->right=z->right;
- y->parent=z->parent;
- y->red=z->red;
- z->left->parent=z->right->parent=y;
- if (z == z->parent->left) {
- z->parent->left=y;
- } else {
- z->parent->right=y;
- }
- free(z);
- } else {
- tree->DestroyKey(y->key);
- if (!(y->red)) RBDeleteFixUp(tree,x);
- free(y);
- }
-
- assert(!tree->nil->red && "nil not black in RBDelete");
- }
|