C/sorting.and.searching.cormen.algo/src/rbtr.txt

   1 // reentrant red-black tree
   2
   3 #include <stdlib.h>
   4 #include "rbtr.h"
   5
   6 typedef enum { BLACK, RED } NodeColor;
   7
   8 typedef struct NodeTag {
   9     struct NodeTag *left;       // left child
  10     struct NodeTag *right;      // right child
  11     struct NodeTag *parent;     // parent
  12     NodeColor color;            // node color (BLACK, RED)
  13     void *key;                  // key used for searching
  14     void *val;                // user data
  15 } NodeType;
  16
  17 typedef struct RbtTag {
  18     NodeType *root;   // root of red-black tree
  19     NodeType sentinel;
  20     int (*compare)(void *a, void *b);    // compare keys
  21 } RbtType;
  22
  23 // all leafs are sentinels
  24 #define SENTINEL &rbt->sentinel
  25
  26 RbtHandle rbtNew(int(*rbtCompare)(void *a, void *b)) {
  27     RbtType *rbt;
  28
  29     if ((rbt = (RbtType *)malloc(sizeof(RbtType))) == NULL) {
  30         return NULL;
  31     }
  32
  33     rbt->compare = rbtCompare;
  34     rbt->root = SENTINEL;
  35     rbt->sentinel.left = SENTINEL;
  36     rbt->sentinel.right = SENTINEL;
  37     rbt->sentinel.parent = NULL;
  38     rbt->sentinel.color = BLACK;
  39     rbt->sentinel.key = NULL;
  40     rbt->sentinel.val = NULL;
  41
  42     return rbt;
  43 }
  44
  45 static void deleteTree(RbtHandle h, NodeType *p) {
  46     RbtType *rbt = h;
  47
  48     // erase nodes depth-first
  49     if (p == SENTINEL) return;
  50     deleteTree(h, p->left);
  51     deleteTree(h, p->right);
  52     free(p);
  53 }
  54
  55 void rbtDelete(RbtHandle h) {
  56     RbtType *rbt = h;
  57
  58     deleteTree(h, rbt->root);
  59     free(rbt);
  60 }
  61
  62 static void rotateLeft(RbtType *rbt, NodeType *x) {
  63
  64     // rotate node x to left
  65
  66     NodeType *y = x->right;
  67
  68     // establish x->right link
  69     x->right = y->left;
  70     if (y->left != SENTINEL) y->left->parent = x;
  71
  72     // establish y->parent link
  73     if (y != SENTINEL) y->parent = x->parent;
  74     if (x->parent) {
  75         if (x == x->parent->left)
  76             x->parent->left = y;
  77         else
  78             x->parent->right = y;
  79     } else {
  80         rbt->root = y;
  81     }
  82
  83     // link x and y
  84     y->left = x;
  85     if (x != SENTINEL) x->parent = y;
  86 }
  87
  88 static void rotateRight(RbtType *rbt, NodeType *x) {
  89
  90     // rotate node x to right
  91
  92     NodeType *y = x->left;
  93
  94     // establish x->left link
  95     x->left = y->right;
  96     if (y->right != SENTINEL) y->right->parent = x;
  97
  98     // establish y->parent link
  99     if (y != SENTINEL) y->parent = x->parent;
 100     if (x->parent) {
 101         if (x == x->parent->right)
 102             x->parent->right = y;
 103         else
 104             x->parent->left = y;
 105     } else {
 106         rbt->root = y;
 107     }
 108
 109     // link x and y
 110     y->right = x;
 111     if (x != SENTINEL) x->parent = y;
 112 }
 113
 114 static void insertFixup(RbtType *rbt, NodeType *x) {
 115
 116     // maintain red-black tree balance after inserting node x
 117
 118     // check red-black properties
 119     while (x != rbt->root && x->parent->color == RED) {
 120         // we have a violation
 121         if (x->parent == x->parent->parent->left) {
 122             NodeType *y = x->parent->parent->right;
 123             if (y->color == RED) {
 124
 125                 // uncle is RED
 126                 x->parent->color = BLACK;
 127                 y->color = BLACK;
 128                 x->parent->parent->color = RED;
 129                 x = x->parent->parent;
 130             } else {
 131
 132                 // uncle is BLACK
 133                 if (x == x->parent->right) {
 134                     // make x a left child
 135                     x = x->parent;
 136                     rotateLeft(rbt, x);
 137                 }
 138
 139                 // recolor and rotate
 140                 x->parent->color = BLACK;
 141                 x->parent->parent->color = RED;
 142                 rotateRight(rbt, x->parent->parent);
 143             }
 144         } else {
 145
 146             // mirror image of above code
 147             NodeType *y = x->parent->parent->left;
 148             if (y->color == RED) {
 149
 150                 // uncle is RED
 151                 x->parent->color = BLACK;
 152                 y->color = BLACK;
 153                 x->parent->parent->color = RED;
 154                 x = x->parent->parent;
 155             } else {
 156
 157                 // uncle is BLACK
 158                 if (x == x->parent->left) {
 159                     x = x->parent;
 160                     rotateRight(rbt, x);
 161                 }
 162                 x->parent->color = BLACK;
 163                 x->parent->parent->color = RED;
 164                 rotateLeft(rbt, x->parent->parent);
 165             }
 166         }
 167     }
 168     rbt->root->color = BLACK;
 169 }
 170
 171 RbtStatus rbtInsert(RbtHandle h, void *key, void *val) {
 172     NodeType *current, *parent, *x;
 173     RbtType *rbt = h;
 174
 175     // allocate node for data and insert in tree
 176
 177     // find future parent
 178     current = rbt->root;
 179     parent = 0;
 180     while (current != SENTINEL) {
 181         int rc = rbt->compare(key, current->key);
 182         if (rc == 0)
 183             return RBT_STATUS_DUPLICATE_KEY;
 184         parent = current;
 185         current = (rc < 0) ? current->left : current->right;
 186     }
 187
 188     // setup new node
 189     if ((x = malloc (sizeof(*x))) == 0)
 190         return RBT_STATUS_MEM_EXHAUSTED;
 191     x->parent = parent;
 192     x->left = SENTINEL;
 193     x->right = SENTINEL;
 194     x->color = RED;
 195     x->key = key;
 196     x->val = val;
 197
 198     // insert node in tree
 199     if(parent) {
 200         if(rbt->compare(key, parent->key) < 0)
 201             parent->left = x;
 202         else
 203             parent->right = x;
 204     } else {
 205         rbt->root = x;
 206     }
 207
 208     insertFixup(rbt, x);
 209
 210     return RBT_STATUS_OK;
 211 }
 212
 213 void deleteFixup(RbtType *rbt, NodeType *x) {
 214
 215     // maintain red-black tree balance after deleting node x
 216
 217     while (x != rbt->root && x->color == BLACK) {
 218         if (x == x->parent->left) {
 219             NodeType *w = x->parent->right;
 220             if (w->color == RED) {
 221                 w->color = BLACK;
 222                 x->parent->color = RED;
 223                 rotateLeft (rbt, x->parent);
 224                 w = x->parent->right;
 225             }
 226             if (w->left->color == BLACK && w->right->color == BLACK) {
 227                 w->color = RED;
 228                 x = x->parent;
 229             } else {
 230                 if (w->right->color == BLACK) {
 231                     w->left->color = BLACK;
 232                     w->color = RED;
 233                     rotateRight (rbt, w);
 234                     w = x->parent->right;
 235                 }
 236                 w->color = x->parent->color;
 237                 x->parent->color = BLACK;
 238                 w->right->color = BLACK;
 239                 rotateLeft (rbt, x->parent);
 240                 x = rbt->root;
 241             }
 242         } else {
 243             NodeType *w = x->parent->left;
 244             if (w->color == RED) {
 245                 w->color = BLACK;
 246                 x->parent->color = RED;
 247                 rotateRight (rbt, x->parent);
 248                 w = x->parent->left;
 249             }
 250             if (w->right->color == BLACK && w->left->color == BLACK) {
 251                 w->color = RED;
 252                 x = x->parent;
 253             } else {
 254                 if (w->left->color == BLACK) {
 255                     w->right->color = BLACK;
 256                     w->color = RED;
 257                     rotateLeft (rbt, w);
 258                     w = x->parent->left;
 259                 }
 260                 w->color = x->parent->color;
 261                 x->parent->color = BLACK;
 262                 w->left->color = BLACK;
 263                 rotateRight (rbt, x->parent);
 264                 x = rbt->root;
 265             }
 266         }
 267     }
 268     x->color = BLACK;
 269 }
 270
 271 RbtStatus rbtErase(RbtHandle h, RbtIterator i) {
 272     NodeType *x, *y;
 273     RbtType *rbt = h;
 274     NodeType *z = i;
 275
 276     if (z->left == SENTINEL || z->right == SENTINEL) {
 277         // y has a SENTINEL node as a child
 278         y = z;
 279     } else {
 280         // find tree successor with a SENTINEL node as a child
 281         y = z->right;
 282         while (y->left != SENTINEL) y = y->left;
 283     }
 284
 285     // x is y's only child
 286     if (y->left != SENTINEL)
 287         x = y->left;
 288     else
 289         x = y->right;
 290
 291     // remove y from the parent chain
 292     x->parent = y->parent;
 293     if (y->parent)
 294         if (y == y->parent->left)
 295             y->parent->left = x;
 296         else
 297             y->parent->right = x;
 298     else
 299         rbt->root = x;
 300
 301     if (y != z) {
 302         z->key = y->key;
 303         z->val = y->val;
 304     }
 305
 306
 307     if (y->color == BLACK)
 308         deleteFixup (rbt, x);
 309
 310     free (y);
 311
 312     return RBT_STATUS_OK;
 313 }
 314
 315 RbtIterator rbtNext(RbtHandle h, RbtIterator it) {
 316     RbtType *rbt = h;
 317     NodeType *i = it;
 318
 319     if (i->right != SENTINEL) {
 320         // go right 1, then left to the end
 321         for (i = i->right; i->left != SENTINEL; i = i->left);
 322     } else {
 323         // while you're the right child, chain up parent link
 324         NodeType *p = i->parent;
 325         while (p && i == p->right) {
 326             i = p;
 327             p = p->parent;
 328         }
 329
 330         // return the "inorder" node
 331         i = p;
 332     }
 333     return i != SENTINEL ? i : NULL;
 334 }
 335
 336 RbtIterator rbtBegin(RbtHandle h) {
 337     RbtType *rbt = h;
 338
 339     // return pointer to first value
 340     NodeType *i;
 341     for (i = rbt->root; i->left != SENTINEL; i = i->left);
 342     return i != SENTINEL ? i : NULL;
 343 }
 344
 345 RbtIterator rbtEnd(RbtHandle h) {
 346    // return pointer to one past last value
 347    return NULL;
 348 }
 349
 350 void rbtKeyValue(RbtHandle h, RbtIterator it, void **key, void **val) {
 351     NodeType *i = it;
 352
 353     *key = i->key;
 354     *val = i->val;
 355 }
 356
 357
 358 void *rbtFind(RbtHandle h, void *key) {
 359     RbtType *rbt = h;
 360
 361     NodeType *current;
 362     current = rbt->root;
 363     while(current != SENTINEL) {
 364         int rc = rbt->compare(key, current->key);
 365         if (rc == 0) return current;
 366         current = (rc < 0) ? current->left : current->right;
 367     }
 368     return NULL;
 369 }