rbtree.cpp

   1 /***************************************************************************
   2  *   Copyright (C) 2006 by Wolfgang Gerlach   *
   3  *   No object matches key 'wgerlach'.   *
   4  *                                                                         *
   5  *   This program is free software; you can redistribute it and/or modify  *
   6  *   it under the terms of the GNU General Public License as published by  *
   7  *   the Free Software Foundation; either version 2 of the License, or     *
   8  *   (at your option) any later version.                                   *
   9  *                                                                         *
  10  *   This program is distributed in the hope that it will be useful,       *
  11  *   but WITHOUT ANY WARRANTY; without even the implied warranty of        *
  12  *   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the         *
  13  *   GNU General Public License for more details.                          *
  14  *                                                                         *
  15  *   You should have received a copy of the GNU General Public License     *
  16  *   along with this program; if not, write to the                         *
  17  *   Free Software Foundation, Inc.,                                       *
  18  *   59 Temple Place - Suite 330, Boston, MA  02111-1307, USA.             *
  19  ***************************************************************************/
  20
  21
  22 #include <iostream>
  23 #include <cstdlib>
  24 #include "rbtree.h"
  25
  26
  27 using std::cout;
  28 using std::endl;
  29 using std::cerr;
  30
  31
  32 void RBTree::checkTree(){
  33         cout << "start" << endl;
  34         this->root->countBlack(0);
  35         cout << "stop" << endl;
  36 }
  37
  38 void RBTree::leftRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T)){
  39         RBNode* y = x->right;
  40         x->right=y->left;
  41         if (y->left != nil) y->left->parent=x;
  42         y->parent=x->parent;
  43         if (x->parent==this->nil)
  44                 root=y;
  45         else {
  46                 if (x == x->parent->left)
  47                         x->parent->left=y;
  48                 else
  49                 x->parent->right=y;
  50                 }
  51         y->left=x;
  52         x->parent=y;
  53
  54         // update counters of x and y !
  55         if (updateNode != 0) {
  56                 updateNode(x, this);
  57                 updateNode(y, this);
  58                 }
  59 }
  60
  61 void RBTree::rightRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T)){
  62         RBNode* y = x->left;
  63         x->left=y->right;
  64         if (y->right != nil) y->right->parent=x;
  65         y->parent=x->parent;
  66
  67
  68         if (x->parent==nil)
  69                 root=y;
  70         else {
  71                 if (x == x->parent->right) {
  72                         x->parent->right=y;
  73                 } else {
  74                         x->parent->left=y;
  75                 }
  76         }
  77
  78         y->right=x;
  79         x->parent=y;
  80         if (updateNode != 0) {
  81                 updateNode(x, this);
  82                 updateNode(y, this);
  83                 }
  84 }
  85
  86 void RBTree::rbInsertFixup(RBNode* z, void (*updateNode)(RBNode* n, RBTree *T)){
  87         RBNode *y;
  88
  89         if (z->parent==nil) return;
  90         while (z->parent->color == RED) {
  91                 if (z->parent == z->parent->parent->left)
  92                 {
  93                         y = z->parent->parent->right;
  94
  95                         if (y->color==RED)
  96                         {
  97                                 z->parent->color=BLACK;        // Case 1a
  98                                 y->color=BLACK;                // Case 1a
  99                                 z->parent->parent->color=RED;  // Case 1a
 100                                 z=z->parent->parent;           // Case 1a
 101                         }
 102                         else
 103                         {
 104                                 if (z==z->parent->right)
 105                                 {
 106                                         z=z->parent;      // Case 2a
 107                                         leftRotate(z, updateNode);  // Case 2a
 108                                 }
 109                                 z->parent->color=BLACK;             // Case 3a
 110                                 z->parent->parent->color=RED;       // Case 3a
 111                                 rightRotate(z->parent->parent, updateNode);  // Case 3a
 112                         }
 113                 }
 114                 else
 115                 {
 116
 117                         y = z->parent->parent->left;
 118
 119                         if (y->color==RED)
 120                         {
 121                                 z->parent->color=BLACK;        // Case 1b
 122                                 y->color=BLACK;                // Case 1b
 123                                 z->parent->parent->color=RED;  // Case 1b
 124                                 z=z->parent->parent;           // Case 1b
 125                         }
 126                         else
 127                         {
 128                                 if (z==z->parent->left)
 129                                 {
 130                                         z=z->parent;      // Case 2b
 131                                         rightRotate(z, updateNode);  // Case 2b
 132                                 }
 133                                 z->parent->color=BLACK;             // Case 3b
 134                                 z->parent->parent->color=RED;       // Case 3b
 135                                 leftRotate(z->parent->parent, updateNode);  // Case 3b
 136                         }
 137                 }
 138                 if (z->parent==nil) return;
 139         } //end of while
 140
 141         root->color=BLACK;
 142 }
 143
 144
 145 void RBTree::rbDeleteFixup(RBNode *x, void (*updateNode)(RBNode* n, RBTree *T)){
 146         RBNode *w;
 147
 148         while ((x != root) && (x->color == BLACK))
 149         {
 150                 if (x == x->parent->left)
 151                 {
 152                         w=x->parent->right;
 153
 154                         if (w->color == RED)
 155                         {
 156                                 w->color=BLACK;           // Case 1a
 157                                 x->parent->color=RED;     // Case 1a
 158                                 leftRotate(x->parent, updateNode);  // Case 1a
 159                                 w=x->parent->right;       // Case 1a
 160                         }
 161                         if ((w->left->color == BLACK) && (w->right->color == BLACK))
 162                         {
 163                                 w->color=RED;  // Case 2a
 164                                 x=x->parent;   // Case 2a
 165                         }
 166                         else
 167                         {
 168                                 if (w->right->color == BLACK)
 169                                 {
 170                                         w->left->color=BLACK;  // Case 3a
 171                                         w->color=RED;          // Case 3a
 172                                         rightRotate(w, updateNode);      // Case 3a
 173                                         w=x->parent->right;    // Case 3a
 174                                 }
 175                                 w->color=x->parent->color;  // Case 4a
 176                                 x->parent->color=BLACK;     // Case 4a
 177                                 w->right->color=BLACK;      // Case 4a
 178                                 leftRotate(x->parent, updateNode);    // Case 4a
 179                                 x=root;                  // Case 4a
 180                         }
 181                 }
 182                 else
 183                 {
 184                         w=x->parent->left;
 185
 186                         if (w->color == RED)
 187                         {
 188                                 w->color=BLACK;           // Case 1b
 189                                 x->parent->color=RED;     // Case 1b
 190                                 rightRotate(x->parent, updateNode);  // Case 1b
 191                                 w=x->parent->left;       // Case 1b
 192                         }
 193                         if ((w->right->color == BLACK) && (w->left->color == BLACK))
 194                         {
 195                                 w->color=RED;  // Case 2b
 196                                 x=x->parent;   // Case 2b
 197                         }
 198                         else
 199                         {
 200                                 if (w->left->color == BLACK)
 201                                 {
 202                                         w->right->color=BLACK;  // Case 3b
 203                                         w->color=RED;          // Case 3b
 204                                         leftRotate(w, updateNode);      // Case 3b
 205                                         w=x->parent->left;    // Case 3b
 206                                 }
 207
 208                                 w->color=x->parent->color;  // Case 4b
 209                                 x->parent->color=BLACK;     // Case 4b
 210                                 w->left->color=BLACK;      // Case 4b
 211                                 rightRotate(x->parent, updateNode);    // Case 4b
 212
 213                                 x=root;                  // Case 4b
 214                         }
 215                 }
 216         } // end of while
 217         x->color=BLACK;
 218 }
 219
 220 // quite similar to Cormen et al
 221 void RBTree::rbDelete(RBNode *z, void (*updateNode)(RBNode* n, RBTree *T)){
 222         RBNode *y,*x,*y_oldParent;
 223         y_oldParent=nil;
 224         if (z->left == nil || z->right == nil) {
 225                 y = z;  //z has no or one child, deletion is easy
 226         } else {
 227                 y = treeSuccessor(z);
 228                 y_oldParent=y->parent;
 229         }
 230
 231         if (y->left != nil) {
 232                 x=y->left;
 233         } else {
 234                 x=y->right;
 235         }
 236
 237         x->parent=y->parent;
 238
 239         // cut out y:
 240         if (y->parent == nil) {
 241                 root=x;
 242         } else {
 243                 if (isLeftChild(y)) {y->parent->left = x;}
 244                         else {y->parent->right = x;}
 245         }
 246
 247         RBNodecolor old_y = y->color;
 248         if (y != z) { // 2 children
 249                 //move y to z's old position and delete z
 250                 if (root==z) {
 251                         root=y;
 252                 } else {
 253                         if (isLeftChild(z)) z->parent->left = y;
 254                         else z->parent->right = y;
 255                 }
 256
 257                 y->parent = z->parent;
 258                 y->left = z->left;
 259                 y->right = z->right;
 260                 y->color = z->color;  // don't forget to delete z after rbDelete
 261
 262                 y->left->parent = y;
 263                 y->right->parent = y;
 264
 265         }
 266
 267
 268         if (old_y == BLACK) {
 269                 rbDeleteFixup(x, updateNode);
 270         }
 271
 272         updateNode(y, this);
 273         if (y_oldParent!=nil) updateNode(y_oldParent, this);
 274
 275 }
 276
 277
 278 RBNode* RBTree::treeSuccessor(RBNode *x){
 279         if (x->right != nil) return treeMinimum(x->right);
 280
 281         RBNode *y = x->parent;
 282         while ((y!=nil) && (x == y->right)) {
 283                 x=y;
 284                 y=y->parent;
 285         }
 286         return y;
 287 }
 288
 289 RBNode* RBTree::treePredecessor(RBNode *x){
 290         if (x->left != nil) return treeMaximum(x->left);
 291
 292         RBNode *y = x->parent;
 293         while ((y!=nil) && (x == y->left)) {
 294                 x=y;
 295                 y=y->parent;
 296         }
 297         return y;
 298 }
 299
 300
 301 RBNode* RBTree::treeMinimum(RBNode *x){
 302         while (x->left != nil) x=x->left;
 303         return x;
 304 }
 305
 306 RBNode* RBTree::treeMaximum(RBNode *x){
 307         while (x->right != nil) x=x->right;
 308         return x;
 309 }
 310
 311
 312 bool RBTree::isLeftChild(RBNode *n){
 313         #ifndef NDEBUG
 314         if (n->parent == nil) {
 315                 cerr << "error: isLeftChild, no parent." << endl;
 316                 exit(EXIT_FAILURE);
 317         }
 318         #endif
 319         return (n->parent->left == n);
 320 }
 321
 322 bool RBTree::isRightChild(RBNode *n){
 323         #ifndef NDEBUG
 324         if ( n->parent == nil) {
 325                 cerr << "error: isLeftChild, no parent." << endl;
 326                 exit(EXIT_FAILURE);
 327         }
 328         #endif
 329         return (n->parent->right == n);
 330 }
 331
 332
 333 RBNode* RBTree::findRightSiblingLeaf(RBNode *n){
 334         // go up:
 335         while (true) {
 336                 if (n->parent!=nil) {
 337                         if (n==n->parent->right)
 338                           n=n->parent;
 339                         else
 340                           break;
 341                 } else
 342                         return nil;
 343         }
 344
 345         n=n->parent;
 346
 347         // leftmost leaf in n is the right sibling searched
 348         n=n->right;
 349
 350         // go down:
 351         while (n->left != nil) {
 352                 n=n->left;
 353         }
 354
 355         return n;
 356 }
 357
 358 RBNode* RBTree::findLeftSiblingLeaf(RBNode *n){
 359         // go up:
 360         while (true) {
 361                 if (n->parent!=nil) {
 362                         if (n==n->parent->left)
 363                                 n=n->parent;
 364                         else
 365                                 break;
 366                 } else
 367                         return nil;
 368         }
 369
 370         n=n->parent;
 371
 372         // rightmost leaf in n is the left sibling searched
 373         n=n->left;
 374
 375         // go down:
 376         while (n->right != nil) {
 377                 n=n->right;
 378         }
 379
 380         return n;
 381 }
 382
 383
 384 int RBTree::getNodeMaxDepth(RBNode *n) {
 385         int l;
 386         int r;
 387         if (n->left == nil) l=0;
 388         else l=getNodeMaxDepth(n->left);
 389         if (n->right == nil) r=0;
 390         else r=getNodeMaxDepth(n->right);
 391
 392         return (1+(l>r?l:r));
 393 }
 394
 395 int RBTree::getNodeMinDepth(RBNode *n) {
 396         int l;
 397         int r;
 398         if (n->left == 0) l=0;
 399         else l=getNodeMinDepth(n->left);
 400         if (n->right == 0) r=0;
 401         else r=getNodeMinDepth(n->right);
 402
 403         return (1+(l>r?r:l));
 404 }
 405
 406
 407 void RBTree::printSubTree(RBNode *n){
 408         cout << ((n->color==BLACK)?"B":"R") << n << " [";
 409         if (n->left==nil) cout << "N";
 410                 else printSubTree(n->left);
 411         cout << ",";
 412         if (n->right==nil) cout << "N";
 413                 else printSubTree(n->right);
 414         cout << "]";
 415 }
 416
 417
 418 void RBTree::checkSubTree(RBNode *n){
 419
 420         if (n->left!=nil) {
 421                 if (n->left->parent != n) {
 422                         cout << "au"<< endl;
 423                         exit(1);
 424                 }
 425                 checkSubTree(n->left);
 426         }
 427
 428         if (n->right!=nil) {
 429                 if (n->right->parent != n) {
 430                         cout << "au"<< endl;
 431                         exit(1);
 432                 }
 433                 checkSubTree(n->right);
 434         }
 435
 436 }
 437
 438
 439 void RBTree::checkNode(RBNode *n){
 440         if (n->left!=nil) {
 441                 if (n->left->parent != n) {
 442                         cout << "au"<< endl;
 443                         exit(1);
 444                 }
 445
 446         }
 447
 448         if (n->right!=nil) {
 449                 if (n->right->parent != n) {
 450                         cout << "au"<< endl;
 451                         exit(1);
 452                 }
 453         }
 454 }