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 
38 template<class T, class Node>
39 class AbstractBinaryNode {
40 public:
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 
73 public:
74  T object;
75  Node *left, *right, *parent;
76 
77 };
78 
79 template<class T>
80 class BinaryNode : public AbstractBinaryNode<T, BinaryNode<T> > {
81 public:
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
101 enum BtreeIteratorMode { BtMinKey, BtRootKey, BtMaxKey };
106 template<class T, class Node>
108 
109 public:
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 
290 protected:
291  Node *root;
292  unsigned int count;
293 };
294 
295 /*
296  class BinaryTree
297  place holder for others type of binary trees
298 template<class T>
299 class BinaryTree : public AbstractBinaryTree<T, BinaryNode<T> > {
300 public:
301  BinaryTree() { }
302 };
303 */
304 
305 
306 // --------------------------------------------------------
307 // AbstractBinaryNode implementation.
308 // --------------------------------------------------------
309 template<class T, class Node>
310 AbstractBinaryNode<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 
321 template<class T, class Node>
322 Node *
323 AbstractBinaryNode<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 
334 template<class T, class Node>
335 Node *
336 AbstractBinaryNode<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 
357 template<class T, class Node>
358 Node *
359 AbstractBinaryNode<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 
380 template<class T, class Node>
381 int
382 AbstractBinaryNode<T, Node>::IsLeftChild()
383 {
384  return (parent && parent->left == (Node *) this);
385 }
386 
387 template<class T, class Node>
388 int
389 AbstractBinaryNode<T, Node>::IsRightChild()
390 {
391  return (parent && parent->right == (Node *) this);
392 }
393 
394 template<class T, class Node>
395 Node *
396 AbstractBinaryNode<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 
410 template<class T, class Node>
411 Node *
412 AbstractBinaryNode<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 
426 template<class T, class Node>
427 Node *
428 AbstractBinaryNode<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 
438 template<class T, class Node>
439 Node *
440 AbstractBinaryNode<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 
470 template<class T, class Node>
471 Node *
472 AbstractBinaryNode<T, Node>::Minimum()
473 {
474  Node *sc = (Node *) this;
475  while (sc && sc->left)
476  sc = sc->left;
477  return sc;
478 }
479 
480 template<class T, class Node>
481 Node *
482 AbstractBinaryNode<T, Node>::Maximum()
483 {
484  Node *sc = (Node *) this;
485  while (sc && sc->right)
486  sc = sc->right;
487  return sc;
488 }
489 
490 template<class T, class Node>
491 Node *
492 AbstractBinaryNode<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 
505 template<class T, class Node>
506 Node *
507 AbstractBinaryNode<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 
520 template<class T, class Node>
521 void
522 AbstractBinaryNode<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 
534 template<class T, class Node>
535 T *
536 AbstractBinaryNode<T, Node>::Object()
537 {
538  return &object;
539 }
540 
541 template<class T, class Node>
542 int
543 AbstractBinaryNode<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 
566 template<class T, class Node>
568 {
569  root = NULL;
570  count = NULL;
571 }
572 
573 template<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 
583 template<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 
599 template<class T, class Node>
601 {
602  if (root) {
603  root->RemoveSubtree();
604  delete root;
605  }
606 }
607 
608 template<class T, class Node>
609 void
611 {
612  count++;
613  if (root == NULL)
614  root = new Node(x);
615  else
616  root = root->add(x);
617 }
618 
619 template<class T, class Node>
620 Node *
622 {
623  return root;
624 }
625 
626 template<class T, class Node>
627 Node *
629 {
630  return (root) ? root->find(x) : NULL;
631 }
632 
633 template<class T, class Node>
634 void
636 {
637  count--;
638  if (! root)
639  return;
640  root = root->unlink(root->find(_x));
641 }
642 
643 template<class T, class Node>
644 T *
646 {
647  Node *p = (root) ? root->find(q) : NULL;
648  return (p) ? &p->object : NULL;
649 }
650 
651 template<class T, class Node>
652 int
654 {
655  if (root->CheckTreeProperties(NULL) == NULL)
656  return NULL;
657  return 1;
658 }
659 
661 // balanced binary trees
662 // (using red & black trees)
664 typedef enum RedBlack { Black, Red };
665 template<class T, class Node>
666 class AbstractRedBlackNode : public AbstractBinaryNode<T, Node> {
667 public:
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 
693 template<class T>
694 class RedBlackNode : public AbstractRedBlackNode<T, RedBlackNode<T> > {
695 public:
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 
716 template<class T, class Node>
717 class AbstractRedBlackTree : public AbstractBinaryTree<T, Node> {
718 protected:
719  virtual Node *FindNode(T q)
720  { return (AbstractBinaryTree<T, Node>::root) ? (Node *) this->root->find(q) : NULL; }
721 };
722 
770 template <class T>
771 class VDKBtree : public AbstractRedBlackTree<T, RedBlackNode<T> > {
772 public:
776  VDKBtree() { }
777 };
778 
779 
780 template<class T, class Node>
781 Node *
782 AbstractRedBlackNode<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 
857 template<class T, class Node>
858 Node *
859 AbstractRedBlackNode<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 
945 template<class T, class Node>
946 Node *
947 AbstractRedBlackNode<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 
978 template<class T, class Node>
979 int
980 AbstractRedBlackNode<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