Main Page | Class Hierarchy | Alphabetical List | Class List | File List | Class Members | Related Pages

vdkbtrees.h

00001 /*
00002  * ===========================
00003  * VDK Visual Development Kit
00004  * Version 0.5
00005  * November 1998
00006  * ===========================
00007  *
00008  * Copyright (C) 1998, Mario Motta
00009  * Developed by Mario Motta <mmotta@guest.net>
00010  *
00011  * This library is free software; you can redistribute it and/or
00012  * modify it under the terms of the GNU Library General Public
00013  * License as published by the Free Software Foundation; either
00014  * version 2 of the License, or (at your option) any later version.
00015  *
00016  * This library is distributed in the hope that it will be useful,
00017  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00018  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00019  * Library General Public License for more details.
00020  *
00021  * You should have received a copy of the GNU Library General Public
00022  * License along with this library; if not, write to the Free Software
00023  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
00024  * 02111-1307, USA.
00025  *
00026  */
00027 
00028 #ifndef VDKBTREES_H
00029 #define VDKBTREES_H
00030 #ifdef NULL
00031 #undef NULL
00032 #define NULL 0x0000
00033 #endif
00034 // --------------------------
00035 // Abstract  class template, 
00036 // --------------------------
00037 
00038 template<class T, class Node>
00039 class AbstractBinaryNode {
00040 public:
00041     AbstractBinaryNode() { }
00042     AbstractBinaryNode(  T& _object, 
00043                Node *_parent = NULL, 
00044                Node *_left = NULL, 
00045                Node *_right = NULL);
00046     virtual ~AbstractBinaryNode() { }
00047 
00048     // Subtree arrangement
00049     virtual Node *Clone(Node *_parent)  ;
00050     virtual void RemoveSubtree();
00051     virtual Node *LeftRotate(Node *root);
00052     virtual Node *RightRotate(Node *root);
00053     virtual int CheckTreeProperties(  Node *);
00054     virtual int IsLeftChild()  ;
00055     virtual int IsRightChild()  ;
00056     // Adding a node and deleting
00057     virtual Node *add(  T& x);
00058     virtual Node *unlink(Node *z);
00059 
00060     // Find
00061     virtual Node *find(  T& x);
00062     virtual Node *findNearest(  T& x);
00063 
00064     // Tree trasverse
00065     virtual Node *Minimum();
00066     virtual Node *Maximum();
00067     virtual Node *Predecessor();
00068     virtual Node *Successor();
00069 
00070     // Miscellaneous
00071     virtual T *Object();
00072 
00073 public:
00074     T object;
00075     Node *left, *right, *parent;
00076 
00077 };
00078 
00079 template<class T>
00080 class BinaryNode : public AbstractBinaryNode<T, BinaryNode<T> > {
00081 public:
00082     //  ructors and destructor
00083     BinaryNode() { }
00084     BinaryNode(  T& object, 
00085                BinaryNode<T> *parent = NULL, 
00086                BinaryNode<T> *left = NULL, 
00087                BinaryNode<T> *right = NULL):
00088         AbstractBinaryNode<T, BinaryNode<T> >(object, parent, left, right) { }
00089     virtual ~BinaryNode() { }
00090 };
00091 
00093 // Iterator class 
00101 enum BtreeIteratorMode { BtMinKey, BtRootKey, BtMaxKey };
00106 template<class T, class Node>
00107 class AbstractBinaryTree {
00108 
00109 public:
00110 
00111     AbstractBinaryTree();
00115     AbstractBinaryTree(  AbstractBinaryTree<T, Node>&);
00119     AbstractBinaryTree<T, Node>& operator=(  AbstractBinaryTree<T, Node>&);
00120     virtual ~AbstractBinaryTree();
00121 
00125     virtual void add(  T&);      // Add a node
00129     virtual void unlink(  T&);      // Remove a node
00133     virtual T *find(  T& q);
00137     virtual int IsEmpty()   { return root == NULL; }
00138 
00139     /*
00140       \internal
00141     */
00142     virtual Node *IteratorRoot()  ;
00143     /*
00144       \internal
00145     */
00146     virtual Node *IteratorFind(  T& x)  ;
00150     virtual int CheckTreeProperties();
00154     unsigned int size() { return count; }
00155 
00156     
00157     class Iterator {
00158 
00159     public:
00168         Iterator(  AbstractBinaryTree<T, Node>& _tree, 
00169                  enum BtreeIteratorMode start = BtMinKey) 
00170         {
00171             tree = (AbstractBinaryTree<T, Node> *) (&_tree);
00172             StartAt(start);
00173         }
00174 
00179         void StartAt(enum BtreeIteratorMode start) 
00180         {
00181             ptr = tree->IteratorRoot();
00182             if (start == BtMinKey)
00183                 ptr = ptr->Minimum();
00184             else if (start == BtMaxKey)
00185                 ptr = ptr->Maximum();
00186         }
00190         virtual ~Iterator() { }
00194         virtual void Previous() 
00195         {
00196             if (ptr)
00197                 ptr = ptr->Predecessor();
00198         }
00202         virtual void Next() 
00203         {
00204             if (ptr)
00205                 ptr = ptr->Successor();
00206         }
00210         virtual void Parent() 
00211         {
00212             if (ptr)
00213                 ptr = ptr->parent;
00214         }
00218         virtual void find(  T& x) 
00219         {
00220             ptr = tree->IteratorFind(x);
00221         }
00226         virtual operator int()   
00227         {
00228             return ptr != NULL;
00229         }
00230 
00235         virtual T operator*()   {  return ptr->object; }
00240         virtual T current()   {  return ptr->object; }
00244         virtual Node* current_node()  
00245           { return ptr; }
00251         virtual   T *RefObject()   
00252         {
00253             if (ptr)
00254                 return &ptr->object;
00255             return (T*) NULL;
00256         }
00262         virtual T *Object() 
00263         {
00264             if (ptr)
00265                 return &ptr->object;
00266             return NULL;
00267         }
00271         virtual void operator++() { Next(); }
00275         virtual void operator++(int) { Next(); }
00279         virtual void operator--() { Previous(); }
00283         virtual void operator--(int) { Previous(); }
00284 
00285     protected:
00286         Node *ptr;
00287         AbstractBinaryTree<T, Node> *tree;
00288     };
00289 
00290 protected:
00291     Node *root;
00292     unsigned int count;
00293 };
00294 
00295 /*
00296   class BinaryTree
00297   place holder for others type of binary trees
00298 template<class T>
00299 class BinaryTree : public AbstractBinaryTree<T, BinaryNode<T> > {
00300 public:
00301     BinaryTree() { }
00302 };
00303 */
00304 
00305 
00306 // --------------------------------------------------------
00307 // AbstractBinaryNode implementation.
00308 // --------------------------------------------------------
00309 template<class T, class Node>
00310 AbstractBinaryNode<T, Node>::AbstractBinaryNode(  T& _object, 
00311                           Node *_parent,
00312                           Node *_left, 
00313                           Node *_right) 
00314 {
00315     object = _object;
00316     parent = _parent;
00317     left = _left;
00318     right = _right;
00319 }
00320 
00321 template<class T, class Node>
00322 Node *
00323 AbstractBinaryNode<T, Node>::Clone(Node *_parent)  
00324 {
00325     Node *ret = new Node( *((Node *) this));
00326     if (left)
00327         ret->left = left->Clone(ret);
00328     if (right)
00329         ret->right = right->Clone(ret);
00330     ret->parent = _parent;
00331     return ret;
00332 }
00333 
00334 template<class T, class Node> 
00335 Node *
00336 AbstractBinaryNode<T, Node>::LeftRotate(Node *root)
00337 {
00338     Node *ret = root;
00339     Node *y = right;
00340     right = y->left;
00341     if (right)
00342         right->parent = (Node *) this;
00343     y->parent = parent;
00344     if (parent) {
00345         if (this == parent->left)
00346             parent->left = y;
00347         else
00348             parent->right = y;
00349     }
00350     else
00351         ret = y;
00352     y->left = (Node *) this;
00353     parent = y;
00354     return ret;
00355 }
00356 
00357 template<class T, class Node> 
00358 Node *
00359 AbstractBinaryNode<T, Node>::RightRotate(Node *root)
00360 {
00361     Node *ret = root;
00362     Node *x = left;
00363     left = x->right;
00364     if (left)
00365         left->parent = (Node *) this;
00366     x->parent = parent;
00367     if (parent) {
00368         if (this == parent->left)
00369           parent->left = x;
00370         else
00371           parent->right = x;
00372     }
00373     else
00374         ret = x;
00375     x->right = (Node *) this;
00376     parent = x;
00377     return ret;
00378 }
00379 
00380 template<class T, class Node>
00381 int
00382 AbstractBinaryNode<T, Node>::IsLeftChild()  
00383 {
00384     return (parent && parent->left == (Node *) this);
00385 }
00386 
00387 template<class T, class Node>
00388 int
00389 AbstractBinaryNode<T, Node>::IsRightChild()  
00390 {
00391     return (parent && parent->right == (Node *) this);
00392 }
00393 
00394 template<class T, class Node>
00395 Node *
00396 AbstractBinaryNode<T, Node>::find(  T& x)
00397 {
00398     Node *sc = (Node *) this;
00399     while (sc) {
00400         if (x == sc->object)
00401             return sc;
00402         if (x < sc->object)
00403             sc = sc->left;
00404         else
00405             sc = sc->right;
00406     }
00407     return NULL;
00408 }
00409 
00410 template<class T, class Node>
00411 Node *
00412 AbstractBinaryNode<T, Node>::findNearest(  T& x)
00413 {
00414     Node *sc = (Node *) this;
00415     Node *prev = NULL;
00416     while (sc) {
00417         prev = sc;
00418         if (x < sc->object)
00419             sc = sc->left;
00420         else
00421             sc = sc->right;
00422     }
00423     return prev;
00424 }
00425 
00426 template<class T, class Node>
00427 Node *
00428 AbstractBinaryNode<T, Node>::add(  T& x) 
00429 {
00430     Node *nearest = findNearest(x);
00431     if (x < nearest->object)
00432         nearest->left = new Node(x, nearest);
00433     else
00434         nearest->right = new Node(x, nearest);
00435     return (Node *) this;
00436 }
00437 
00438 template<class T, class Node>
00439 Node *
00440 AbstractBinaryNode<T, Node>::unlink(Node *z)
00441 {
00442     Node *root = (Node *) this;
00443     Node *x, *y;
00444     if (! z)
00445         return root;
00446     if (! z->left || ! z->right)
00447         y = z;
00448     else
00449         y = z->Successor();
00450     if (y->left)
00451         x = y->left;
00452     else
00453         x = y->right;
00454     if (x)
00455         x->parent = y->parent;
00456     if (y->parent) {
00457         if (y == y->parent->left)
00458             y->parent->left = x;
00459         else
00460             y->parent->right = x;
00461     }
00462     else
00463         root = x;
00464     if (y != z)
00465         z->object = y->object;
00466     delete y;
00467     return root;
00468 }
00469 
00470 template<class T, class Node>
00471 Node *
00472 AbstractBinaryNode<T, Node>::Minimum()
00473 {
00474     Node *sc = (Node *) this;
00475     while (sc && sc->left)
00476         sc = sc->left;
00477     return sc;
00478 }
00479 
00480 template<class T, class Node>
00481 Node *
00482 AbstractBinaryNode<T, Node>::Maximum()
00483 {
00484     Node *sc = (Node *) this;
00485     while (sc && sc->right)
00486         sc = sc->right;
00487     return sc;
00488 }
00489 
00490 template<class T, class Node>
00491 Node *
00492 AbstractBinaryNode<T, Node>::Predecessor()
00493 {
00494     if (left)
00495         return left->Maximum();
00496     Node *x = (Node *) this;
00497     Node *y = parent;
00498     while (y && x == y->left) {
00499         x = y;
00500         y = y->parent;
00501     }
00502     return y;
00503 }
00504 
00505 template<class T, class Node>
00506 Node *
00507 AbstractBinaryNode<T, Node>::Successor() 
00508 {
00509     if (right)
00510         return right->Minimum();
00511     Node *x = (Node *) this;
00512     Node *y = parent;
00513     while (y && x == y->right) {
00514         x = y;
00515         y = y->parent;
00516     }
00517     return y;
00518 }
00519 
00520 template<class T, class Node>
00521 void
00522 AbstractBinaryNode<T, Node>::RemoveSubtree()
00523 {
00524     if (left) {
00525         left->RemoveSubtree();
00526         delete  left;
00527     }
00528     if (right) {
00529         right->RemoveSubtree();
00530         delete right;
00531     }
00532 }
00533 
00534 template<class T, class Node>
00535 T *
00536 AbstractBinaryNode<T, Node>::Object()
00537 {
00538     return &object;
00539 }
00540 
00541 template<class T, class Node>
00542 int
00543 AbstractBinaryNode<T, Node>::CheckTreeProperties(  Node *_parent)
00544 {
00545     if (parent != _parent)
00546         return NULL;
00547     if (left) {
00548         if (object < left->object)
00549             return NULL;
00550         if (! left->CheckTreeProperties((Node *) this))
00551             return NULL;
00552     }
00553     if (right) {
00554         if (right->object < object)
00555             return NULL;
00556         if (! right->CheckTreeProperties((Node *) this))
00557             return NULL;
00558     }
00559     return 1;
00560 }
00561 
00562 // --------------------------------------------------------
00563 // AbstractBinaryTree class template implementation.
00564 // --------------------------------------------------------
00565 
00566 template<class T, class Node>
00567 AbstractBinaryTree<T, Node>::AbstractBinaryTree()
00568 {
00569     root = NULL;
00570     count = NULL;
00571 }
00572 
00573 template<class T, class Node>
00574 AbstractBinaryTree<T, Node>::AbstractBinaryTree(  AbstractBinaryTree<T, Node>& x)
00575 {
00576     if (x.root)
00577         root = x.root->Clone(NULL);
00578     else
00579         root = NULL;
00580     count = x.count;
00581 }
00582 
00583 template<class T, class Node>
00584 AbstractBinaryTree<T, Node>&
00585 AbstractBinaryTree<T, Node>::operator=(  AbstractBinaryTree<T, Node>& x)
00586 {
00587     if (root) {
00588         root->RemoveSubtree();
00589         delete root;
00590     }
00591     if (x.root)
00592         root = x.root->Clone(NULL);
00593     else
00594         root = NULL;
00595     count = x.count;
00596     return *this;
00597 }
00598 
00599 template<class T, class Node>
00600 AbstractBinaryTree<T, Node>::~AbstractBinaryTree()
00601 {
00602     if (root) {
00603         root->RemoveSubtree();
00604         delete root;
00605     }
00606 } 
00607 
00608 template<class T, class Node>
00609 void
00610 AbstractBinaryTree<T, Node>::add(  T& x)
00611 {
00612   count++;
00613   if (root == NULL)
00614     root = new Node(x);
00615   else
00616     root = root->add(x);
00617 }
00618 
00619 template<class T, class Node>
00620 Node *
00621 AbstractBinaryTree<T, Node>::IteratorRoot()  
00622 {
00623     return root;
00624 }
00625 
00626 template<class T, class Node>
00627 Node *
00628 AbstractBinaryTree<T, Node>::IteratorFind(  T& x)  
00629 {
00630     return (root) ? root->find(x) : NULL;
00631 }
00632 
00633 template<class T, class Node>
00634 void
00635 AbstractBinaryTree<T, Node>::unlink(  T& _x)
00636 {
00637   count--;
00638   if (! root)
00639     return;
00640   root = root->unlink(root->find(_x));
00641 }
00642 
00643 template<class T, class Node>
00644 T *
00645 AbstractBinaryTree<T, Node>::find(  T& q)
00646 {
00647     Node *p = (root) ? root->find(q) : NULL;
00648     return (p) ? &p->object : NULL;
00649 }
00650 
00651 template<class T, class Node>
00652 int
00653 AbstractBinaryTree<T, Node>::CheckTreeProperties()
00654 {
00655   if (root->CheckTreeProperties(NULL) == NULL)
00656     return NULL;
00657   return 1;
00658 }
00659 
00661 // balanced binary trees 
00662 // (using red & black trees)
00664 typedef enum RedBlack { Black, Red };
00665 template<class T, class Node>
00666 class AbstractRedBlackNode : public AbstractBinaryNode<T, Node> {
00667 public:
00668 
00669   RedBlack clr;
00670   //  ructors.  Node always starts out red.
00671   AbstractRedBlackNode() { clr = Red; }
00672   AbstractRedBlackNode(  T& X, 
00673                        Node *P = NULL,
00674                        Node *L = NULL,
00675                        Node *R = NULL):
00676     AbstractBinaryNode<T, Node>(X, P, L, R) { }
00677   AbstractRedBlackNode(  T& X, RedBlack Clr, Node *P = NULL,
00678                        Node *L = NULL, Node *R = NULL):
00679     AbstractBinaryNode<T, Node>(X, P, L, R), clr(Clr) { }
00680   virtual ~AbstractRedBlackNode() { }
00681 
00682     // Tree manipulations used during insertion and deletion
00683     virtual Node *RemoveFixup(Node *x, Node *p);
00684     
00685     // Operations defined on binary trees.  All run in O(lgN) time.
00686     virtual Node *add(  T& AddMe);
00687     virtual Node *unlink(Node *z);
00688     
00689     // Returns NULL if the red-black invariant holds.
00690     virtual int CheckTreeProperties(  Node *);
00691 };
00692 
00693 template<class T>
00694 class RedBlackNode : public AbstractRedBlackNode<T, RedBlackNode<T> > {
00695 public:
00696 
00697     //  ructors.  Node always starts out red.
00698     RedBlackNode() { }
00699     RedBlackNode(  T& X, 
00700                  RedBlackNode<T> *P = NULL,
00701                  RedBlackNode<T> *L = NULL,
00702                  RedBlackNode<T> *R = NULL):
00703         AbstractRedBlackNode<T, RedBlackNode<T> >(X, P, L, R) { }
00704     RedBlackNode(  T& X, RedBlack Clr, RedBlackNode<T> *P = NULL,
00705             RedBlackNode<T> *L = NULL, RedBlackNode<T> *R = NULL):
00706         AbstractRedBlackNode<T, RedBlackNode<T> >(X, Clr, P, L, R) { }
00707     virtual ~RedBlackNode() { }
00708 };
00709 
00710 
00711 
00716 template<class T, class Node> 
00717 class AbstractRedBlackTree : public AbstractBinaryTree<T, Node> {
00718 protected:
00719     virtual Node *FindNode(T q)  
00720         { return (AbstractBinaryTree<T, Node>::root) ? (Node *) root->find(q) : NULL; }
00721 };
00722 
00770 template <class T>
00771 class VDKBtree : public AbstractRedBlackTree<T, RedBlackNode<T> > {
00772 public:
00776     VDKBtree() { }
00777 };
00778 
00779 
00780 template<class T, class Node> 
00781 Node *
00782 AbstractRedBlackNode<T, Node>::add(  T& AddMe)
00783 {
00784     Node *root = (Node *) this;
00785     Node *x = (Node *) this;
00786     Node *y = NULL;
00787     while (x) {
00788         y = x;
00789         x = (AddMe < x->object) ? x->left : x->right;
00790     }
00791     Node *addme = new Node(AddMe, y);
00792     if (! y)
00793         root = addme;
00794     else {
00795       if (AddMe < y->object)
00796           y->left = addme;
00797       else
00798           y->right = addme;
00799     }
00800     addme->clr = Red;
00801     while (addme != root && 
00802            addme->parent->parent && 
00803            addme->parent->clr == Red) {
00804         Node *y;
00805 
00806         if (addme->parent == addme->parent->parent->left) {
00807             y = addme->parent->parent->right;
00808             if (y && y->clr == Red) {
00809                 // Case 1: x's uncle is red
00810                 addme->parent->clr = Black;
00811                 y->clr = Black;
00812                 addme->parent->parent->clr = Red;
00813                 addme = addme->parent->parent;
00814             }
00815             else {
00816                 if (addme == addme->parent->right) {
00817                     // Case 2: x is a right child
00818                     // Rotate to transform to case 3
00819                     addme = addme->parent;
00820                     root = addme->LeftRotate(root);
00821                 }
00822                 // Case 3: x is a left child
00823                 addme->parent->clr = Black;
00824                 if (addme->parent->parent) {
00825                     addme->parent->parent->clr = Red;
00826                     root = addme->parent->parent->RightRotate(root);
00827                 }
00828                 // The while loop will terminate 
00829                 // on the next iteration.
00830             }
00831         }
00832         else {
00833             y = addme->parent->parent->left;
00834             if (y && y->clr == Red) {
00835                 addme->parent->clr = Black;
00836                 y->clr = Black;
00837                 addme->parent->parent->clr = Red;
00838                 addme = addme->parent->parent;
00839             }
00840             else {
00841                 if (addme == addme->parent->left) {
00842                   addme = addme->parent;
00843                   root = addme->RightRotate(root);
00844                 }
00845                 addme->parent->clr = Black;
00846                 if (addme->parent->parent) {
00847                     addme->parent->parent->clr = Red;
00848                     root = addme->parent->parent->LeftRotate(root);
00849                 }
00850             }
00851         }
00852     }
00853     root->clr = Black;
00854     return root;
00855 }
00856 
00857 template<class T, class Node> 
00858 Node *
00859 AbstractRedBlackNode<T, Node>::RemoveFixup(Node *x, Node *p)
00860 {
00861     Node *root = (Node *) this;
00862 
00863     while (x != root && (! x || x->clr == Black)) {
00864         Node *w;
00865         if (x == p->left) {
00866             if (! p)
00867                 return root;
00868             w = p->right;
00869             if (! w)
00870                 return root;
00871             if (w->clr == Red) {
00872                 w->clr = Black;
00873                 p->clr = Red;
00874                 root = p->LeftRotate(root);
00875                 w = p->right;
00876                 if (! p || ! w)
00877                     return root;
00878             }
00879             if ( ((! w->left) || w->left->clr == Black) &&
00880                  ((! w->right) || w->right->clr == Black)) {
00881                   w->clr = Red;
00882                   x = p;
00883                   p = p->parent;
00884                   continue;
00885             }
00886             else if ((! w->right) || w->right->clr == Black) {
00887                 w->left->clr = Black;
00888                 w->clr = Red;
00889                 root = w->RightRotate(root);
00890                 w = p->right;
00891                 if (! p || ! w)
00892                     return root;
00893             }
00894             w->clr = p->clr;
00895             if (p)
00896                 p->clr = Black;
00897             w->right->clr = Black;
00898             if (p)
00899                 root = p->LeftRotate(root);
00900             x = root;
00901         }
00902         else {
00903             if (! p)
00904                 return root;
00905             w = p->left;
00906             if (! p || ! w)
00907                 return root;
00908             if (w->clr == Red) {
00909                 w->clr = Black;
00910                 p->clr = Red;
00911                 root = p->RightRotate(root);
00912                 w = p->left;
00913                 if (! p || ! w)
00914                     return root;
00915             }
00916             if ( ((! w->right) || w->right->clr == Black) &&
00917                  ((! w->left) || w->left->clr == Black)) {
00918                 w->clr = Red;
00919                 x = p;
00920                 p = p->parent;
00921                 continue;
00922             }
00923             else if ((! w->left) || w->left->clr == Black) {
00924                 w->right->clr = Black;
00925                 w->clr = Red;
00926                 root = w->LeftRotate(root);
00927                 w = p->left;
00928                 if (! p || ! w)
00929                     return root;
00930             }
00931             w->clr = p->clr;
00932             if (p)
00933                 p->clr = Black;
00934             w->left->clr = Black;
00935             if (p)
00936                 root = p->RightRotate(root);
00937             x = root;
00938         }
00939     }
00940     if (x)
00941         x->clr = Black;
00942     return root;
00943 }
00944 
00945 template<class T, class Node> 
00946 Node *
00947 AbstractRedBlackNode<T, Node>::unlink(Node *z)
00948 {
00949     Node *root = (Node *) this;
00950     Node *x, *y;
00951 
00952     if (! z)
00953         return root;
00954     y = (! z->left || ! z->right) ? z : (Node *) z->Successor();
00955     x = (y->left) ? y->left : y->right;
00956 
00957     if (x)
00958         x->parent = y->parent;
00959 
00960     if (y->parent) {
00961         if (y == y->parent->left)
00962             y->parent->left = x;
00963         else
00964             y->parent->right = x;
00965     }
00966     else
00967         root = x;
00968     if (y != z)
00969         z->object = y->object;
00970     if (y->clr == Black) {
00971         if (root)
00972             root = root->RemoveFixup(x, y->parent);
00973     }
00974     delete y;
00975     return root;
00976 }
00977 
00978 template<class T, class Node> 
00979 int
00980 AbstractRedBlackNode<T, Node>::CheckTreeProperties(  Node *_parent)
00981 {
00982     static int BlackHeight;
00983 
00984     if (_parent == NULL)
00985         BlackHeight = -1;
00986 
00987     // Check binary tree properties.
00988     if (parent != _parent)
00989         return NULL;
00990     if (left) {
00991         if (object < left->object)
00992             return NULL;
00993     }
00994     if (right) {
00995         if (right->object < object)
00996             return NULL;
00997     }
00998 
00999     // Now check red-black tree properties.
01000 
01001     // If a node is red, then both its children are black
01002     // (NULL nodes are black).
01003     if (clr == Red) {
01004         if ((left && left->clr != Black) ||
01005             (right && right->clr != Black))
01006             return NULL;
01007     }
01008 
01009     // The black-heights of all leaf nodes are equal.
01010     int bh = NULL;
01011 
01012     if ((! left) && (! right)) {
01013         // Compute black-height of node
01014         for (Node *sc = (Node *) this; sc; sc = sc->parent)
01015             if (sc->clr == Black)
01016                 bh += 1;
01017 
01018         if (BlackHeight == -1) {
01019             BlackHeight = bh;
01020         }
01021         else {
01022             if (bh != BlackHeight)
01023                 return NULL;
01024         }
01025     }
01026     if (left && (! left->CheckTreeProperties((Node *) this)))
01027         return NULL;
01028     if (right && (! right->CheckTreeProperties((Node *) this)))
01029         return NULL;
01030     return 1;
01031 }
01032 #endif
01033 
01034 
01035 
01036 
01037 

Generated on Tue Oct 26 18:58:51 2004 for vdk 2.4.0 by  doxygen 1.3.9.1