src/livarot/AVL.cpp

   1 /*
   2  *  AVL.cpp
   3  *  nlivarot
   4  *
   5  *  Created by fred on Mon Jun 16 2003.
   6  *
   7  */
   8
   9 #include "AVL.h"
  10
  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  */
  15
  16 AVLTree::AVLTree()
  17 {
  18     MakeNew();
  19 }
  20
  21 AVLTree::~AVLTree()
  22 {
  23     MakeDelete();
  24 }
  25
  26 void AVLTree::MakeNew()
  27 {
  28     for (int i = 0; i < 2; i++)
  29     {
  30         elem[i] = NULL;
  31         son[i] = NULL;
  32     }
  33
  34     dad = NULL;
  35     balance = 0;
  36 }
  37
  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 }
  47
  48 AVLTree *AVLTree::Leftmost()
  49 {
  50     return leafFromDad(NULL, LEFT);
  51 }
  52
  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     }
  68
  69     return NULL;
  70 }
  71
  72 AVLTree *AVLTree::leafFromDad(AVLTree */*from*/, Side s)
  73 {
  74     if (son[s]) {
  75         return son[s]->leafFromDad(this, s);
  76     }
  77
  78     return this;
  79 }
  80
  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;
 121
 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;
 143
 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;
 158
 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;
 175
 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;
 186
 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             {
 227
 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];
 262
 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;
 279
 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 }
 313
 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];
 419
 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];
 578
 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 }
 652
 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 }
 666
 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;
 675
 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;
 704
 705           oDad->son[RIGHT] = newMe->son[LEFT];
 706           if (newMe->son[LEFT])
 707             newMe->son[LEFT]->dad = oDad;
 708
 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 }
 799
 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 }
 812
 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
 879
 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 }
 907
 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];
 917
 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 }
 937
 938
 939 void AVLTree::insertOn(Side s, AVLTree *of)
 940 {
 941   elem[1 - s] = of;
 942   if (of)
 943     of->elem[s] = this;
 944 }
 945
 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 }
 955
 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:fileencoding=utf-8:textwidth=99 :