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:
AbstractBinaryNode()41 AbstractBinaryNode() { }
42 AbstractBinaryNode( T& _object,
43 Node *_parent = NULL,
44 Node *_left = NULL,
45 Node *_right = NULL);
~AbstractBinaryNode()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
BinaryNode()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) { }
~BinaryNode()89 virtual ~BinaryNode() { }
90 };
91
92 //////////////////////////////////////////////////////
93 // Iterator class
94 /*!
95 \class AbstractBinaryTree::Iterator
96 \brief Provides a nlog(n) iterator for AbstractBinaryTree
97
98 Iterator is implementes as a member of AbstractBinaryTree
99 rather than an external object.
100 */
101 enum BtreeIteratorMode { BtMinKey, BtRootKey, BtMaxKey };
102 /*!
103 \class AbstractBinaryTree
104 \brief provides an abstract class for concrete VDKBtree class
105 */
106 template<class T, class Node>
107 class AbstractBinaryTree {
108
109 public:
110
111 AbstractBinaryTree();
112 /*!
113 Copy initializer
114 */
115 AbstractBinaryTree( AbstractBinaryTree<T, Node>&);
116 /*!
117 Assignement operator
118 */
119 AbstractBinaryTree<T, Node>& operator=( AbstractBinaryTree<T, Node>&);
120 virtual ~AbstractBinaryTree();
121
122 /*!
123 Adds a type <T> to tree.
124 */
125 virtual void add( T&); // Add a node
126 /*!
127 Remove a type <T> from the tree
128 */
129 virtual void unlink( T&); // Remove a node
130 /*!
131 Membership operator, return T* NULL on failure.
132 */
133 virtual T *find( T& q);
134 /*!
135 Return 1 if tree is empty
136 */
IsEmpty()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) ;
147 /*!
148 Checks tree integrity (for debugging purposes)
149 */
150 virtual int CheckTreeProperties();
151 /*!
152 Returns tree size in nodes.
153 */
size()154 unsigned int size() { return count; }
155
156
157 class Iterator {
158
159 public:
160 /*!
161 ructor
162 \param tree tree reference
163 \param start where the iterator starts, can be:
164 \arg BtMinKey from lowest key
165 \arg BtRootKey from the tree root
166 \arg BtMaxKey from the highest key
167 */
168 Iterator( AbstractBinaryTree<T, Node>& _tree,
169 enum BtreeIteratorMode start = BtMinKey)
170 {
171 tree = (AbstractBinaryTree<T, Node> *) (&_tree);
172 StartAt(start);
173 }
174
175 /*!
176 Starts iterator over at the minimum, maximum or
177 root node of the binary tree.
178 */
StartAt(enum BtreeIteratorMode start)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 }
187 /*!
188 Destructor
189 */
~Iterator()190 virtual ~Iterator() { }
191 /*!
192 Move iterator to prev key
193 */
Previous()194 virtual void Previous()
195 {
196 if (ptr)
197 ptr = ptr->Predecessor();
198 }
199 /*!
200 Move iterator to next key
201 */
Next()202 virtual void Next()
203 {
204 if (ptr)
205 ptr = ptr->Successor();
206 }
207 /*!
208 Move iterator to parent node
209 */
Parent()210 virtual void Parent()
211 {
212 if (ptr)
213 ptr = ptr->parent;
214 }
215 /*!
216 \internal
217 */
find(T & x)218 virtual void find( T& x)
219 {
220 ptr = tree->IteratorFind(x);
221 }
222 /*!
223 Returns o if iterator points a non valid node.
224 ie: was moved behind the lowest/highest key
225 */
226 virtual operator int()
227 {
228 return ptr != NULL;
229 }
230
231 /*!
232 Dereferencing operator returns the object of the
233 node currently pointed to by the iterator.
234 */
235 virtual T operator*() { return ptr->object; }
236 /*!
237 Dereferencing operator returns the object of the
238 node currently pointed to by the iterator.
239 */
current()240 virtual T current() { return ptr->object; }
241 /*!
242 \internal
243 */
current_node()244 virtual Node* current_node()
245 { return ptr; }
246 /*!
247 returns a pointer to the object of the
248 node currently pointed to (as opposed to returning
249 a copy of the node, as the dereferencing operator does).
250 */
RefObject()251 virtual T *RefObject()
252 {
253 if (ptr)
254 return &ptr->object;
255 return (T*) NULL;
256 }
257 /*!
258 returns a pointer to the object of the
259 node currently pointed to (as opposed to returning
260 a copy of the node, as the dereferencing operator does).
261 */
Object()262 virtual T *Object()
263 {
264 if (ptr)
265 return &ptr->object;
266 return NULL;
267 }
268 /*!
269 Move iterator to next key
270 */
271 virtual void operator++() { Next(); }
272 /*!
273 Move iterator to next key
274 */
275 virtual void operator++(int) { Next(); }
276 /*!
277 Move iterator to prev key
278 */
279 virtual void operator--() { Previous(); }
280 /*!
281 Move iterator to prev key
282 */
283 virtual void operator--(int) { Previous(); }
284
285 protected:
286 Node *ptr;
287 AbstractBinaryTree<T, Node> *tree;
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>
AbstractBinaryNode(T & _object,Node * _parent,Node * _left,Node * _right)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 *
Clone(Node * _parent)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 *
LeftRotate(Node * root)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 *
RightRotate(Node * root)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
IsLeftChild()382 AbstractBinaryNode<T, Node>::IsLeftChild()
383 {
384 return (parent && parent->left == (Node *) this);
385 }
386
387 template<class T, class Node>
388 int
IsRightChild()389 AbstractBinaryNode<T, Node>::IsRightChild()
390 {
391 return (parent && parent->right == (Node *) this);
392 }
393
394 template<class T, class Node>
395 Node *
find(T & x)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 *
findNearest(T & x)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 *
add(T & x)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 *
unlink(Node * z)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 *
Minimum()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 *
Maximum()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 *
Predecessor()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 *
Successor()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
RemoveSubtree()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 *
Object()536 AbstractBinaryNode<T, Node>::Object()
537 {
538 return &object;
539 }
540
541 template<class T, class Node>
542 int
CheckTreeProperties(Node * _parent)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>
AbstractBinaryTree()567 AbstractBinaryTree<T, Node>::AbstractBinaryTree()
568 {
569 root = NULL;
570 count = NULL;
571 }
572
573 template<class T, class Node>
AbstractBinaryTree(AbstractBinaryTree<T,Node> & x)574 AbstractBinaryTree<T, Node>::AbstractBinaryTree( AbstractBinaryTree<T, Node>& x)
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>
584 AbstractBinaryTree<T, Node>&
585 AbstractBinaryTree<T, Node>::operator=( AbstractBinaryTree<T, Node>& x)
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>
~AbstractBinaryTree()600 AbstractBinaryTree<T, Node>::~AbstractBinaryTree()
601 {
602 if (root) {
603 root->RemoveSubtree();
604 delete root;
605 }
606 }
607
608 template<class T, class Node>
609 void
add(T & x)610 AbstractBinaryTree<T, Node>::add( T& x)
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 *
IteratorRoot()621 AbstractBinaryTree<T, Node>::IteratorRoot()
622 {
623 return root;
624 }
625
626 template<class T, class Node>
627 Node *
IteratorFind(T & x)628 AbstractBinaryTree<T, Node>::IteratorFind( T& x)
629 {
630 return (root) ? root->find(x) : NULL;
631 }
632
633 template<class T, class Node>
634 void
unlink(T & _x)635 AbstractBinaryTree<T, Node>::unlink( T& _x)
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 *
find(T & q)645 AbstractBinaryTree<T, Node>::find( T& q)
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
CheckTreeProperties()653 AbstractBinaryTree<T, Node>::CheckTreeProperties()
654 {
655 if (root->CheckTreeProperties(NULL) == NULL)
656 return NULL;
657 return 1;
658 }
659
660 /////////////////////////////
661 // balanced binary trees
662 // (using red & black trees)
663 /////////////////////////////
664 //plm
665 /*typedef */enum RedBlack { Black, Red };
666 template<class T, class Node>
667 class AbstractRedBlackNode : public AbstractBinaryNode<T, Node> {
668 public:
669
670 RedBlack clr;
671 // ructors. Node always starts out red.
AbstractRedBlackNode()672 AbstractRedBlackNode() { clr = Red; }
673 AbstractRedBlackNode( T& X,
674 Node *P = NULL,
675 Node *L = NULL,
676 Node *R = NULL):
677 AbstractBinaryNode<T, Node>(X, P, L, R) { }
678 AbstractRedBlackNode( T& X, RedBlack Clr, Node *P = NULL,
679 Node *L = NULL, Node *R = NULL):
680 AbstractBinaryNode<T, Node>(X, P, L, R), clr(Clr) { }
~AbstractRedBlackNode()681 virtual ~AbstractRedBlackNode() { }
682
683 // Tree manipulations used during insertion and deletion
684 virtual Node *RemoveFixup(Node *x, Node *p);
685
686 // Operations defined on binary trees. All run in O(lgN) time.
687 virtual Node *add( T& AddMe);
688 virtual Node *unlink(Node *z);
689
690 // Returns NULL if the red-black invariant holds.
691 virtual int CheckTreeProperties( Node *);
692 };
693
694 template<class T>
695 class RedBlackNode : public AbstractRedBlackNode<T, RedBlackNode<T> > {
696 public:
697
698 // ructors. Node always starts out red.
RedBlackNode()699 RedBlackNode() { }
700 RedBlackNode( T& X,
701 RedBlackNode<T> *P = NULL,
702 RedBlackNode<T> *L = NULL,
703 RedBlackNode<T> *R = NULL):
704 AbstractRedBlackNode<T, RedBlackNode<T> >(X, P, L, R) { }
705 RedBlackNode( T& X, RedBlack Clr, RedBlackNode<T> *P = NULL,
706 RedBlackNode<T> *L = NULL, RedBlackNode<T> *R = NULL):
707 AbstractRedBlackNode<T, RedBlackNode<T> >(X, Clr, P, L, R) { }
~RedBlackNode()708 virtual ~RedBlackNode() { }
709 };
710
711
712
713 /*!
714 \class AbstractRedBlackTree
715 \brief provides an abstract frame class for VDKBTree
716 */
717 template<class T, class Node>
718 class AbstractRedBlackTree : public AbstractBinaryTree<T, Node> {
719 protected:
FindNode(T q)720 virtual Node *FindNode(T q)
721 { return (this->root) ? (Node *) this->root->find(q) : NULL; }
722 };
723
724 /*!
725 \class VDKBtree
726 \brief provides a templatized binary tree data structure
727
728 \par Description
729 VDKBtree<T> class has a value semantic, all objects are copied
730 from original values.
731 VDKBtree<T> class implements red/black balanced trees.
732 All managed type T objects should provide:
733 \arg a default constructor: T::T()
734 \arg a copy initializer: T::T(T& t)
735 \arg an assignement operator: T& T::operator=(T& t)
736 \arg an equality and less-than operators:
737 \arg bool T::operator==(T& t)
738 \arg bool T::operator<(T& t)
739 \par Implementation notes
740 I suggest to use typedef's like:
741 \code
742 typedef VDKBtree<someClass> SomeClassBtree;
743 \endcode
744 \par Programming tips
745 Here an example how to construct, fill and trasverse a btree
746 \code
747 #define LEN 10
748 typedef VDKBtree<int> intbt;
749 int v[LUNG] = { 3, 5, 7, 2, 1, 4, 45, 6, 23, 6 };
750 int main(int , char **)
751 {
752 intbt btree;
753 // add nodes to tree
754 for (t=0; t < LEN ;t++)
755 btree.add(v[t]);
756 // makes an iterator
757 intbt::Iterator iter(btree);
758 for (; iter;iter++)
759 {
760 int i = iter.current();
761 // make whatever with i
762 }
763 // removes all nodes
764 for (t=0; t < LEN; t++)
765 btree.unlink(v[t]);
766 }
767 \endcode
768 \par EXAMPLES
769 in ./example/template/ttest.cc
770 */
771 template <class T>
772 class VDKBtree : public AbstractRedBlackTree<T, RedBlackNode<T> > {
773 public:
774 /*!
775 Constructor, makes an empty tree
776 */
VDKBtree()777 VDKBtree() { }
778 };
779
780
781 template<class T, class Node>
782 Node *
add(T & AddMe)783 AbstractRedBlackNode<T, Node>::add( T& AddMe)
784 {
785 Node *root = (Node *) this;
786 Node *x = (Node *) this;
787 Node *y = NULL;
788 while (x) {
789 y = x;
790 x = (AddMe < x->object) ? x->left : x->right;
791 }
792 Node *addme = new Node(AddMe, y);
793 if (! y)
794 root = addme;
795 else {
796 if (AddMe < y->object)
797 y->left = addme;
798 else
799 y->right = addme;
800 }
801 addme->clr = Red;
802 while (addme != root &&
803 addme->parent->parent &&
804 addme->parent->clr == Red) {
805 Node *y;
806
807 if (addme->parent == addme->parent->parent->left) {
808 y = addme->parent->parent->right;
809 if (y && y->clr == Red) {
810 // Case 1: x's uncle is red
811 addme->parent->clr = Black;
812 y->clr = Black;
813 addme->parent->parent->clr = Red;
814 addme = addme->parent->parent;
815 }
816 else {
817 if (addme == addme->parent->right) {
818 // Case 2: x is a right child
819 // Rotate to transform to case 3
820 addme = addme->parent;
821 root = addme->LeftRotate(root);
822 }
823 // Case 3: x is a left child
824 addme->parent->clr = Black;
825 if (addme->parent->parent) {
826 addme->parent->parent->clr = Red;
827 root = addme->parent->parent->RightRotate(root);
828 }
829 // The while loop will terminate
830 // on the next iteration.
831 }
832 }
833 else {
834 y = addme->parent->parent->left;
835 if (y && y->clr == Red) {
836 addme->parent->clr = Black;
837 y->clr = Black;
838 addme->parent->parent->clr = Red;
839 addme = addme->parent->parent;
840 }
841 else {
842 if (addme == addme->parent->left) {
843 addme = addme->parent;
844 root = addme->RightRotate(root);
845 }
846 addme->parent->clr = Black;
847 if (addme->parent->parent) {
848 addme->parent->parent->clr = Red;
849 root = addme->parent->parent->LeftRotate(root);
850 }
851 }
852 }
853 }
854 root->clr = Black;
855 return root;
856 }
857
858 template<class T, class Node>
859 Node *
RemoveFixup(Node * x,Node * p)860 AbstractRedBlackNode<T, Node>::RemoveFixup(Node *x, Node *p)
861 {
862 Node *root = (Node *) this;
863
864 while (x != root && (! x || x->clr == Black)) {
865 Node *w;
866 if (x == p->left) {
867 if (! p)
868 return root;
869 w = p->right;
870 if (! w)
871 return root;
872 if (w->clr == Red) {
873 w->clr = Black;
874 p->clr = Red;
875 root = p->LeftRotate(root);
876 w = p->right;
877 if (! p || ! w)
878 return root;
879 }
880 if ( ((! w->left) || w->left->clr == Black) &&
881 ((! w->right) || w->right->clr == Black)) {
882 w->clr = Red;
883 x = p;
884 p = p->parent;
885 continue;
886 }
887 else if ((! w->right) || w->right->clr == Black) {
888 w->left->clr = Black;
889 w->clr = Red;
890 root = w->RightRotate(root);
891 w = p->right;
892 if (! p || ! w)
893 return root;
894 }
895 w->clr = p->clr;
896 if (p)
897 p->clr = Black;
898 w->right->clr = Black;
899 if (p)
900 root = p->LeftRotate(root);
901 x = root;
902 }
903 else {
904 if (! p)
905 return root;
906 w = p->left;
907 if (! p || ! w)
908 return root;
909 if (w->clr == Red) {
910 w->clr = Black;
911 p->clr = Red;
912 root = p->RightRotate(root);
913 w = p->left;
914 if (! p || ! w)
915 return root;
916 }
917 if ( ((! w->right) || w->right->clr == Black) &&
918 ((! w->left) || w->left->clr == Black)) {
919 w->clr = Red;
920 x = p;
921 p = p->parent;
922 continue;
923 }
924 else if ((! w->left) || w->left->clr == Black) {
925 w->right->clr = Black;
926 w->clr = Red;
927 root = w->LeftRotate(root);
928 w = p->left;
929 if (! p || ! w)
930 return root;
931 }
932 w->clr = p->clr;
933 if (p)
934 p->clr = Black;
935 w->left->clr = Black;
936 if (p)
937 root = p->RightRotate(root);
938 x = root;
939 }
940 }
941 if (x)
942 x->clr = Black;
943 return root;
944 }
945
946 template<class T, class Node>
947 Node *
unlink(Node * z)948 AbstractRedBlackNode<T, Node>::unlink(Node *z)
949 {
950 Node *root = (Node *) this;
951 Node *x, *y;
952
953 if (! z)
954 return root;
955 y = (! z->left || ! z->right) ? z : (Node *) z->Successor();
956 x = (y->left) ? y->left : y->right;
957
958 if (x)
959 x->parent = y->parent;
960
961 if (y->parent) {
962 if (y == y->parent->left)
963 y->parent->left = x;
964 else
965 y->parent->right = x;
966 }
967 else
968 root = x;
969 if (y != z)
970 z->object = y->object;
971 if (y->clr == Black) {
972 if (root)
973 root = root->RemoveFixup(x, y->parent);
974 }
975 delete y;
976 return root;
977 }
978
979 template<class T, class Node>
980 int
CheckTreeProperties(Node * _parent)981 AbstractRedBlackNode<T, Node>::CheckTreeProperties( Node *_parent)
982 {
983 static int BlackHeight;
984
985 if (_parent == NULL)
986 BlackHeight = -1;
987
988 // Check binary tree properties.
989 if (this->parent != _parent)
990 return NULL;
991 if (this->left) {
992 if (this->object < this->left->object)
993 return NULL;
994 }
995 if (this->right) {
996 if (this->right->object < this->object)
997 return NULL;
998 }
999
1000 // Now check red-black tree properties.
1001
1002 // If a node is red, then both its children are black
1003 // (NULL nodes are black).
1004 if (clr == Red) {
1005 if ((this->left && this->left->clr != Black) ||
1006 (this->right && this->right->clr != Black))
1007 return NULL;
1008 }
1009
1010 // The black-heights of all leaf nodes are equal.
1011 int bh = NULL;
1012
1013 if ((! this->left) && (! this->right)) {
1014 // Compute black-height of node
1015 for (Node *sc = (Node *) this; sc; sc = sc->parent)
1016 if (sc->clr == Black)
1017 bh += 1;
1018
1019 if (BlackHeight == -1) {
1020 BlackHeight = bh;
1021 }
1022 else {
1023 if (bh != BlackHeight)
1024 return NULL;
1025 }
1026 }
1027 if (this->left && (! this->left->CheckTreeProperties((Node *) this)))
1028 return NULL;
1029 if (this->right && (! this->right->CheckTreeProperties((Node *) this)))
1030 return NULL;
1031 return 1;
1032 }
1033 #endif
1034
1035
1036
1037
1038
1039