00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
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
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
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
00057 virtual Node *add( T& x);
00058 virtual Node *unlink(Node *z);
00059
00060
00061 virtual Node *find( T& x);
00062 virtual Node *findNearest( T& x);
00063
00064
00065 virtual Node *Minimum();
00066 virtual Node *Maximum();
00067 virtual Node *Predecessor();
00068 virtual Node *Successor();
00069
00070
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
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
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&);
00129 virtual void unlink( T&);
00133 virtual T *find( T& q);
00137 virtual int IsEmpty() { return root == NULL; }
00138
00139
00140
00141
00142 virtual Node *IteratorRoot() ;
00143
00144
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
00297
00298
00299
00300
00301
00302
00303
00304
00305
00306
00307
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
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
00662
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
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
00683 virtual Node *RemoveFixup(Node *x, Node *p);
00684
00685
00686 virtual Node *add( T& AddMe);
00687 virtual Node *unlink(Node *z);
00688
00689
00690 virtual int CheckTreeProperties( Node *);
00691 };
00692
00693 template<class T>
00694 class RedBlackNode : public AbstractRedBlackNode<T, RedBlackNode<T> > {
00695 public:
00696
00697
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
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
00818
00819 addme = addme->parent;
00820 root = addme->LeftRotate(root);
00821 }
00822
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
00829
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
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
01000
01001
01002
01003 if (clr == Red) {
01004 if ((left && left->clr != Black) ||
01005 (right && right->clr != Black))
01006 return NULL;
01007 }
01008
01009
01010 int bh = NULL;
01011
01012 if ((! left) && (! right)) {
01013
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