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