38 template<
class T,
class Node>
39 class AbstractBinaryNode {
41 AbstractBinaryNode() { }
42 AbstractBinaryNode( T& _object,
46 virtual ~AbstractBinaryNode() { }
49 virtual Node *Clone(Node *_parent) ;
50 virtual void RemoveSubtree();
51 virtual Node *LeftRotate(Node *root);
52 virtual Node *RightRotate(Node *root);
53 virtual int CheckTreeProperties( Node *);
54 virtual int IsLeftChild() ;
55 virtual int IsRightChild() ;
57 virtual Node *add( T& x);
58 virtual Node *unlink(Node *z);
61 virtual Node *find( T& x);
62 virtual Node *findNearest( T& x);
65 virtual Node *Minimum();
66 virtual Node *Maximum();
67 virtual Node *Predecessor();
68 virtual Node *Successor();
75 Node *left, *right, *parent;
80 class BinaryNode :
public AbstractBinaryNode<T, BinaryNode<T> > {
84 BinaryNode( T&
object,
85 BinaryNode<T> *parent = NULL,
86 BinaryNode<T> *left = NULL,
87 BinaryNode<T> *right = NULL):
88 AbstractBinaryNode<T, BinaryNode<T> >(object, parent, left, right) { }
89 virtual ~BinaryNode() { }
101 enum BtreeIteratorMode { BtMinKey, BtRootKey, BtMaxKey };
106 template<
class T,
class Node>
125 virtual void add( T&);
133 virtual T *
find( T& q);
137 virtual int IsEmpty() {
return root == NULL; }
142 virtual Node *IteratorRoot() ;
146 virtual Node *IteratorFind( T& x) ;
154 unsigned int size() {
return count; }
169 enum BtreeIteratorMode start = BtMinKey)
181 ptr = tree->IteratorRoot();
182 if (start == BtMinKey)
183 ptr = ptr->Minimum();
184 else if (start == BtMaxKey)
185 ptr = ptr->Maximum();
197 ptr = ptr->Predecessor();
205 ptr = ptr->Successor();
218 virtual void find( T& x)
220 ptr = tree->IteratorFind(x);
226 virtual operator int()
244 virtual Node* current_node()
309 template<
class T,
class Node>
310 AbstractBinaryNode<T, Node>::AbstractBinaryNode( T& _object,
321 template<
class T,
class Node>
323 AbstractBinaryNode<T, Node>::Clone(Node *_parent)
325 Node *ret =
new Node( *((Node *)
this));
327 ret->left = left->Clone(ret);
329 ret->right = right->Clone(ret);
330 ret->parent = _parent;
334 template<
class T,
class Node>
336 AbstractBinaryNode<T, Node>::LeftRotate(Node *root)
342 right->parent = (Node *)
this;
345 if (
this == parent->left)
352 y->left = (Node *)
this;
357 template<
class T,
class Node>
359 AbstractBinaryNode<T, Node>::RightRotate(Node *root)
365 left->parent = (Node *)
this;
368 if (
this == parent->left)
375 x->right = (Node *)
this;
380 template<
class T,
class Node>
382 AbstractBinaryNode<T, Node>::IsLeftChild()
384 return (parent && parent->left == (Node *)
this);
387 template<
class T,
class Node>
389 AbstractBinaryNode<T, Node>::IsRightChild()
391 return (parent && parent->right == (Node *)
this);
394 template<
class T,
class Node>
396 AbstractBinaryNode<T, Node>::find( T& x)
398 Node *sc = (Node *)
this;
410 template<
class T,
class Node>
412 AbstractBinaryNode<T, Node>::findNearest( T& x)
414 Node *sc = (Node *)
this;
426 template<
class T,
class Node>
428 AbstractBinaryNode<T, Node>::add( T& x)
430 Node *nearest = findNearest(x);
431 if (x < nearest->
object)
432 nearest->left =
new Node(x, nearest);
434 nearest->right =
new Node(x, nearest);
435 return (Node *)
this;
438 template<
class T,
class Node>
440 AbstractBinaryNode<T, Node>::unlink(Node *z)
442 Node *root = (Node *)
this;
446 if (! z->left || ! z->right)
455 x->parent = y->parent;
457 if (y == y->parent->left)
460 y->parent->right = x;
465 z->object = y->object;
470 template<
class T,
class Node>
472 AbstractBinaryNode<T, Node>::Minimum()
474 Node *sc = (Node *)
this;
475 while (sc && sc->left)
480 template<
class T,
class Node>
482 AbstractBinaryNode<T, Node>::Maximum()
484 Node *sc = (Node *)
this;
485 while (sc && sc->right)
490 template<
class T,
class Node>
492 AbstractBinaryNode<T, Node>::Predecessor()
495 return left->Maximum();
496 Node *x = (Node *)
this;
498 while (y && x == y->left) {
505 template<
class T,
class Node>
507 AbstractBinaryNode<T, Node>::Successor()
510 return right->Minimum();
511 Node *x = (Node *)
this;
513 while (y && x == y->right) {
520 template<
class T,
class Node>
522 AbstractBinaryNode<T, Node>::RemoveSubtree()
525 left->RemoveSubtree();
529 right->RemoveSubtree();
534 template<
class T,
class Node>
536 AbstractBinaryNode<T, Node>::Object()
541 template<
class T,
class Node>
543 AbstractBinaryNode<T, Node>::CheckTreeProperties( Node *_parent)
545 if (parent != _parent)
548 if (object < left->
object)
550 if (! left->CheckTreeProperties((Node *)
this))
554 if (right->object <
object)
556 if (! right->CheckTreeProperties((Node *)
this))
566 template<
class T,
class Node>
573 template<
class T,
class Node>
577 root = x.root->Clone(NULL);
583 template<
class T,
class Node>
588 root->RemoveSubtree();
592 root = x.root->Clone(NULL);
599 template<
class T,
class Node>
603 root->RemoveSubtree();
608 template<
class T,
class Node>
619 template<
class T,
class Node>
626 template<
class T,
class Node>
630 return (root) ? root->
find(x) : NULL;
633 template<
class T,
class Node>
640 root = root->unlink(root->find(_x));
643 template<
class T,
class Node>
647 Node *p = (root) ? root->find(q) : NULL;
648 return (p) ? &p->object : NULL;
651 template<
class T,
class Node>
655 if (root->CheckTreeProperties(NULL) == NULL)
664 typedef enum RedBlack { Black, Red };
665 template<
class T,
class Node>
666 class AbstractRedBlackNode :
public AbstractBinaryNode<T, Node> {
671 AbstractRedBlackNode() { clr = Red; }
672 AbstractRedBlackNode( T& X,
676 AbstractBinaryNode<T, Node>(X, P, L, R) { }
677 AbstractRedBlackNode( T& X, RedBlack Clr, Node *P = NULL,
678 Node *L = NULL, Node *R = NULL):
679 AbstractBinaryNode<T, Node>(X, P, L, R), clr(Clr) { }
680 virtual ~AbstractRedBlackNode() { }
683 virtual Node *RemoveFixup(Node *x, Node *p);
686 virtual Node *add( T& AddMe);
687 virtual Node *unlink(Node *z);
690 virtual int CheckTreeProperties( Node *);
694 class RedBlackNode :
public AbstractRedBlackNode<T, RedBlackNode<T> > {
700 RedBlackNode<T> *P = NULL,
701 RedBlackNode<T> *L = NULL,
702 RedBlackNode<T> *R = NULL):
703 AbstractRedBlackNode<T, RedBlackNode<T> >(X, P, L, R) { }
704 RedBlackNode( T& X, RedBlack Clr, RedBlackNode<T> *P = NULL,
705 RedBlackNode<T> *L = NULL, RedBlackNode<T> *R = NULL):
706 AbstractRedBlackNode<T, RedBlackNode<T> >(X, Clr, P, L, R) { }
707 virtual ~RedBlackNode() { }
716 template<
class T,
class Node>
719 virtual Node *FindNode(T q)
780 template<
class T,
class Node>
782 AbstractRedBlackNode<T, Node>::add( T& AddMe)
784 Node *root = (Node *)
this;
785 Node *x = (Node *)
this;
789 x = (AddMe < x->object) ? x->left : x->right;
791 Node *addme =
new Node(AddMe, y);
795 if (AddMe < y->
object)
801 while (addme != root &&
802 addme->parent->parent &&
803 addme->parent->clr == Red) {
806 if (addme->parent == addme->parent->parent->left) {
807 y = addme->parent->parent->right;
808 if (y && y->clr == Red) {
810 addme->parent->clr = Black;
812 addme->parent->parent->clr = Red;
813 addme = addme->parent->parent;
816 if (addme == addme->parent->right) {
819 addme = addme->parent;
820 root = addme->LeftRotate(root);
823 addme->parent->clr = Black;
824 if (addme->parent->parent) {
825 addme->parent->parent->clr = Red;
826 root = addme->parent->parent->RightRotate(root);
833 y = addme->parent->parent->left;
834 if (y && y->clr == Red) {
835 addme->parent->clr = Black;
837 addme->parent->parent->clr = Red;
838 addme = addme->parent->parent;
841 if (addme == addme->parent->left) {
842 addme = addme->parent;
843 root = addme->RightRotate(root);
845 addme->parent->clr = Black;
846 if (addme->parent->parent) {
847 addme->parent->parent->clr = Red;
848 root = addme->parent->parent->LeftRotate(root);
857 template<
class T,
class Node>
859 AbstractRedBlackNode<T, Node>::RemoveFixup(Node *x, Node *p)
861 Node *root = (Node *)
this;
863 while (x != root && (! x || x->clr == Black)) {
874 root = p->LeftRotate(root);
879 if ( ((! w->left) || w->left->clr == Black) &&
880 ((! w->right) || w->right->clr == Black)) {
886 else if ((! w->right) || w->right->clr == Black) {
887 w->left->clr = Black;
889 root = w->RightRotate(root);
897 w->right->clr = Black;
899 root = p->LeftRotate(root);
911 root = p->RightRotate(root);
916 if ( ((! w->right) || w->right->clr == Black) &&
917 ((! w->left) || w->left->clr == Black)) {
923 else if ((! w->left) || w->left->clr == Black) {
924 w->right->clr = Black;
926 root = w->LeftRotate(root);
934 w->left->clr = Black;
936 root = p->RightRotate(root);
945 template<
class T,
class Node>
947 AbstractRedBlackNode<T, Node>::unlink(Node *z)
949 Node *root = (Node *)
this;
954 y = (! z->left || ! z->right) ? z : (Node *) z->Successor();
955 x = (y->left) ? y->left : y->right;
958 x->parent = y->parent;
961 if (y == y->parent->left)
964 y->parent->right = x;
969 z->object = y->object;
970 if (y->clr == Black) {
972 root = root->RemoveFixup(x, y->parent);
978 template<
class T,
class Node>
980 AbstractRedBlackNode<T, Node>::CheckTreeProperties( Node *_parent)
982 static int BlackHeight;
988 if (this->parent != _parent)
991 if (this->object < this->left->object)
995 if (this->right->object < this->object)
1004 if ((this->left && this->left->clr != Black) ||
1005 (this->right && this->right->clr != Black))
1012 if ((! this->left) && (! this->right)) {
1014 for (Node *sc = (Node *)
this; sc; sc = sc->parent)
1015 if (sc->clr == Black)
1018 if (BlackHeight == -1) {
1022 if (bh != BlackHeight)
1026 if (this->left && (! this->left->CheckTreeProperties((Node *)
this)))
1028 if (this->right && (! this->right->CheckTreeProperties((Node *)
this)))
virtual void add(T &)
Definition: vdkbtrees.h:610
VDKBtree()
Definition: vdkbtrees.h:776
virtual void operator--()
Definition: vdkbtrees.h:279
virtual int IsEmpty()
Definition: vdkbtrees.h:137
unsigned int size()
Definition: vdkbtrees.h:154
virtual int CheckTreeProperties()
Definition: vdkbtrees.h:653
Iterator(AbstractBinaryTree< T, Node > &_tree, enum BtreeIteratorMode start=BtMinKey)
Definition: vdkbtrees.h:168
Provides a nlog(n) iterator for AbstractBinaryTree.
Definition: vdkbtrees.h:157
virtual T * Object()
Definition: vdkbtrees.h:262
provides a templatized binary tree data structure
Definition: vdkbtrees.h:771
virtual void operator++()
Definition: vdkbtrees.h:271
provides an abstract class for concrete VDKBtree class
Definition: vdkbtrees.h:107
virtual T * RefObject()
Definition: vdkbtrees.h:251
virtual ~Iterator()
Definition: vdkbtrees.h:190
AbstractBinaryTree< T, Node > & operator=(AbstractBinaryTree< T, Node > &)
Definition: vdkbtrees.h:585
virtual void Previous()
Definition: vdkbtrees.h:194
virtual void unlink(T &)
Definition: vdkbtrees.h:635
virtual void Parent()
Definition: vdkbtrees.h:210
virtual T current()
Definition: vdkbtrees.h:240
provides an abstract frame class for VDKBTree
Definition: vdkbtrees.h:717
virtual void operator++(int)
Definition: vdkbtrees.h:275
virtual void Next()
Definition: vdkbtrees.h:202
virtual void operator--(int)
Definition: vdkbtrees.h:283
virtual T * find(T &q)
Definition: vdkbtrees.h:645
virtual T operator*()
Definition: vdkbtrees.h:235
void StartAt(enum BtreeIteratorMode start)
Definition: vdkbtrees.h:179