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