Rudiments
avltreeinlines.h
1 // Copyright (c) 2016 David Muse
2 // See the COPYING file for more information
3 
4 //#define DEBUG_AVLTREE 1
5 
6 #include <rudiments/stdio.h>
7 #include <rudiments/private/nodeinlines.h>
8 
9 #define AVLTREE_TEMPLATE template <class valuetype>
10 
11 #define AVLTREE_CLASS avltree<valuetype>
12 
13 #define AVLTREENODE_TEMPLATE template <class valuetype>
14 
15 #define AVLTREENODE_CLASS avltreenode<valuetype>
16 
17 AVLTREE_TEMPLATE
18 inline
19 AVLTREE_CLASS::avltree() {
20  top=NULL;
21  first=NULL;
22  last=NULL;
23  length=0;
24 }
25 
26 AVLTREE_TEMPLATE
27 inline
28 AVLTREE_CLASS::~avltree() {
29  clear();
30 }
31 
32 AVLTREE_TEMPLATE
33 inline
34 void AVLTREE_CLASS::insert(valuetype value) {
35  insert(new avltreenode<valuetype>(value));
36 }
37 
38 AVLTREE_TEMPLATE
39 inline
40 void AVLTREE_CLASS::insert(avltreenode<valuetype> *node) {
41 
42  // degenerate case
43  if (!node) {
44  return;
45  }
46 
47  #ifdef DEBUG_AVLTREE
48  stdoutput.printf("----------------------------------------"
49  "---------------------------------------\n");
50  #endif
51 
52  if (top) {
53 
54  // insert the node, optionally replacing the top of the tree
55  top->insert(node,&top);
56 
57  // update first
58  for (first=top;
59  first->getLeftChild();
60  first=first->getLeftChild()) {}
61 
62  // update last
63  for (last=top;
64  last->getRightChild();
65  last=last->getRightChild()) {}
66  } else {
67 
68  // if there was no top node, then this is the
69  // first node inserted into the entire tree
70  top=node;
71  first=node;
72  last=node;
73  }
74 
75  // increment length
76  length++;
77 }
78 
79 AVLTREE_TEMPLATE
80 inline
81 avltreenode<valuetype> *AVLTREE_CLASS::detach(avltreenode<valuetype> *node) {
82 
83  // degenerate case
84  if (!node) {
85  return NULL;
86  }
87 
88  #ifdef DEBUG_AVLTREE
89  stdoutput.printf("----------------------------------------"
90  "---------------------------------------\n");
91  #endif
92 
93  // update first
94  if (first==node) {
95  first=node->getNext();
96  }
97 
98  // update last
99  if (last==node) {
100  last=node->getPrevious();
101  }
102 
103  // detach the node
104  node->detach(&top);
105 
106  // decrement length
107  length--;
108 
109  return node;
110 }
111 
112 AVLTREE_TEMPLATE
113 inline
114 bool AVLTREE_CLASS::remove(valuetype value) {
115  avltreenode<valuetype> *current=find(value);
116  return (current)?remove(current):false;
117 }
118 
119 AVLTREE_TEMPLATE
120 inline
121 bool AVLTREE_CLASS::removeAll(valuetype value) {
122  bool removed=false;
123  while (remove(value)) {
124  removed=true;
125  }
126  return removed;
127 }
128 
129 AVLTREE_TEMPLATE
130 inline
131 bool AVLTREE_CLASS::remove(avltreenode<valuetype> *node) {
132  delete detach(node);
133  return true;
134 }
135 
136 AVLTREE_TEMPLATE
137 inline
138 uint64_t AVLTREE_CLASS::getLength() const {
139  return length;
140 }
141 
142 AVLTREE_TEMPLATE
143 inline
144 avltreenode<valuetype> *AVLTREE_CLASS::getTop() {
145  return top;
146 }
147 
148 AVLTREE_TEMPLATE
149 inline
150 avltreenode<valuetype> *AVLTREE_CLASS::getFirst() {
151  return first;
152 }
153 
154 AVLTREE_TEMPLATE
155 inline
156 avltreenode<valuetype> *AVLTREE_CLASS::getLast() {
157  return last;
158 }
159 
160 AVLTREE_TEMPLATE
161 inline
162 avltreenode<valuetype> *AVLTREE_CLASS::getPrevious(
163  avltreenode<valuetype> *node) {
164  return (node)?node->getPrevious():NULL;
165 }
166 
167 AVLTREE_TEMPLATE
168 inline
169 avltreenode<valuetype> *AVLTREE_CLASS::getNext(
170  avltreenode<valuetype> *node) {
171  return (node)?node->getNext():NULL;
172 }
173 
174 AVLTREE_TEMPLATE
175 inline
176 avltreenode<valuetype> *AVLTREE_CLASS::find(valuetype value) {
177  return find((avltreenode<valuetype> *)top,value);
178 }
179 
180 AVLTREE_TEMPLATE
181 inline
182 avltreenode<valuetype> *AVLTREE_CLASS::find(
183  avltreenode<valuetype> *startnode,
184  valuetype value) {
185 
186  #ifdef DEBUG_AVLTREE
187  stdoutput.printf("find ");
188  node_print(value);
189  stdoutput.printf(" from ");
190  if (startnode) {
191  node_print(startnode->getValue());
192  } else {
193  node_print("(null)");
194  }
195  stdoutput.printf(" {\n");
196  #endif
197 
198  // descend the tree until we find the value or run off of the bottom
199  avltreenode<valuetype> *current=startnode;
200  while (current) {
201 
202  int32_t result=current->compare(value);
203 
204  #ifdef DEBUG_AVLTREE
205  stdoutput.printf(" ");
206  node_print(current->getValue());
207  stdoutput.printf(" - %d\n",result);
208  #endif
209 
210  if (result<0) {
211  current=current->getRightChild();
212  } else if (result==0) {
213  break;
214  } else if (result>0) {
215  current=current->getLeftChild();
216  }
217  }
218 
219  #ifdef DEBUG_AVLTREE
220  if (current) {
221  stdoutput.printf(" success!\n");
222  } else {
223  stdoutput.printf(" failed\n");
224  }
225  stdoutput.printf("} find\n\n");
226  #endif
227 
228  return current;
229 }
230 
231 // NOTE: Don't collapse the clear methods into a single method, or the compiler
232 // will attempt to compile calls to:
233 // delete current->getValue();
234 // and
235 // delete[] current->getValue();
236 // even if the app just calls clear(). This will fail for primitive types or
237 // when the type has a private destructor.
238 
239 AVLTREE_TEMPLATE
240 inline
241 void AVLTREE_CLASS::clear() {
242 
243  #ifdef DEBUG_AVLTREE
244  uint64_t i=0;
245  stdoutput.printf("clearing %d nodes {\n",length);
246  #endif
247 
248  // start at the top
249  AVLTREENODE_CLASS *node=top;
250  while (node) {
251 
252  // go right one, then go left as far as possible
253  if (node->getRightChild()) {
254  node=node->getRightChild();
255  }
256  while (node->getLeftChild()) {
257  node=node->getLeftChild();
258  }
259 
260  // get the parent
261  AVLTREENODE_CLASS *p=node->getParent();
262  if (p) {
263  if (p->getLeftChild()==node) {
264  p->setLeftChild(NULL);
265  } else {
266  p->setRightChild(NULL);
267  }
268  }
269 
270  // delete the node
271  #ifdef DEBUG_AVLTREE
272  stdoutput.printf(" clearing %lld\n",i);
273  // It's dangerous to try to print the value of the node here.
274  // If the value is a pointer to something, it may have been
275  // deleted already. In fact, it's really common to run through
276  // the tree, deleting values, before finally calling clear()
277  // on the tree itself.
278  i++;
279  #endif
280  delete node;
281 
282  // continue with parent...
283  node=p;
284  }
285 
286  #ifdef DEBUG_AVLTREE
287  stdoutput.printf("} cleared %d nodes\n\n",i);
288  #endif
289 
290  // clear pointers and length
291  top=NULL;
292  first=NULL;
293  last=NULL;
294  length=0;
295 }
296 
297 AVLTREE_TEMPLATE
298 inline
299 void AVLTREE_CLASS::clearAndDelete() {
300 
301  #ifdef DEBUG_AVLTREE
302  uint64_t i=0;
303  stdoutput.printf("clearing %d nodes {\n",length);
304  #endif
305 
306  // start at the top
307  AVLTREENODE_CLASS *node=top;
308  while (node) {
309 
310  // go right one, then go left as far as possible
311  if (node->getRightChild()) {
312  node=node->getRightChild();
313  }
314  while (node->getLeftChild()) {
315  node=node->getLeftChild();
316  }
317 
318  // get the parent
319  AVLTREENODE_CLASS *p=node->getParent();
320  if (p) {
321  if (p->getLeftChild()==node) {
322  p->setLeftChild(NULL);
323  } else {
324  p->setRightChild(NULL);
325  }
326  }
327 
328  // delete the node
329  #ifdef DEBUG_AVLTREE
330  stdoutput.printf(" clearing %lld\n",i);
331  i++;
332  #endif
333  delete node->getValue();
334  delete node;
335 
336  // continue with parent...
337  node=p;
338  }
339 
340  #ifdef DEBUG_AVLTREE
341  stdoutput.printf("} cleared %d nodes\n\n",i);
342  #endif
343 
344  // clear pointers and length
345  top=NULL;
346  first=NULL;
347  last=NULL;
348  length=0;
349 }
350 
351 AVLTREE_TEMPLATE
352 inline
353 void AVLTREE_CLASS::clearAndArrayDelete() {
354 
355  #ifdef DEBUG_AVLTREE
356  uint64_t i=0;
357  stdoutput.printf("clearing %d nodes {\n",length);
358  #endif
359 
360  // start at the top
361  AVLTREENODE_CLASS *node=top;
362  while (node) {
363 
364  // go right one, then go left as far as possible
365  if (node->getRightChild()) {
366  node=node->getRightChild();
367  }
368  while (node->getLeftChild()) {
369  node=node->getLeftChild();
370  }
371 
372  // get the parent
373  AVLTREENODE_CLASS *p=node->getParent();
374  if (p) {
375  if (p->getLeftChild()==node) {
376  p->setLeftChild(NULL);
377  } else {
378  p->setRightChild(NULL);
379  }
380  }
381 
382  // delete the node
383  #ifdef DEBUG_AVLTREE
384  stdoutput.printf(" clearing %lld\n",i);
385  i++;
386  #endif
387  delete[] node->getValue();
388  delete node;
389 
390  // continue with parent...
391  node=p;
392  }
393 
394  #ifdef DEBUG_AVLTREE
395  stdoutput.printf("} cleared %d nodes\n\n",i);
396  #endif
397 
398  // clear pointers and length
399  top=NULL;
400  first=NULL;
401  last=NULL;
402  length=0;
403 }
404 
405 AVLTREE_TEMPLATE
406 inline
407 void AVLTREE_CLASS::print() const {
408  if (top) {
409  top->print();
410  }
411 }
412 
413 AVLTREENODE_TEMPLATE
414 inline
415 AVLTREENODE_CLASS::avltreenode(valuetype value) {
416  this->value=value;
417  parent=NULL;
418  left=NULL;
419  right=NULL;
420  leftheight=0;
421  rightheight=0;
422 }
423 
424 AVLTREENODE_TEMPLATE
425 inline
426 AVLTREENODE_CLASS::~avltreenode() {
427 }
428 
429 AVLTREENODE_TEMPLATE
430 inline
431 void AVLTREENODE_CLASS::setValue(valuetype value) {
432  this->value=value;
433 }
434 
435 AVLTREENODE_TEMPLATE
436 inline
437 valuetype AVLTREENODE_CLASS::getValue() const {
438  return value;
439 }
440 
441 AVLTREENODE_TEMPLATE
442 inline
443 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getParent() {
444  return parent;
445 }
446 
447 AVLTREENODE_TEMPLATE
448 inline
449 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getLeftChild() {
450  return left;
451 }
452 
453 AVLTREENODE_TEMPLATE
454 inline
455 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getRightChild() {
456  return right;
457 }
458 
459 AVLTREENODE_TEMPLATE
460 inline
461 uint8_t AVLTREENODE_CLASS::getLeftHeight() {
462  return leftheight;
463 }
464 
465 AVLTREENODE_TEMPLATE
466 inline
467 uint8_t AVLTREENODE_CLASS::getRightHeight() {
468  return rightheight;
469 }
470 
471 AVLTREENODE_TEMPLATE
472 inline
473 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getPrevious() {
474 
475  // reverse in-order, depth-first traversal...
476 
477  if (left) {
478 
479  // if we have a left child then its rightmost descendent
480  // contains the next lowest value...
481 
482  // go left
483  AVLTREENODE_CLASS *node=left;
484 
485  // go as far right as possible
486  while (node->right) {
487  node=node->right;
488  }
489  return node;
490 
491  } else if (parent) {
492 
493  // if we're the right child of our parent,
494  // then our parent contains the next lowest value
495  if (parent->right==this) {
496  return parent;
497  }
498 
499  // If we're the left child of our parent, then we have to
500  // move up until we find an acestor that's the right child of
501  // its parent. That node contains the next lowest value.
502  AVLTREENODE_CLASS *node=parent;
503  while (node) {
504  if (!node->parent) {
505  break;
506  }
507  if (node->parent->right==node) {
508  return node->parent;
509  }
510  node=node->parent;
511  }
512  }
513  return NULL;
514 }
515 
516 AVLTREENODE_TEMPLATE
517 inline
518 AVLTREENODE_CLASS *AVLTREENODE_CLASS::getNext() {
519 
520  // in-order, depth-first traversal...
521 
522  if (right) {
523 
524  // if we have a right child then its leftmost descendent
525  // contains the next highest value...
526 
527  // go right
528  AVLTREENODE_CLASS *node=right;
529 
530  // go as far left as possible
531  while (node->left) {
532  node=node->left;
533  }
534  return node;
535 
536  } else if (parent) {
537 
538  // if we're the left child of our parent,
539  // then our parent contains the next highest value
540  if (parent->left==this) {
541  return parent;
542  }
543 
544  // If we're the right child of our parent, then we have to
545  // move up until we find an acestor that's the left child of
546  // its parent. That node contains the next highest value.
547  AVLTREENODE_CLASS *node=parent;
548  while (node) {
549  if (!node->parent) {
550  break;
551  }
552  if (node->parent->left==node) {
553  return node->parent;
554  }
555  node=node->parent;
556  }
557  }
558  return NULL;
559 }
560 
561 AVLTREENODE_TEMPLATE
562 inline
563 int32_t AVLTREENODE_CLASS::compare(valuetype value) const {
564  return node_compare(this->value,value);
565 }
566 
567 AVLTREENODE_TEMPLATE
568 inline
569 int32_t AVLTREENODE_CLASS::compare(avltreenode<valuetype> *peer) const {
570  return node_compare(this->value,peer->value);
571 }
572 
573 AVLTREENODE_TEMPLATE
574 inline
575 void AVLTREENODE_CLASS::print() const {
576  uint16_t indentlevel=0;
577  print("top",&indentlevel);
578 }
579 
580 AVLTREENODE_TEMPLATE
581 inline
582 void AVLTREENODE_CLASS::print(const char *name, uint16_t *indentlevel) const {
583  // print an xml-style representation of the node and its descendents
584  for (uint16_t i=0; i<*indentlevel; i++) {
585  stdoutput.printf(" ");
586  }
587  stdoutput.printf("<%s value=\"",name);
588  node_print(value);
589  stdoutput.printf("\" lh=\"%d\" rh=\"%d\" bf=\"%d\"",
590  leftheight,rightheight,leftheight-rightheight);
591  if (!left && !right) {
592  stdoutput.printf("/>\n");
593  } else {
594  stdoutput.printf(">\n");
595  (*indentlevel)++;
596  if (left) {
597  left->print("left ",indentlevel);
598  }
599  if (right) {
600  right->print("right",indentlevel);
601  }
602  (*indentlevel)--;
603  for (uint16_t i=0; i<*indentlevel; i++) {
604  stdoutput.printf(" ");
605  }
606  stdoutput.printf("</%s>\n",name);
607  }
608 }
609 
610 AVLTREENODE_TEMPLATE
611 inline
612 void AVLTREENODE_CLASS::setParent(AVLTREENODE_CLASS *node) {
613  parent=node;
614 }
615 
616 AVLTREENODE_TEMPLATE
617 inline
618 void AVLTREENODE_CLASS::setLeftChild(AVLTREENODE_CLASS *node) {
619  left=node;
620 }
621 
622 AVLTREENODE_TEMPLATE
623 inline
624 void AVLTREENODE_CLASS::setRightChild(AVLTREENODE_CLASS *node) {
625  right=node;
626 }
627 
628 AVLTREE_TEMPLATE
629 inline
630 void AVLTREENODE_CLASS::insert(avltreenode<valuetype> *node,
631  avltreenode<valuetype> **treetop) {
632 
633  // degenerate case
634  if (!node) {
635  return;
636  }
637 
638  // find a location to insert the node (should always be a leaf node)
639  avltreenode<valuetype> *location=this;
640  for (;;) {
641 
642  if (node->compare(location->value)<=0) {
643 
644  if (location->left) {
645  location=location->left;
646  } else {
647 
648  #ifdef DEBUG_AVLTREE
649  stdoutput.printf("insert ");
650  node_print(node->value);
651  stdoutput.printf(" to left of ");
652  node_print(location->value);
653  stdoutput.printf(" {\n\n");
654  #endif
655 
656  location->setLeftChild(node);
657  break;
658  }
659 
660  } else if (node->compare(location->value)>0) {
661 
662  if (location->right) {
663  location=location->right;
664  } else {
665 
666  #ifdef DEBUG_AVLTREE
667  stdoutput.printf("insert ");
668  node_print(node->value);
669  stdoutput.printf(" to right of ");
670  node_print(location->value);
671  stdoutput.printf(" {\n\n");
672  #endif
673 
674  location->setRightChild(node);
675  break;
676  }
677  }
678  }
679 
680  node->setParent(location);
681 
682  // update heights up the tree
683  adjustParentHeights(node);
684 
685  // balance the tree
686  node->parent->balance(treetop);
687 
688  #ifdef DEBUG_AVLTREE
689  stdoutput.printf("} insert\n\n");
690  #endif
691 }
692 
693 AVLTREE_TEMPLATE
694 inline
695 void AVLTREENODE_CLASS::detach(avltreenode<valuetype> **treetop) {
696 
697  #ifdef DEBUG_AVLTREE
698  stdoutput.printf("detach ");
699  node_print(value);
700  stdoutput.printf(" {\n\n");
701 
702  avltreenode<valuetype> *top=this;
703  while (top->parent) { top=top->parent; }
704  top->print(); stdoutput.printf("\n");
705  #endif
706 
707  if (left && right) {
708 
709  // node with left and right children...
710 
711  #ifdef DEBUG_AVLTREE
712  stdoutput.printf("less simple case: 2 children\n\n");
713  #endif
714 
715  // get this node's successor...
716  //
717  // (eg. if the tree contains values 5, 7, 10, 12, 15, and 18,
718  // and this node is 10, then find the node with 12 in it)
719  //
720  // following the rules from our in-order, depth-first traversal
721  // above, since we have a right child, we must go right one,
722  // then go left as far as possible
723  avltreenode<valuetype> *successor=right;
724  while (successor->left) {
725  successor=successor->left;
726  }
727 
728  #ifdef DEBUG_AVLTREE
729  stdoutput.printf("swap ");
730  node_print(value);
731  stdoutput.printf(" and ");
732  node_print(successor->value);
733  stdoutput.printf("\n\n");
734  #endif
735 
736 
737  // if the successor was the immediate right child of this node
738  // then we need to handle a few things differently later
739  bool successorwasimmediaterightchild=(right==successor);
740 
741 
742  // swap this node with the successor...
743 
744  // get a copy of the successor
745  avltreenode<valuetype> temp(*successor);
746 
747  // re-parent the successor
748  successor->parent=parent;
749  if (successor->parent) {
750  if (successor->parent->left==this) {
751  successor->parent->left=successor;
752  } else {
753  successor->parent->right=successor;
754  }
755  } else {
756  *treetop=successor;
757  }
758 
759  // replace the successor's children
760  // with those of this node
761  successor->left=left;
762  if (successor->left) {
763  successor->left->parent=successor;
764  }
765  if (successorwasimmediaterightchild) {
766  successor->right=this;
767  successor->right->parent=successor;
768  } else {
769  successor->right=right;
770  if (successor->right) {
771  successor->right->parent=successor;
772  }
773 
774  // re-parent this node
775  parent=temp.parent;
776  if (parent->left==successor) {
777  parent->left=this;
778  } else {
779  parent->right=this;
780  }
781  }
782 
783  // replace the successor's heights
784  // with those of this node
785  successor->leftheight=leftheight;
786  successor->rightheight=rightheight;
787 
788 
789  // replace this node's children
790  // with those of the successor
791  left=temp.left;
792  if (left) {
793  left->parent=this;
794  }
795  right=temp.right;
796  if (right) {
797  right->parent=this;
798  }
799 
800  // replace this node's heights
801  // with those of the successor
802  leftheight=temp.leftheight;
803  rightheight=temp.rightheight;
804 
805  #ifdef DEBUG_AVLTREE
806  avltreenode<valuetype> *top=this;
807  while (top->parent) { top=top->parent; }
808  top->print(); stdoutput.printf("\n");
809  #endif
810 
811  // fall through to the code below because now
812  // the node should have one or zero children...
813  }
814 
815  // node with one or zero children...
816 
817  #ifdef DEBUG_AVLTREE
818  stdoutput.printf("simple case: 1 or 0 children\n\n");
819  #endif
820 
821  // decide which child the node has
822  // NOTE: If the node has no children then this will implicitly
823  // set child=NULL (which is what we want in that case) because
824  // right=NULL.
825  avltreenode<valuetype> *child=(left)?left:right;
826 
827  if (parent) {
828 
829  // disconnect this node from its children
830  left=NULL;
831  right=NULL;
832 
833  // connect the parent to the child
834  // (or to NULL if the node has no children)
835  // decrement the appropriate height of parent
836  if (parent->left==this) {
837  parent->left=child;
838  parent->leftheight--;
839  } else {
840  parent->right=child;
841  parent->rightheight--;
842  }
843 
844  // connect the child to the parent
845  if (child) {
846  child->parent=parent;
847  }
848 
849  // disconnect this node from its parent
850  // (but keep track of the parent so we
851  // can use it to balance)
852  avltreenode<valuetype> *p=parent;
853  parent=NULL;
854 
855  // update heights up the tree
856  adjustParentHeights(p);
857 
858  // balance the tree
859  p->balance(treetop);
860 
861  } else {
862 
863  // disconnect this node's child from it
864  if (child) {
865  child->parent=NULL;
866  }
867 
868  // disconnect this node from its children
869  left=NULL;
870  right=NULL;
871 
872  // NOTE: If the node has no children, then this will
873  // implicitly (re)set treetop=NULL, which is what
874  // we want in that case.
875  *treetop=child;
876 
877  #ifdef DEBUG_AVLTREE
878  avltreenode<valuetype> *top=this;
879  while (top->parent) { top=top->parent; }
880  top->print(); stdoutput.printf("\n");
881  #endif
882  }
883 
884  #ifdef DEBUG_AVLTREE
885  stdoutput.printf("} detach\n\n");
886  #endif
887 }
888 
889 AVLTREE_TEMPLATE
890 inline
891 void AVLTREENODE_CLASS::adjustParentHeights(avltreenode<valuetype> *node) {
892 
893  // move up the tree, starting with the parent of "node"...
894  while (node->parent) {
895 
896  // calculate the new height of the parent
897  uint8_t height=((node->leftheight>node->rightheight)?
898  node->leftheight:
899  node->rightheight)+1;
900 
901  // If "node" is the left child of the parent, then adjust the
902  // parent's left height.
903  // If "node" is the right child of the parent, then adjust the
904  // parent's right height.
905  // In either case, bail if the height is already the same as we
906  // calculated.
907  if (node->parent->left==node) {
908  if (node->parent->leftheight==height) {
909  return;
910  }
911  node->parent->leftheight=height;
912  } else {
913  if (node->parent->rightheight==height) {
914  return;
915  }
916  node->parent->rightheight=height;
917  }
918 
919  // move up
920  node=node->parent;
921  }
922 }
923 
924 AVLTREE_TEMPLATE
925 inline
926 void AVLTREENODE_CLASS::balance(avltreenode<valuetype> **treetop) {
927 
928  // AVL balance...
929 
930  #ifdef DEBUG_AVLTREE
931  stdoutput.printf("balance at ");
932  node_print(value);
933  stdoutput.printf(" {\n\n");
934 
935  avltreenode<valuetype> *top=this;
936  while (top->parent) { top=top->parent; }
937  top->print(); stdoutput.printf("\n");
938  #endif
939 
940  // start balancing with the current node
941  avltreenode<valuetype> *node=this;
942  while (node) {
943 
944  // there's an imbalance if the left and right
945  // tree heights differ by more than 1
946  if ((node->leftheight>node->rightheight &&
947  node->leftheight-node->rightheight>1) ||
948  (node->rightheight>node->leftheight &&
949  node->rightheight-node->leftheight>1)) {
950 
951  #ifdef DEBUG_AVLTREE
952  stdoutput.printf("imbalance at ");
953  node_print(node->value);
954  stdoutput.printf("\n\n");
955  #endif
956 
957  // apply the appropriate rotation to restore balance
958  // and let the rotation method tell us whch node to
959  // process next
960  if (node->rightheight>node->leftheight) {
961  if (node->right->rightheight>
962  node->right->leftheight) {
963  node=node->leftRotate(treetop);
964  } else {
965  node=node->rightLeftRotate(treetop);
966  }
967  } else if (node->leftheight>node->rightheight) {
968  if (node->left->leftheight>
969  node->left->rightheight) {
970  node=node->rightRotate(treetop);
971  } else {
972  node=node->leftRightRotate(treetop);
973  }
974  }
975 
976  #ifdef DEBUG_AVLTREE
977  avltreenode<valuetype> *top=this;
978  while (top->parent) { top=top->parent; }
979  top->print(); stdoutput.printf("\n");
980  #endif
981 
982  } else {
983 
984  #ifdef DEBUG_AVLTREE
985  stdoutput.printf("no imbalance at ");
986  node_print(node->value);
987  stdoutput.printf("\n\n");
988  #endif
989 
990  // if there's no imbalance then the next node we need
991  // to process is the parent of the current node
992  node=node->parent;
993  }
994 
995  #ifdef DEBUG_AVLTREE
996  if (node) {
997  stdoutput.printf("continuing at ");
998  node_print(node->value);
999  stdoutput.printf("\n\n");
1000  }
1001  #endif
1002  }
1003 
1004 
1005  #ifdef DEBUG_AVLTREE
1006  stdoutput.printf("} balance\n\n");
1007  #endif
1008 }
1009 
1010 AVLTREE_TEMPLATE
1011 inline
1012 avltreenode<valuetype> *AVLTREENODE_CLASS::leftRotate(
1013  avltreenode<valuetype> **treetop) {
1014 
1015  /* one of these: (eg: insert order a,b,c)
1016  *
1017  * \
1018  * a
1019  * / \ \
1020  * b -> b
1021  * / \ / \
1022  * * c a c
1023  * / \ / \ / \
1024  * *
1025  * needs left rotation */
1026 
1027  #ifdef DEBUG_AVLTREE
1028  stdoutput.printf("left rotation at ");
1029  node_print(value);
1030  stdoutput.printf("\n\n");
1031  #endif
1032 
1033  // get a, b, and "star"
1034  avltreenode<valuetype> *a=this;
1035  avltreenode<valuetype> *b=a->right;
1036  avltreenode<valuetype> *star=b->left;
1037  uint8_t starheight=b->leftheight;
1038 
1039  // move b
1040  avltreenode<valuetype> *p=a->parent;
1041  if (p) {
1042  if (p->right==a) {
1043  p->right=b;
1044  } else {
1045  p->left=b;
1046  }
1047  } else {
1048  #ifdef DEBUG_AVLTREE
1049  stdoutput.printf("(new tree top)\n\n");
1050  #endif
1051  *treetop=b;
1052  }
1053  b->parent=a->parent;
1054  b->left=a;
1055 
1056  // move a
1057  a->parent=b;
1058  a->right=star;
1059  a->rightheight=starheight;
1060 
1061  // move "star"
1062  if (star) {
1063  star->parent=a;
1064  }
1065 
1066  // update heights up the tree
1067  adjustParentHeights(a);
1068 
1069  // Since a was moved into a location in the tree that may not have
1070  // prevoiusly existed, and thus may have unbalanced the tree, we need
1071  // to continue balancing, starting at a.
1072  return a;
1073 }
1074 
1075 AVLTREE_TEMPLATE
1076 inline
1077 avltreenode<valuetype> *AVLTREENODE_CLASS::rightLeftRotate(
1078  avltreenode<valuetype> **treetop) {
1079 
1080  /* one of these: (eg: insert order a,c,b)
1081  *
1082  * \ \
1083  * a a
1084  * / \ / \ \
1085  * c -> b -> b
1086  * / \ / \ / \
1087  * b c a c
1088  * / \ / \ / \ / \
1089  * * *
1090  *
1091  * needs right-left rotation */
1092 
1093  #ifdef DEBUG_AVLTREE
1094  stdoutput.printf("right-left rotation at ");
1095  node_print(value);
1096  stdoutput.printf(" {\n\n");
1097  stdoutput.printf("right part\n\n");
1098  #endif
1099 
1100  // do the right part of the right-left rotation...
1101 
1102  // get a, c, b, and "star"
1103  avltreenode<valuetype> *a=this;
1104  avltreenode<valuetype> *c=a->right;
1105  avltreenode<valuetype> *b=c->left;
1106  avltreenode<valuetype> *star=b->right;
1107  uint8_t starheight=b->rightheight;
1108 
1109  // move b
1110  a->right=b;
1111  b->parent=a;
1112  b->right=c;
1113 
1114  // move c
1115  c->parent=b;
1116  c->left=star;
1117  c->leftheight=starheight;
1118 
1119  // move "star"
1120  if (star) {
1121  star->parent=c;
1122  }
1123 
1124  // update heights up the tree
1125  adjustParentHeights(c);
1126 
1127  #ifdef DEBUG_AVLTREE
1128  avltreenode<valuetype> *top=this;
1129  while (top->parent) { top=top->parent; }
1130  top->print(); stdoutput.printf("\n");
1131  #endif
1132 
1133  // do the left part of the right-left rotation
1134  leftRotate(treetop);
1135 
1136  #ifdef DEBUG_AVLTREE
1137  stdoutput.printf("} right-left\n\n");
1138  #endif
1139 
1140  // Since c was moved into a location in the tree that may not have
1141  // prevoiusly existed, and thus may have unbalanced the tree, we need
1142  // to continue balancing, starting at c.
1143  return c;
1144 }
1145 
1146 AVLTREE_TEMPLATE
1147 inline
1148 avltreenode<valuetype> *AVLTREENODE_CLASS::rightRotate(
1149  avltreenode<valuetype> **treetop) {
1150 
1151  /* one of these: (insert order c,b,a)
1152  *
1153  * \
1154  * c
1155  * / \ \
1156  * b -> b
1157  * / \ / \
1158  * a * a c
1159  * / \ / \ / \
1160  * *
1161  * needs right rotation */
1162 
1163  #ifdef DEBUG_AVLTREE
1164  stdoutput.printf("right rotation at ");
1165  node_print(value);
1166  stdoutput.printf("\n\n");
1167  #endif
1168 
1169  // get c, b, and "star"
1170  avltreenode<valuetype> *c=this;
1171  avltreenode<valuetype> *b=c->left;
1172  avltreenode<valuetype> *star=b->right;
1173  uint8_t starheight=b->rightheight;
1174 
1175  // move b
1176  avltreenode<valuetype> *p=c->parent;
1177  if (p) {
1178  if (p->right==c) {
1179  p->right=b;
1180  } else {
1181  p->left=b;
1182  }
1183  } else {
1184  #ifdef DEBUG_AVLTREE
1185  stdoutput.printf("(new tree top)\n\n");
1186  #endif
1187  *treetop=b;
1188  }
1189  b->parent=c->parent;
1190  b->right=c;
1191 
1192  // move c
1193  c->parent=b;
1194  c->left=star;
1195  c->leftheight=starheight;
1196 
1197  // move "star"
1198  if (star) {
1199  star->parent=c;
1200  }
1201 
1202  // update heights up the tree
1203  adjustParentHeights(c);
1204 
1205  // Since c was moved into a location in the tree that may not have
1206  // prevoiusly existed, and thus may have unbalanced the tree, we need
1207  // to continue balancing, starting at c.
1208  return c;
1209 }
1210 
1211 AVLTREE_TEMPLATE
1212 inline
1213 avltreenode<valuetype> *AVLTREENODE_CLASS::leftRightRotate(
1214  avltreenode<valuetype> **treetop) {
1215 
1216  /* one of these: (insert order c,a,b)
1217  *
1218  * \ \
1219  * c c
1220  * / \ / \ \
1221  * a -> b -> b
1222  * / \ / \ / \
1223  * b a a c
1224  * / \ / \ / \
1225  * * *
1226  *
1227  * needs left-right rotation */
1228 
1229  #ifdef DEBUG_AVLTREE
1230  stdoutput.printf("left-right rotation at ");
1231  node_print(value);
1232  stdoutput.printf(" {\n\n");
1233  stdoutput.printf("left part\n\n");
1234  #endif
1235 
1236  // do the left part of the left-right rotation...
1237 
1238  // get c, a, b, and "star"
1239  avltreenode<valuetype> *c=this;
1240  avltreenode<valuetype> *a=c->left;
1241  avltreenode<valuetype> *b=a->right;
1242  avltreenode<valuetype> *star=b->left;
1243  uint8_t starheight=b->leftheight;
1244 
1245  // move b
1246  c->left=b;
1247  b->parent=c;
1248  b->left=a;
1249 
1250  // move a
1251  a->parent=b;
1252  a->right=star;
1253  a->rightheight=starheight;
1254 
1255  // move "star"
1256  if (star) {
1257  star->parent=a;
1258  }
1259 
1260  // update heights up the tree
1261  adjustParentHeights(a);
1262 
1263  #ifdef DEBUG_AVLTREE
1264  avltreenode<valuetype> *top=this;
1265  while (top->parent) { top=top->parent; }
1266  top->print(); stdoutput.printf("\n");
1267  #endif
1268 
1269  // do the right part of the left-right rotation
1270  rightRotate(treetop);
1271 
1272  #ifdef DEBUG_AVLTREE
1273  stdoutput.printf("} left-right\n\n");
1274  #endif
1275 
1276  // Since a was moved into a location in the tree that may not have
1277  // prevoiusly existed, and thus may have unbalanced the tree, we need
1278  // to continue balancing, starting at a.
1279  return a;
1280 }
int32_t compare(valuetype value) const
avltreenode< valuetype > * getNext()
avltreenode< valuetype > * getLeftChild()
size_t printf(const char *format,...)
void print() const
avltreenode< valuetype > * getPrevious()
avltreenode< valuetype > * getRightChild()
valuetype getValue() const
Definition: avltree.h:11