1 /*
2 * AVL.cpp
3 * nlivarot
4 *
5 * Created by fred on Mon Jun 16 2003.
6 *
7 */
9 #include "AVL.h"
11 /*
12 * the algorithm explanation for this code comes from purists.org, which seems to have disappeared since
13 * it's a classic AVL tree rebalancing, nothing fancy
14 */
16 AVLTree::AVLTree()
17 {
18 MakeNew();
19 }
21 AVLTree::~AVLTree()
22 {
23 MakeDelete();
24 }
26 void AVLTree::MakeNew()
27 {
28 for (int i = 0; i < 2; i++)
29 {
30 elem[i] = NULL;
31 son[i] = NULL;
32 }
34 dad = NULL;
35 balance = 0;
36 }
38 void AVLTree::MakeDelete()
39 {
40 for (int i = 0; i < 2; i++) {
41 if (elem[i]) {
42 elem[i]->elem[1 - i] = elem[1 - i];
43 }
44 elem[i] = NULL;
45 }
46 }
48 AVLTree *AVLTree::Leftmost()
49 {
50 return leafFromDad(NULL, LEFT);
51 }
53 AVLTree *AVLTree::leaf(AVLTree *from, Side s)
54 {
55 if (from == son[1 - s]) {
56 if (son[s]) {
57 return son[s]->leafFromDad(this, s);
58 }
59 else if (dad) {
60 return dad->leaf(this, s);
61 }
62 }
63 else if (from == son[s]) {
64 if (dad) {
65 return dad->leaf(this, s);
66 }
67 }
69 return NULL;
70 }
72 AVLTree *AVLTree::leafFromDad(AVLTree *from, Side s)
73 {
74 if (son[s]) {
75 return son[s]->leafFromDad(this, s);
76 }
78 return this;
79 }
81 int
82 AVLTree::RestoreBalances (AVLTree * from, AVLTree * &racine)
83 {
84 if (from == NULL)
85 {
86 if (dad)
87 return dad->RestoreBalances (this, racine);
88 }
89 else
90 {
91 if (balance == 0)
92 {
93 if (from == son[LEFT])
94 balance = 1;
95 if (from == son[RIGHT])
96 balance = -1;
97 if (dad)
98 return dad->RestoreBalances (this, racine);
99 return avl_no_err;
100 }
101 else if (balance > 0)
102 {
103 if (from == son[RIGHT])
104 {
105 balance = 0;
106 return avl_no_err;
107 }
108 if (son[LEFT] == NULL)
109 {
110 // cout << "mierda\n";
111 return avl_bal_err;
112 }
113 AVLTree *a = this;
114 AVLTree *b = son[LEFT];
115 AVLTree *e = son[RIGHT];
116 AVLTree *c = son[LEFT]->son[LEFT];
117 AVLTree *d = son[LEFT]->son[RIGHT];
118 if (son[LEFT]->balance > 0)
119 {
120 AVLTree *r = dad;
122 a->dad = b;
123 b->son[RIGHT] = a;
124 a->son[RIGHT] = e;
125 if (e)
126 e->dad = a;
127 a->son[LEFT] = d;
128 if (d)
129 d->dad = a;
130 b->son[LEFT] = c;
131 if (c)
132 c->dad = b;
133 b->dad = r;
134 if (r)
135 {
136 if (r->son[LEFT] == a)
137 r->son[LEFT] = b;
138 if (r->son[RIGHT] == a)
139 r->son[RIGHT] = b;
140 }
141 if (racine == a)
142 racine = b;
144 a->balance = 0;
145 b->balance = 0;
146 return avl_no_err;
147 }
148 else
149 {
150 if (son[LEFT]->son[RIGHT] == NULL)
151 {
152 // cout << "mierda\n";
153 return avl_bal_err;
154 }
155 AVLTree *f = son[LEFT]->son[RIGHT]->son[LEFT];
156 AVLTree *g = son[LEFT]->son[RIGHT]->son[RIGHT];
157 AVLTree *r = dad;
159 a->dad = d;
160 d->son[RIGHT] = a;
161 b->dad = d;
162 d->son[LEFT] = b;
163 a->son[LEFT] = g;
164 if (g)
165 g->dad = a;
166 a->son[RIGHT] = e;
167 if (e)
168 e->dad = a;
169 b->son[LEFT] = c;
170 if (c)
171 c->dad = b;
172 b->son[RIGHT] = f;
173 if (f)
174 f->dad = b;
176 d->dad = r;
177 if (r)
178 {
179 if (r->son[LEFT] == a)
180 r->son[LEFT] = d;
181 if (r->son[RIGHT] == a)
182 r->son[RIGHT] = d;
183 }
184 if (racine == a)
185 racine = d;
187 int old_bal = d->balance;
188 d->balance = 0;
189 if (old_bal == 0)
190 {
191 a->balance = 0;
192 b->balance = 0;
193 }
194 else if (old_bal > 0)
195 {
196 a->balance = -1;
197 b->balance = 0;
198 }
199 else if (old_bal < 0)
200 {
201 a->balance = 0;
202 b->balance = 1;
203 }
204 return avl_no_err;
205 }
206 }
207 else if (balance < 0)
208 {
209 if (from == son[LEFT])
210 {
211 balance = 0;
212 return avl_no_err;
213 }
214 if (son[RIGHT] == NULL)
215 {
216 // cout << "mierda\n";
217 return avl_bal_err;
218 }
219 AVLTree *a = this;
220 AVLTree *b = son[RIGHT];
221 AVLTree *e = son[LEFT];
222 AVLTree *c = son[RIGHT]->son[RIGHT];
223 AVLTree *d = son[RIGHT]->son[LEFT];
224 AVLTree *r = dad;
225 if (son[RIGHT]->balance < 0)
226 {
228 a->dad = b;
229 b->son[LEFT] = a;
230 a->son[LEFT] = e;
231 if (e)
232 e->dad = a;
233 a->son[RIGHT] = d;
234 if (d)
235 d->dad = a;
236 b->son[RIGHT] = c;
237 if (c)
238 c->dad = b;
239 b->dad = r;
240 if (r)
241 {
242 if (r->son[LEFT] == a)
243 r->son[LEFT] = b;
244 if (r->son[RIGHT] == a)
245 r->son[RIGHT] = b;
246 }
247 if (racine == a)
248 racine = b;
249 a->balance = 0;
250 b->balance = 0;
251 return avl_no_err;
252 }
253 else
254 {
255 if (son[RIGHT]->son[LEFT] == NULL)
256 {
257 // cout << "mierda\n";
258 return avl_bal_err;
259 }
260 AVLTree *f = son[RIGHT]->son[LEFT]->son[RIGHT];
261 AVLTree *g = son[RIGHT]->son[LEFT]->son[LEFT];
263 a->dad = d;
264 d->son[LEFT] = a;
265 b->dad = d;
266 d->son[RIGHT] = b;
267 a->son[RIGHT] = g;
268 if (g)
269 g->dad = a;
270 a->son[LEFT] = e;
271 if (e)
272 e->dad = a;
273 b->son[RIGHT] = c;
274 if (c)
275 c->dad = b;
276 b->son[LEFT] = f;
277 if (f)
278 f->dad = b;
280 d->dad = r;
281 if (r)
282 {
283 if (r->son[LEFT] == a)
284 r->son[LEFT] = d;
285 if (r->son[RIGHT] == a)
286 r->son[RIGHT] = d;
287 }
288 if (racine == a)
289 racine = d;
290 int old_bal = d->balance;
291 d->balance = 0;
292 if (old_bal == 0)
293 {
294 a->balance = 0;
295 b->balance = 0;
296 }
297 else if (old_bal > 0)
298 {
299 a->balance = 0;
300 b->balance = -1;
301 }
302 else if (old_bal < 0)
303 {
304 a->balance = 1;
305 b->balance = 0;
306 }
307 return avl_no_err;
308 }
309 }
310 }
311 return avl_no_err;
312 }
314 int
315 AVLTree::RestoreBalances (int diff, AVLTree * &racine)
316 {
317 if (balance > 0)
318 {
319 if (diff < 0)
320 {
321 balance = 0;
322 if (dad)
323 {
324 if (this == dad->son[RIGHT])
325 return dad->RestoreBalances (1, racine);
326 if (this == dad->son[LEFT])
327 return dad->RestoreBalances (-1, racine);
328 }
329 return avl_no_err;
330 }
331 else if (diff == 0)
332 {
333 }
334 else if (diff > 0)
335 {
336 if (son[LEFT] == NULL)
337 {
338 // cout << "un probleme\n";
339 return avl_bal_err;
340 }
341 AVLTree *r = dad;
342 AVLTree *a = this;
343 AVLTree *b = son[RIGHT];
344 AVLTree *e = son[LEFT];
345 AVLTree *f = e->son[RIGHT];
346 AVLTree *g = e->son[LEFT];
347 if (e->balance > 0)
348 {
349 e->son[RIGHT] = a;
350 e->son[LEFT] = g;
351 a->son[RIGHT] = b;
352 a->son[LEFT] = f;
353 if (a)
354 a->dad = e;
355 if (g)
356 g->dad = e;
357 if (b)
358 b->dad = a;
359 if (f)
360 f->dad = a;
361 e->dad = r;
362 if (r)
363 {
364 if (r->son[LEFT] == a)
365 r->son[LEFT] = e;
366 if (r->son[RIGHT] == a)
367 r->son[RIGHT] = e;
368 }
369 if (racine == this)
370 racine = e;
371 e->balance = 0;
372 a->balance = 0;
373 if (r)
374 {
375 if (e == r->son[RIGHT])
376 return r->RestoreBalances (1, racine);
377 if (e == r->son[LEFT])
378 return r->RestoreBalances (-1, racine);
379 }
380 return avl_no_err;
381 }
382 else if (e->balance == 0)
383 {
384 e->son[RIGHT] = a;
385 e->son[LEFT] = g;
386 a->son[RIGHT] = b;
387 a->son[LEFT] = f;
388 if (a)
389 a->dad = e;
390 if (g)
391 g->dad = e;
392 if (b)
393 b->dad = a;
394 if (f)
395 f->dad = a;
396 e->dad = r;
397 if (r)
398 {
399 if (r->son[LEFT] == a)
400 r->son[LEFT] = e;
401 if (r->son[RIGHT] == a)
402 r->son[RIGHT] = e;
403 }
404 if (racine == this)
405 racine = e;
406 e->balance = -1;
407 a->balance = 1;
408 return avl_no_err;
409 }
410 else if (e->balance < 0)
411 {
412 if (son[LEFT]->son[RIGHT] == NULL)
413 {
414 // cout << "un probleme\n";
415 return avl_bal_err;
416 }
417 AVLTree *i = son[LEFT]->son[RIGHT]->son[RIGHT];
418 AVLTree *j = son[LEFT]->son[RIGHT]->son[LEFT];
420 f->son[RIGHT] = a;
421 f->son[LEFT] = e;
422 a->son[RIGHT] = b;
423 a->son[LEFT] = i;
424 e->son[RIGHT] = j;
425 e->son[LEFT] = g;
426 if (b)
427 b->dad = a;
428 if (i)
429 i->dad = a;
430 if (g)
431 g->dad = e;
432 if (j)
433 j->dad = e;
434 if (a)
435 a->dad = f;
436 if (e)
437 e->dad = f;
438 f->dad = r;
439 if (r)
440 {
441 if (r->son[LEFT] == a)
442 r->son[LEFT] = f;
443 if (r->son[RIGHT] == a)
444 r->son[RIGHT] = f;
445 }
446 if (racine == this)
447 racine = f;
448 int oBal = f->balance;
449 f->balance = 0;
450 if (oBal > 0)
451 {
452 a->balance = -1;
453 e->balance = 0;
454 }
455 else if (oBal == 0)
456 {
457 a->balance = 0;
458 e->balance = 0;
459 }
460 else if (oBal < 0)
461 {
462 a->balance = 0;
463 e->balance = 1;
464 }
465 if (r)
466 {
467 if (f == r->son[RIGHT])
468 return r->RestoreBalances (1, racine);
469 if (f == r->son[LEFT])
470 return r->RestoreBalances (-1, racine);
471 }
472 return avl_no_err;
473 }
474 }
475 }
476 else if (balance == 0)
477 {
478 if (diff < 0)
479 {
480 balance = -1;
481 }
482 else if (diff == 0)
483 {
484 }
485 else if (diff > 0)
486 {
487 balance = 1;
488 }
489 return avl_no_err;
490 }
491 else if (balance < 0)
492 {
493 if (diff < 0)
494 {
495 if (son[RIGHT] == NULL)
496 {
497 // cout << "un probleme\n";
498 return avl_bal_err;
499 }
500 AVLTree *r = dad;
501 AVLTree *a = this;
502 AVLTree *b = son[LEFT];
503 AVLTree *e = son[RIGHT];
504 AVLTree *f = e->son[LEFT];
505 AVLTree *g = e->son[RIGHT];
506 if (e->balance < 0)
507 {
508 e->son[LEFT] = a;
509 e->son[RIGHT] = g;
510 a->son[LEFT] = b;
511 a->son[RIGHT] = f;
512 if (a)
513 a->dad = e;
514 if (g)
515 g->dad = e;
516 if (b)
517 b->dad = a;
518 if (f)
519 f->dad = a;
520 e->dad = r;
521 if (r)
522 {
523 if (r->son[LEFT] == a)
524 r->son[LEFT] = e;
525 if (r->son[RIGHT] == a)
526 r->son[RIGHT] = e;
527 }
528 if (racine == this)
529 racine = e;
530 e->balance = 0;
531 a->balance = 0;
532 if (r)
533 {
534 if (e == r->son[RIGHT])
535 return r->RestoreBalances (1, racine);
536 if (e == r->son[LEFT])
537 return r->RestoreBalances (-1, racine);
538 }
539 return avl_no_err;
540 }
541 else if (e->balance == 0)
542 {
543 e->son[LEFT] = a;
544 e->son[RIGHT] = g;
545 a->son[LEFT] = b;
546 a->son[RIGHT] = f;
547 if (a)
548 a->dad = e;
549 if (g)
550 g->dad = e;
551 if (b)
552 b->dad = a;
553 if (f)
554 f->dad = a;
555 e->dad = r;
556 if (r)
557 {
558 if (r->son[LEFT] == a)
559 r->son[LEFT] = e;
560 if (r->son[RIGHT] == a)
561 r->son[RIGHT] = e;
562 }
563 if (racine == this)
564 racine = e;
565 e->balance = 1;
566 a->balance = -1;
567 return avl_no_err;
568 }
569 else if (e->balance > 0)
570 {
571 if (son[RIGHT]->son[LEFT] == NULL)
572 {
573 // cout << "un probleme\n";
574 return avl_bal_err;
575 }
576 AVLTree *i = son[RIGHT]->son[LEFT]->son[LEFT];
577 AVLTree *j = son[RIGHT]->son[LEFT]->son[RIGHT];
579 f->son[LEFT] = a;
580 f->son[RIGHT] = e;
581 a->son[LEFT] = b;
582 a->son[RIGHT] = i;
583 e->son[LEFT] = j;
584 e->son[RIGHT] = g;
585 if (b)
586 b->dad = a;
587 if (i)
588 i->dad = a;
589 if (g)
590 g->dad = e;
591 if (j)
592 j->dad = e;
593 if (a)
594 a->dad = f;
595 if (e)
596 e->dad = f;
597 f->dad = r;
598 if (r)
599 {
600 if (r->son[LEFT] == a)
601 r->son[LEFT] = f;
602 if (r->son[RIGHT] == a)
603 r->son[RIGHT] = f;
604 }
605 if (racine == this)
606 racine = f;
607 int oBal = f->balance;
608 f->balance = 0;
609 if (oBal > 0)
610 {
611 a->balance = 0;
612 e->balance = -1;
613 }
614 else if (oBal == 0)
615 {
616 a->balance = 0;
617 e->balance = 0;
618 }
619 else if (oBal < 0)
620 {
621 a->balance = 1;
622 e->balance = 0;
623 }
624 if (r)
625 {
626 if (f == r->son[RIGHT])
627 return r->RestoreBalances (1, racine);
628 if (f == r->son[LEFT])
629 return r->RestoreBalances (-1, racine);
630 }
631 return avl_no_err;
632 }
633 }
634 else if (diff == 0)
635 {
636 }
637 else if (diff > 0)
638 {
639 balance = 0;
640 if (dad)
641 {
642 if (this == dad->son[RIGHT])
643 return dad->RestoreBalances (1, racine);
644 if (this == dad->son[LEFT])
645 return dad->RestoreBalances (-1, racine);
646 }
647 return avl_no_err;
648 }
649 }
650 return avl_no_err;
651 }
653 /*
654 * removal
655 */
656 int
657 AVLTree::Remove (AVLTree * &racine, bool rebalance)
658 {
659 AVLTree *startNode = NULL;
660 int remDiff = 0;
661 int res = Remove (racine, startNode, remDiff);
662 if (res == avl_no_err && rebalance && startNode)
663 res = startNode->RestoreBalances (remDiff, racine);
664 return res;
665 }
667 int
668 AVLTree::Remove (AVLTree * &racine, AVLTree * &startNode, int &diff)
669 {
670 if (elem[LEFT])
671 elem[LEFT]->elem[RIGHT] = elem[RIGHT];
672 if (elem[RIGHT])
673 elem[RIGHT]->elem[LEFT] = elem[LEFT];
674 elem[LEFT] = elem[RIGHT] = NULL;
676 if (son[LEFT] && son[RIGHT])
677 {
678 AVLTree *newMe = son[LEFT]->leafFromDad(this, RIGHT);
679 if (newMe == NULL || newMe->son[RIGHT])
680 {
681 // cout << "pas normal\n";
682 return avl_rm_err;
683 }
684 if (newMe == son[LEFT])
685 {
686 startNode = newMe;
687 diff = -1;
688 newMe->son[RIGHT] = son[RIGHT];
689 son[RIGHT]->dad = newMe;
690 newMe->dad = dad;
691 if (dad)
692 {
693 if (dad->son[LEFT] == this)
694 dad->son[LEFT] = newMe;
695 if (dad->son[RIGHT] == this)
696 dad->son[RIGHT] = newMe;
697 }
698 }
699 else
700 {
701 AVLTree *oDad = newMe->dad;
702 startNode = oDad;
703 diff = 1;
705 oDad->son[RIGHT] = newMe->son[LEFT];
706 if (newMe->son[LEFT])
707 newMe->son[LEFT]->dad = oDad;
709 newMe->dad = dad;
710 newMe->son[LEFT] = son[LEFT];
711 newMe->son[RIGHT] = son[RIGHT];
712 if (dad)
713 {
714 if (dad->son[LEFT] == this)
715 dad->son[LEFT] = newMe;
716 if (dad->son[RIGHT] == this)
717 dad->son[RIGHT] = newMe;
718 }
719 if (son[LEFT])
720 son[LEFT]->dad = newMe;
721 if (son[RIGHT])
722 son[RIGHT]->dad = newMe;
723 }
724 newMe->balance = balance;
725 if (racine == this)
726 racine = newMe;
727 }
728 else if (son[LEFT])
729 {
730 startNode = dad;
731 diff = 0;
732 if (dad)
733 {
734 if (this == dad->son[LEFT])
735 diff = -1;
736 if (this == dad->son[RIGHT])
737 diff = 1;
738 }
739 if (dad)
740 {
741 if (dad->son[LEFT] == this)
742 dad->son[LEFT] = son[LEFT];
743 if (dad->son[RIGHT] == this)
744 dad->son[RIGHT] = son[LEFT];
745 }
746 if (son[LEFT]->dad == this)
747 son[LEFT]->dad = dad;
748 if (racine == this)
749 racine = son[LEFT];
750 }
751 else if (son[RIGHT])
752 {
753 startNode = dad;
754 diff = 0;
755 if (dad)
756 {
757 if (this == dad->son[LEFT])
758 diff = -1;
759 if (this == dad->son[RIGHT])
760 diff = 1;
761 }
762 if (dad)
763 {
764 if (dad->son[LEFT] == this)
765 dad->son[LEFT] = son[RIGHT];
766 if (dad->son[RIGHT] == this)
767 dad->son[RIGHT] = son[RIGHT];
768 }
769 if (son[RIGHT]->dad == this)
770 son[RIGHT]->dad = dad;
771 if (racine == this)
772 racine = son[RIGHT];
773 }
774 else
775 {
776 startNode = dad;
777 diff = 0;
778 if (dad)
779 {
780 if (this == dad->son[LEFT])
781 diff = -1;
782 if (this == dad->son[RIGHT])
783 diff = 1;
784 }
785 if (dad)
786 {
787 if (dad->son[LEFT] == this)
788 dad->son[LEFT] = NULL;
789 if (dad->son[RIGHT] == this)
790 dad->son[RIGHT] = NULL;
791 }
792 if (racine == this)
793 racine = NULL;
794 }
795 dad = son[RIGHT] = son[LEFT] = NULL;
796 balance = 0;
797 return avl_no_err;
798 }
800 /*
801 * insertion
802 */
803 int
804 AVLTree::Insert (AVLTree * &racine, int insertType, AVLTree * insertL,
805 AVLTree * insertR, bool rebalance)
806 {
807 int res = Insert (racine, insertType, insertL, insertR);
808 if (res == avl_no_err && rebalance)
809 res = RestoreBalances ((AVLTree *) NULL, racine);
810 return res;
811 }
813 int
814 AVLTree::Insert (AVLTree * &racine, int insertType, AVLTree * insertL,
815 AVLTree * insertR)
816 {
817 if (racine == NULL)
818 {
819 racine = this;
820 return avl_no_err;
821 }
822 else
823 {
824 if (insertType == not_found)
825 {
826 // cout << "pb avec l'arbre de raster\n";
827 return avl_ins_err;
828 }
829 else if (insertType == found_on_left)
830 {
831 if (insertR == NULL || insertR->son[LEFT])
832 {
833 // cout << "ngou?\n";
834 return avl_ins_err;
835 }
836 insertR->son[LEFT] = this;
837 dad = insertR;
838 insertOn(LEFT, insertR);
839 }
840 else if (insertType == found_on_right)
841 {
842 if (insertL == NULL || insertL->son[RIGHT])
843 {
844 // cout << "ngou?\n";
845 return avl_ins_err;
846 }
847 insertL->son[RIGHT] = this;
848 dad = insertL;
849 insertOn(RIGHT, insertL);
850 }
851 else if (insertType == found_between)
852 {
853 if (insertR == NULL || insertL == NULL
854 || (insertR->son[LEFT] != NULL && insertL->son[RIGHT] != NULL))
855 {
856 // cout << "ngou?\n";
857 return avl_ins_err;
858 }
859 if (insertR->son[LEFT] == NULL)
860 {
861 insertR->son[LEFT] = this;
862 dad = insertR;
863 }
864 else if (insertL->son[RIGHT] == NULL)
865 {
866 insertL->son[RIGHT] = this;
867 dad = insertL;
868 }
869 insertBetween (insertL, insertR);
870 }
871 else if (insertType == found_exact)
872 {
873 if (insertL == NULL)
874 {
875 // cout << "ngou?\n";
876 return avl_ins_err;
877 }
878 // et on insere
880 if (insertL->son[RIGHT])
881 {
882 insertL = insertL->son[RIGHT]->leafFromDad(insertL, LEFT);
883 if (insertL->son[LEFT])
884 {
885 // cout << "ngou?\n";
886 return avl_ins_err;
887 }
888 insertL->son[LEFT] = this;
889 this->dad = insertL;
890 insertBetween (insertL->elem[LEFT], insertL);
891 }
892 else
893 {
894 insertL->son[RIGHT] = this;
895 dad = insertL;
896 insertBetween (insertL, insertL->elem[RIGHT]);
897 }
898 }
899 else
900 {
901 // cout << "code incorrect\n";
902 return avl_ins_err;
903 }
904 }
905 return avl_no_err;
906 }
908 void
909 AVLTree::Relocate (AVLTree * to)
910 {
911 if (elem[LEFT])
912 elem[LEFT]->elem[RIGHT] = to;
913 if (elem[RIGHT])
914 elem[RIGHT]->elem[LEFT] = to;
915 to->elem[LEFT] = elem[LEFT];
916 to->elem[RIGHT] = elem[RIGHT];
918 if (dad)
919 {
920 if (dad->son[LEFT] == this)
921 dad->son[LEFT] = to;
922 if (dad->son[RIGHT] == this)
923 dad->son[RIGHT] = to;
924 }
925 if (son[RIGHT])
926 {
927 son[RIGHT]->dad = to;
928 }
929 if (son[LEFT])
930 {
931 son[LEFT]->dad = to;
932 }
933 to->dad = dad;
934 to->son[RIGHT] = son[RIGHT];
935 to->son[LEFT] = son[LEFT];
936 }
939 void AVLTree::insertOn(Side s, AVLTree *of)
940 {
941 elem[1 - s] = of;
942 if (of)
943 of->elem[s] = this;
944 }
946 void AVLTree::insertBetween(AVLTree *l, AVLTree *r)
947 {
948 if (l)
949 l->elem[RIGHT] = this;
950 if (r)
951 r->elem[LEFT] = this;
952 elem[LEFT] = l;
953 elem[RIGHT] = r;
954 }
956 /*
957 Local Variables:
958 mode:c++
959 c-file-style:"stroustrup"
960 c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
961 indent-tabs-mode:nil
962 fill-column:99
963 End:
964 */
965 // vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:encoding=utf-8:textwidth=99 :