1 /***************************************************************************
2 * Copyright (C) 2006 by Wolfgang Gerlach *
3 * No object matches key 'wgerlach'. *
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. *
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. *
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 ***************************************************************************/
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
33 enum RBNodecolor{BLACK,RED};
36 // generic Red-Black Tree Node:
42 RBNode* right; // 3*4 bytes
44 enum RBNodecolor color; // due to structure alignment: 4 bytes !!!
49 : parent(n), left(n), right(n){
54 virtual ~RBNode(){} //adds 4 bytes vtable
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 << ",";
74 if (root != this->nil)
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);
93 bool isLeftChild(RBNode *n);
94 bool isRightChild(RBNode *n);
96 int getNodeMaxDepth(RBNode *n);
97 int getNodeMinDepth(RBNode *n);
99 void printSubTree(RBNode *n);
100 void checkSubTree(RBNode *n);
101 void checkNode(RBNode *x);
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);
111 void leftRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T));
112 void rightRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T));