vdk 2.4.0
|
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 *) this->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 (this->parent != _parent) 00989 return NULL; 00990 if (this->left) { 00991 if (this->object < this->left->object) 00992 return NULL; 00993 } 00994 if (this->right) { 00995 if (this->right->object < this->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 ((this->left && this->left->clr != Black) || 01005 (this->right && this->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 ((! this->left) && (! this->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 (this->left && (! this->left->CheckTreeProperties((Node *) this))) 01027 return NULL; 01028 if (this->right && (! this->right->CheckTreeProperties((Node *) this))) 01029 return NULL; 01030 return 1; 01031 } 01032 #endif 01033 01034 01035 01036 01037