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 ***************************************************************************/
32 void RBTree::checkTree(){
33 cout << "start" << endl;
34 this->root->countBlack(0);
35 cout << "stop" << endl;
38 void RBTree::leftRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T)){
41 if (y->left != nil) y->left->parent=x;
43 if (x->parent==this->nil)
46 if (x == x->parent->left)
54 // update counters of x and y !
55 if (updateNode != 0) {
61 void RBTree::rightRotate(RBNode* x, void (*updateNode)(RBNode* n, RBTree *T)){
64 if (y->right != nil) y->right->parent=x;
71 if (x == x->parent->right) {
80 if (updateNode != 0) {
86 void RBTree::rbInsertFixup(RBNode* z, void (*updateNode)(RBNode* n, RBTree *T)){
89 if (z->parent==nil) return;
90 while (z->parent->color == RED) {
91 if (z->parent == z->parent->parent->left)
93 y = z->parent->parent->right;
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
104 if (z==z->parent->right)
106 z=z->parent; // Case 2a
107 leftRotate(z, updateNode); // Case 2a
109 z->parent->color=BLACK; // Case 3a
110 z->parent->parent->color=RED; // Case 3a
111 rightRotate(z->parent->parent, updateNode); // Case 3a
117 y = z->parent->parent->left;
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
128 if (z==z->parent->left)
130 z=z->parent; // Case 2b
131 rightRotate(z, updateNode); // Case 2b
133 z->parent->color=BLACK; // Case 3b
134 z->parent->parent->color=RED; // Case 3b
135 leftRotate(z->parent->parent, updateNode); // Case 3b
138 if (z->parent==nil) return;
145 void RBTree::rbDeleteFixup(RBNode *x, void (*updateNode)(RBNode* n, RBTree *T)){
148 while ((x != root) && (x->color == BLACK))
150 if (x == x->parent->left)
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
161 if ((w->left->color == BLACK) && (w->right->color == BLACK))
163 w->color=RED; // Case 2a
164 x=x->parent; // Case 2a
168 if (w->right->color == BLACK)
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
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
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
193 if ((w->right->color == BLACK) && (w->left->color == BLACK))
195 w->color=RED; // Case 2b
196 x=x->parent; // Case 2b
200 if (w->left->color == BLACK)
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
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
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;
224 if (z->left == nil || z->right == nil) {
225 y = z; //z has no or one child, deletion is easy
227 y = treeSuccessor(z);
228 y_oldParent=y->parent;
231 if (y->left != nil) {
240 if (y->parent == nil) {
243 if (isLeftChild(y)) {y->parent->left = x;}
244 else {y->parent->right = x;}
247 RBNodecolor old_y = y->color;
248 if (y != z) { // 2 children
249 //move y to z's old position and delete z
253 if (isLeftChild(z)) z->parent->left = y;
254 else z->parent->right = y;
257 y->parent = z->parent;
260 y->color = z->color; // don't forget to delete z after rbDelete
263 y->right->parent = y;
268 if (old_y == BLACK) {
269 rbDeleteFixup(x, updateNode);
273 if (y_oldParent!=nil) updateNode(y_oldParent, this);
278 RBNode* RBTree::treeSuccessor(RBNode *x){
279 if (x->right != nil) return treeMinimum(x->right);
281 RBNode *y = x->parent;
282 while ((y!=nil) && (x == y->right)) {
289 RBNode* RBTree::treePredecessor(RBNode *x){
290 if (x->left != nil) return treeMaximum(x->left);
292 RBNode *y = x->parent;
293 while ((y!=nil) && (x == y->left)) {
301 RBNode* RBTree::treeMinimum(RBNode *x){
302 while (x->left != nil) x=x->left;
306 RBNode* RBTree::treeMaximum(RBNode *x){
307 while (x->right != nil) x=x->right;
312 bool RBTree::isLeftChild(RBNode *n){
314 if (n->parent == nil) {
315 cerr << "error: isLeftChild, no parent." << endl;
319 return (n->parent->left == n);
322 bool RBTree::isRightChild(RBNode *n){
324 if ( n->parent == nil) {
325 cerr << "error: isLeftChild, no parent." << endl;
329 return (n->parent->right == n);
333 RBNode* RBTree::findRightSiblingLeaf(RBNode *n){
336 if (n->parent!=nil) {
337 if (n==n->parent->right)
347 // leftmost leaf in n is the right sibling searched
351 while (n->left != nil) {
358 RBNode* RBTree::findLeftSiblingLeaf(RBNode *n){
361 if (n->parent!=nil) {
362 if (n==n->parent->left)
372 // rightmost leaf in n is the left sibling searched
376 while (n->right != nil) {
384 int RBTree::getNodeMaxDepth(RBNode *n) {
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);
392 return (1+(l>r?l:r));
395 int RBTree::getNodeMinDepth(RBNode *n) {
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);
403 return (1+(l>r?r:l));
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);
412 if (n->right==nil) cout << "N";
413 else printSubTree(n->right);
418 void RBTree::checkSubTree(RBNode *n){
421 if (n->left->parent != n) {
425 checkSubTree(n->left);
429 if (n->right->parent != n) {
433 checkSubTree(n->right);
439 void RBTree::checkNode(RBNode *n){
441 if (n->left->parent != n) {
449 if (n->right->parent != n) {