rbtree.h

   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 // this is a red-black tree implementation by wolfgang Gerlach based on the algorithm provided by
  23 // Cormen et al.: Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001
  24
  25
  26
  27 #ifndef RBTree
  28 #define RBTree RBTree
  29
  30
  31
  32
  33 enum RBNodecolor{BLACK,RED};
  34
  35
  36 // generic Red-Black Tree Node:
  37 class RBNode
  38 {
  39         public:
  40         RBNode* parent;
  41         RBNode* left;
  42         RBNode* right;   // 3*4 bytes
  43
  44         enum RBNodecolor color; // due to structure alignment: 4 bytes !!!
  45
  46         RBNode(){};
  47
  48         RBNode(RBNode *n)
  49                 : parent(n), left(n), right(n){
  50                 color=RED;
  51         }
  52
  53
  54         virtual ~RBNode(){} //adds 4 bytes vtable
  55
  56         void countBlack(int i){
  57             if (this->color == BLACK) i++;
  58             if (this->left != this) this->left->countBlack(i);
  59             else std::cout << i << ",";
  60             if (this->right != this) this->right->countBlack(i);
  61             else std::cout << i << ",";
  62         }
  63 };
  64
  65 class RBTree{
  66         public:
  67
  68         RBNode *root;
  69         RBNode *nil;
  70
  71
  72         virtual ~RBTree(){
  73             // Don't double free!
  74             if (root != this->nil)
  75                 deleteNode(root);
  76             root = 0;
  77             delete this->nil;
  78             this->nil = 0;
  79         }
  80
  81         void checkTree();
  82
  83         void rbInsertFixup(RBNode* z, void (*updateNode)(RBNode* n, RBTree *T));
  84         void rbDeleteFixup(RBNode *x, void (*updateNode)(RBNode* n, RBTree *T));
  85         void rbDelete(RBNode *z, void (*updateNode)(RBNode* n, RBTree *T));
  86         RBNode* findRightSiblingLeaf(RBNode *n);
  87         RBNode* findLeftSiblingLeaf(RBNode *n);
  88         RBNode* treeSuccessor(RBNode *x);
  89         RBNode* treePredecessor(RBNode *x);
  90         RBNode* treeMinimum(RBNode *x);
  91         RBNode* treeMaximum(RBNode *x);
  92
  93         bool isLeftChild(RBNode *n);
  94         bool isRightChild(RBNode *n);
  95
  96         int getNodeMaxDepth(RBNode *n);
  97         int getNodeMinDepth(RBNode *n);
  98
  99         void printSubTree(RBNode *n);
 100         void checkSubTree(RBNode *n);
 101         void checkNode(RBNode *x);
 102
 103         void deleteNode(RBNode* x){
 104                 if (x->left!=nil && x->left) deleteNode(x->left);
 105                 if (x->right!=nil && x->right) deleteNode(x->right);
 106                 delete x;
 107         }
 108
 109
 110         private:
 111         void leftRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T));
 112         void rightRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T));
 113
 114 };
 115
 116 #endif