vdk 2.4.0
vdkbtrees.h
1/*
2 * ===========================
3 * VDK Visual Development Kit
4 * Version 0.5
5 * November 1998
6 * ===========================
7 *
8 * Copyright (C) 1998, Mario Motta
9 * Developed by Mario Motta <mmotta@guest.net>
10 *
11 * This library is free software; you can redistribute it and/or
12 * modify it under the terms of the GNU Library General Public
13 * License as published by the Free Software Foundation; either
14 * version 2 of the License, or (at your option) any later version.
15 *
16 * This library is distributed in the hope that it will be useful,
17 * but WITHOUT ANY WARRANTY; without even the implied warranty of
18 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
19 * Library General Public License for more details.
20 *
21 * You should have received a copy of the GNU Library General Public
22 * License along with this library; if not, write to the Free Software
23 * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
24 * 02111-1307, USA.
25 *
26 */
27
28#ifndef VDKBTREES_H
29#define VDKBTREES_H
30#ifdef NULL
31#undef NULL
32#define NULL 0x0000
33#endif
34// --------------------------
35// Abstract class template,
36// --------------------------
37
38template<class T, class Node>
39class AbstractBinaryNode {
40public:
41 AbstractBinaryNode() { }
42 AbstractBinaryNode( T& _object,
43 Node *_parent = NULL,
44 Node *_left = NULL,
45 Node *_right = NULL);
46 virtual ~AbstractBinaryNode() { }
47
48 // Subtree arrangement
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() ;
56 // Adding a node and deleting
57 virtual Node *add( T& x);
58 virtual Node *unlink(Node *z);
59
60 // Find
61 virtual Node *find( T& x);
62 virtual Node *findNearest( T& x);
63
64 // Tree trasverse
65 virtual Node *Minimum();
66 virtual Node *Maximum();
67 virtual Node *Predecessor();
68 virtual Node *Successor();
69
70 // Miscellaneous
71 virtual T *Object();
72
73public:
74 T object;
75 Node *left, *right, *parent;
76
77};
78
79template<class T>
80class BinaryNode : public AbstractBinaryNode<T, BinaryNode<T> > {
81public:
82 // ructors and destructor
83 BinaryNode() { }
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() { }
90};
91
93// Iterator class
101enum BtreeIteratorMode { BtMinKey, BtRootKey, BtMaxKey };
106template<class T, class Node>
108
109public:
110
120 virtual ~AbstractBinaryTree();
121
125 virtual void add( T&); // Add a node
129 virtual void unlink( T&); // Remove a node
133 virtual T *find( T& q);
137 virtual int IsEmpty() { return root == NULL; }
138
139 /*
140 \internal
141 */
142 virtual Node *IteratorRoot() ;
143 /*
144 \internal
145 */
146 virtual Node *IteratorFind( T& x) ;
150 virtual int CheckTreeProperties();
154 unsigned int size() { return count; }
155
156
157 class Iterator {
158
159 public:
169 enum BtreeIteratorMode start = BtMinKey)
170 {
171 tree = (AbstractBinaryTree<T, Node> *) (&_tree);
172 StartAt(start);
173 }
174
179 void StartAt(enum BtreeIteratorMode start)
180 {
181 ptr = tree->IteratorRoot();
182 if (start == BtMinKey)
183 ptr = ptr->Minimum();
184 else if (start == BtMaxKey)
185 ptr = ptr->Maximum();
186 }
190 virtual ~Iterator() { }
194 virtual void Previous()
195 {
196 if (ptr)
197 ptr = ptr->Predecessor();
198 }
202 virtual void Next()
203 {
204 if (ptr)
205 ptr = ptr->Successor();
206 }
210 virtual void Parent()
211 {
212 if (ptr)
213 ptr = ptr->parent;
214 }
218 virtual void find( T& x)
219 {
220 ptr = tree->IteratorFind(x);
221 }
226 virtual operator int()
227 {
228 return ptr != NULL;
229 }
230
235 virtual T operator*() { return ptr->object; }
240 virtual T current() { return ptr->object; }
244 virtual Node* current_node()
245 { return ptr; }
251 virtual T *RefObject()
252 {
253 if (ptr)
254 return &ptr->object;
255 return (T*) NULL;
256 }
262 virtual T *Object()
263 {
264 if (ptr)
265 return &ptr->object;
266 return NULL;
267 }
271 virtual void operator++() { Next(); }
275 virtual void operator++(int) { Next(); }
279 virtual void operator--() { Previous(); }
283 virtual void operator--(int) { Previous(); }
284
285 protected:
286 Node *ptr;
288 };
289
290protected:
291 Node *root;
292 unsigned int count;
293};
294
295/*
296 class BinaryTree
297 place holder for others type of binary trees
298template<class T>
299class BinaryTree : public AbstractBinaryTree<T, BinaryNode<T> > {
300public:
301 BinaryTree() { }
302};
303*/
304
305
306// --------------------------------------------------------
307// AbstractBinaryNode implementation.
308// --------------------------------------------------------
309template<class T, class Node>
310AbstractBinaryNode<T, Node>::AbstractBinaryNode( T& _object,
311 Node *_parent,
312 Node *_left,
313 Node *_right)
314{
315 object = _object;
316 parent = _parent;
317 left = _left;
318 right = _right;
319}
320
321template<class T, class Node>
322Node *
323AbstractBinaryNode<T, Node>::Clone(Node *_parent)
324{
325 Node *ret = new Node( *((Node *) this));
326 if (left)
327 ret->left = left->Clone(ret);
328 if (right)
329 ret->right = right->Clone(ret);
330 ret->parent = _parent;
331 return ret;
332}
333
334template<class T, class Node>
335Node *
336AbstractBinaryNode<T, Node>::LeftRotate(Node *root)
337{
338 Node *ret = root;
339 Node *y = right;
340 right = y->left;
341 if (right)
342 right->parent = (Node *) this;
343 y->parent = parent;
344 if (parent) {
345 if (this == parent->left)
346 parent->left = y;
347 else
348 parent->right = y;
349 }
350 else
351 ret = y;
352 y->left = (Node *) this;
353 parent = y;
354 return ret;
355}
356
357template<class T, class Node>
358Node *
359AbstractBinaryNode<T, Node>::RightRotate(Node *root)
360{
361 Node *ret = root;
362 Node *x = left;
363 left = x->right;
364 if (left)
365 left->parent = (Node *) this;
366 x->parent = parent;
367 if (parent) {
368 if (this == parent->left)
369 parent->left = x;
370 else
371 parent->right = x;
372 }
373 else
374 ret = x;
375 x->right = (Node *) this;
376 parent = x;
377 return ret;
378}
379
380template<class T, class Node>
381int
382AbstractBinaryNode<T, Node>::IsLeftChild()
383{
384 return (parent && parent->left == (Node *) this);
385}
386
387template<class T, class Node>
388int
389AbstractBinaryNode<T, Node>::IsRightChild()
390{
391 return (parent && parent->right == (Node *) this);
392}
393
394template<class T, class Node>
395Node *
396AbstractBinaryNode<T, Node>::find( T& x)
397{
398 Node *sc = (Node *) this;
399 while (sc) {
400 if (x == sc->object)
401 return sc;
402 if (x < sc->object)
403 sc = sc->left;
404 else
405 sc = sc->right;
406 }
407 return NULL;
408}
409
410template<class T, class Node>
411Node *
412AbstractBinaryNode<T, Node>::findNearest( T& x)
413{
414 Node *sc = (Node *) this;
415 Node *prev = NULL;
416 while (sc) {
417 prev = sc;
418 if (x < sc->object)
419 sc = sc->left;
420 else
421 sc = sc->right;
422 }
423 return prev;
424}
425
426template<class T, class Node>
427Node *
428AbstractBinaryNode<T, Node>::add( T& x)
429{
430 Node *nearest = findNearest(x);
431 if (x < nearest->object)
432 nearest->left = new Node(x, nearest);
433 else
434 nearest->right = new Node(x, nearest);
435 return (Node *) this;
436}
437
438template<class T, class Node>
439Node *
440AbstractBinaryNode<T, Node>::unlink(Node *z)
441{
442 Node *root = (Node *) this;
443 Node *x, *y;
444 if (! z)
445 return root;
446 if (! z->left || ! z->right)
447 y = z;
448 else
449 y = z->Successor();
450 if (y->left)
451 x = y->left;
452 else
453 x = y->right;
454 if (x)
455 x->parent = y->parent;
456 if (y->parent) {
457 if (y == y->parent->left)
458 y->parent->left = x;
459 else
460 y->parent->right = x;
461 }
462 else
463 root = x;
464 if (y != z)
465 z->object = y->object;
466 delete y;
467 return root;
468}
469
470template<class T, class Node>
471Node *
472AbstractBinaryNode<T, Node>::Minimum()
473{
474 Node *sc = (Node *) this;
475 while (sc && sc->left)
476 sc = sc->left;
477 return sc;
478}
479
480template<class T, class Node>
481Node *
482AbstractBinaryNode<T, Node>::Maximum()
483{
484 Node *sc = (Node *) this;
485 while (sc && sc->right)
486 sc = sc->right;
487 return sc;
488}
489
490template<class T, class Node>
491Node *
492AbstractBinaryNode<T, Node>::Predecessor()
493{
494 if (left)
495 return left->Maximum();
496 Node *x = (Node *) this;
497 Node *y = parent;
498 while (y && x == y->left) {
499 x = y;
500 y = y->parent;
501 }
502 return y;
503}
504
505template<class T, class Node>
506Node *
507AbstractBinaryNode<T, Node>::Successor()
508{
509 if (right)
510 return right->Minimum();
511 Node *x = (Node *) this;
512 Node *y = parent;
513 while (y && x == y->right) {
514 x = y;
515 y = y->parent;
516 }
517 return y;
518}
519
520template<class T, class Node>
521void
522AbstractBinaryNode<T, Node>::RemoveSubtree()
523{
524 if (left) {
525 left->RemoveSubtree();
526 delete left;
527 }
528 if (right) {
529 right->RemoveSubtree();
530 delete right;
531 }
532}
533
534template<class T, class Node>
535T *
536AbstractBinaryNode<T, Node>::Object()
537{
538 return &object;
539}
540
541template<class T, class Node>
542int
543AbstractBinaryNode<T, Node>::CheckTreeProperties( Node *_parent)
544{
545 if (parent != _parent)
546 return NULL;
547 if (left) {
548 if (object < left->object)
549 return NULL;
550 if (! left->CheckTreeProperties((Node *) this))
551 return NULL;
552 }
553 if (right) {
554 if (right->object < object)
555 return NULL;
556 if (! right->CheckTreeProperties((Node *) this))
557 return NULL;
558 }
559 return 1;
560}
561
562// --------------------------------------------------------
563// AbstractBinaryTree class template implementation.
564// --------------------------------------------------------
565
566template<class T, class Node>
568{
569 root = NULL;
570 count = NULL;
571}
572
573template<class T, class Node>
575{
576 if (x.root)
577 root = x.root->Clone(NULL);
578 else
579 root = NULL;
580 count = x.count;
581}
582
583template<class T, class Node>
586{
587 if (root) {
588 root->RemoveSubtree();
589 delete root;
590 }
591 if (x.root)
592 root = x.root->Clone(NULL);
593 else
594 root = NULL;
595 count = x.count;
596 return *this;
597}
598
599template<class T, class Node>
601{
602 if (root) {
603 root->RemoveSubtree();
604 delete root;
605 }
606}
607
608template<class T, class Node>
609void
611{
612 count++;
613 if (root == NULL)
614 root = new Node(x);
615 else
616 root = root->add(x);
617}
618
619template<class T, class Node>
620Node *
622{
623 return root;
624}
625
626template<class T, class Node>
627Node *
629{
630 return (root) ? root->find(x) : NULL;
631}
632
633template<class T, class Node>
634void
636{
637 count--;
638 if (! root)
639 return;
640 root = root->unlink(root->find(_x));
641}
642
643template<class T, class Node>
644T *
646{
647 Node *p = (root) ? root->find(q) : NULL;
648 return (p) ? &p->object : NULL;
649}
650
651template<class T, class Node>
652int
654{
655 if (root->CheckTreeProperties(NULL) == NULL)
656 return NULL;
657 return 1;
658}
659
661// balanced binary trees
662// (using red & black trees)
664typedef enum RedBlack { Black, Red };
665template<class T, class Node>
666class AbstractRedBlackNode : public AbstractBinaryNode<T, Node> {
667public:
668
669 RedBlack clr;
670 // ructors. Node always starts out red.
671 AbstractRedBlackNode() { clr = Red; }
672 AbstractRedBlackNode( T& X,
673 Node *P = NULL,
674 Node *L = NULL,
675 Node *R = NULL):
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() { }
681
682 // Tree manipulations used during insertion and deletion
683 virtual Node *RemoveFixup(Node *x, Node *p);
684
685 // Operations defined on binary trees. All run in O(lgN) time.
686 virtual Node *add( T& AddMe);
687 virtual Node *unlink(Node *z);
688
689 // Returns NULL if the red-black invariant holds.
690 virtual int CheckTreeProperties( Node *);
691};
692
693template<class T>
694class RedBlackNode : public AbstractRedBlackNode<T, RedBlackNode<T> > {
695public:
696
697 // ructors. Node always starts out red.
698 RedBlackNode() { }
699 RedBlackNode( T& X,
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() { }
708};
709
710
711
716template<class T, class Node>
718protected:
719 virtual Node *FindNode(T q)
720 { return (AbstractBinaryTree<T, Node>::root) ? (Node *) this->root->find(q) : NULL; }
721};
722
770template <class T>
771class VDKBtree : public AbstractRedBlackTree<T, RedBlackNode<T> > {
772public:
777};
778
779
780template<class T, class Node>
781Node *
782AbstractRedBlackNode<T, Node>::add( T& AddMe)
783{
784 Node *root = (Node *) this;
785 Node *x = (Node *) this;
786 Node *y = NULL;
787 while (x) {
788 y = x;
789 x = (AddMe < x->object) ? x->left : x->right;
790 }
791 Node *addme = new Node(AddMe, y);
792 if (! y)
793 root = addme;
794 else {
795 if (AddMe < y->object)
796 y->left = addme;
797 else
798 y->right = addme;
799 }
800 addme->clr = Red;
801 while (addme != root &&
802 addme->parent->parent &&
803 addme->parent->clr == Red) {
804 Node *y;
805
806 if (addme->parent == addme->parent->parent->left) {
807 y = addme->parent->parent->right;
808 if (y && y->clr == Red) {
809 // Case 1: x's uncle is red
810 addme->parent->clr = Black;
811 y->clr = Black;
812 addme->parent->parent->clr = Red;
813 addme = addme->parent->parent;
814 }
815 else {
816 if (addme == addme->parent->right) {
817 // Case 2: x is a right child
818 // Rotate to transform to case 3
819 addme = addme->parent;
820 root = addme->LeftRotate(root);
821 }
822 // Case 3: x is a left child
823 addme->parent->clr = Black;
824 if (addme->parent->parent) {
825 addme->parent->parent->clr = Red;
826 root = addme->parent->parent->RightRotate(root);
827 }
828 // The while loop will terminate
829 // on the next iteration.
830 }
831 }
832 else {
833 y = addme->parent->parent->left;
834 if (y && y->clr == Red) {
835 addme->parent->clr = Black;
836 y->clr = Black;
837 addme->parent->parent->clr = Red;
838 addme = addme->parent->parent;
839 }
840 else {
841 if (addme == addme->parent->left) {
842 addme = addme->parent;
843 root = addme->RightRotate(root);
844 }
845 addme->parent->clr = Black;
846 if (addme->parent->parent) {
847 addme->parent->parent->clr = Red;
848 root = addme->parent->parent->LeftRotate(root);
849 }
850 }
851 }
852 }
853 root->clr = Black;
854 return root;
855}
856
857template<class T, class Node>
858Node *
859AbstractRedBlackNode<T, Node>::RemoveFixup(Node *x, Node *p)
860{
861 Node *root = (Node *) this;
862
863 while (x != root && (! x || x->clr == Black)) {
864 Node *w;
865 if (x == p->left) {
866 if (! p)
867 return root;
868 w = p->right;
869 if (! w)
870 return root;
871 if (w->clr == Red) {
872 w->clr = Black;
873 p->clr = Red;
874 root = p->LeftRotate(root);
875 w = p->right;
876 if (! p || ! w)
877 return root;
878 }
879 if ( ((! w->left) || w->left->clr == Black) &&
880 ((! w->right) || w->right->clr == Black)) {
881 w->clr = Red;
882 x = p;
883 p = p->parent;
884 continue;
885 }
886 else if ((! w->right) || w->right->clr == Black) {
887 w->left->clr = Black;
888 w->clr = Red;
889 root = w->RightRotate(root);
890 w = p->right;
891 if (! p || ! w)
892 return root;
893 }
894 w->clr = p->clr;
895 if (p)
896 p->clr = Black;
897 w->right->clr = Black;
898 if (p)
899 root = p->LeftRotate(root);
900 x = root;
901 }
902 else {
903 if (! p)
904 return root;
905 w = p->left;
906 if (! p || ! w)
907 return root;
908 if (w->clr == Red) {
909 w->clr = Black;
910 p->clr = Red;
911 root = p->RightRotate(root);
912 w = p->left;
913 if (! p || ! w)
914 return root;
915 }
916 if ( ((! w->right) || w->right->clr == Black) &&
917 ((! w->left) || w->left->clr == Black)) {
918 w->clr = Red;
919 x = p;
920 p = p->parent;
921 continue;
922 }
923 else if ((! w->left) || w->left->clr == Black) {
924 w->right->clr = Black;
925 w->clr = Red;
926 root = w->LeftRotate(root);
927 w = p->left;
928 if (! p || ! w)
929 return root;
930 }
931 w->clr = p->clr;
932 if (p)
933 p->clr = Black;
934 w->left->clr = Black;
935 if (p)
936 root = p->RightRotate(root);
937 x = root;
938 }
939 }
940 if (x)
941 x->clr = Black;
942 return root;
943}
944
945template<class T, class Node>
946Node *
947AbstractRedBlackNode<T, Node>::unlink(Node *z)
948{
949 Node *root = (Node *) this;
950 Node *x, *y;
951
952 if (! z)
953 return root;
954 y = (! z->left || ! z->right) ? z : (Node *) z->Successor();
955 x = (y->left) ? y->left : y->right;
956
957 if (x)
958 x->parent = y->parent;
959
960 if (y->parent) {
961 if (y == y->parent->left)
962 y->parent->left = x;
963 else
964 y->parent->right = x;
965 }
966 else
967 root = x;
968 if (y != z)
969 z->object = y->object;
970 if (y->clr == Black) {
971 if (root)
972 root = root->RemoveFixup(x, y->parent);
973 }
974 delete y;
975 return root;
976}
977
978template<class T, class Node>
979int
980AbstractRedBlackNode<T, Node>::CheckTreeProperties( Node *_parent)
981{
982 static int BlackHeight;
983
984 if (_parent == NULL)
985 BlackHeight = -1;
986
987 // Check binary tree properties.
988 if (this->parent != _parent)
989 return NULL;
990 if (this->left) {
991 if (this->object < this->left->object)
992 return NULL;
993 }
994 if (this->right) {
995 if (this->right->object < this->object)
996 return NULL;
997 }
998
999 // Now check red-black tree properties.
1000
1001 // If a node is red, then both its children are black
1002 // (NULL nodes are black).
1003 if (clr == Red) {
1004 if ((this->left && this->left->clr != Black) ||
1005 (this->right && this->right->clr != Black))
1006 return NULL;
1007 }
1008
1009 // The black-heights of all leaf nodes are equal.
1010 int bh = NULL;
1011
1012 if ((! this->left) && (! this->right)) {
1013 // Compute black-height of node
1014 for (Node *sc = (Node *) this; sc; sc = sc->parent)
1015 if (sc->clr == Black)
1016 bh += 1;
1017
1018 if (BlackHeight == -1) {
1019 BlackHeight = bh;
1020 }
1021 else {
1022 if (bh != BlackHeight)
1023 return NULL;
1024 }
1025 }
1026 if (this->left && (! this->left->CheckTreeProperties((Node *) this)))
1027 return NULL;
1028 if (this->right && (! this->right->CheckTreeProperties((Node *) this)))
1029 return NULL;
1030 return 1;
1031}
1032#endif
1033
1034
1035
1036
1037
Provides a nlog(n) iterator for AbstractBinaryTree.
Definition: vdkbtrees.h:157
virtual void Next()
Definition: vdkbtrees.h:202
virtual T * Object()
Definition: vdkbtrees.h:262
virtual void operator--()
Definition: vdkbtrees.h:279
virtual ~Iterator()
Definition: vdkbtrees.h:190
virtual void operator++(int)
Definition: vdkbtrees.h:275
virtual void operator++()
Definition: vdkbtrees.h:271
virtual T current()
Definition: vdkbtrees.h:240
void StartAt(enum BtreeIteratorMode start)
Definition: vdkbtrees.h:179
Iterator(AbstractBinaryTree< T, Node > &_tree, enum BtreeIteratorMode start=BtMinKey)
Definition: vdkbtrees.h:168
virtual void operator--(int)
Definition: vdkbtrees.h:283
virtual T * RefObject()
Definition: vdkbtrees.h:251
virtual void Parent()
Definition: vdkbtrees.h:210
virtual void Previous()
Definition: vdkbtrees.h:194
virtual T operator*()
Definition: vdkbtrees.h:235
provides an abstract class for concrete VDKBtree class
Definition: vdkbtrees.h:107
virtual int IsEmpty()
Definition: vdkbtrees.h:137
unsigned int size()
Definition: vdkbtrees.h:154
AbstractBinaryTree(AbstractBinaryTree< T, Node > &)
Definition: vdkbtrees.h:574
virtual void unlink(T &)
Definition: vdkbtrees.h:635
virtual void add(T &)
Definition: vdkbtrees.h:610
virtual int CheckTreeProperties()
Definition: vdkbtrees.h:653
AbstractBinaryTree< T, Node > & operator=(AbstractBinaryTree< T, Node > &)
Definition: vdkbtrees.h:585
virtual T * find(T &q)
Definition: vdkbtrees.h:645
provides an abstract frame class for VDKBTree
Definition: vdkbtrees.h:717
provides a templatized binary tree data structure
Definition: vdkbtrees.h:771
VDKBtree()
Definition: vdkbtrees.h:776