home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / ledar34.zip / leda-r-3_4_tar / LEDA-3.4 / src / dict / _avl_tree.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  4KB  |  171 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _avl_tree.c
  6. +
  7. +  This file is part of the LEDA research version (LEDA-R) that can be 
  8. +  used free of charge in academic research and teaching. Any commercial
  9. +  use of this software requires a license which is distributed by the
  10. +  LEDA Software GmbH, Postfach 151101, 66041 Saarbruecken, FRG
  11. +  (fax +49 681 31104).
  12. +
  13. +  Copyright (c) 1991-1996  by  Max-Planck-Institut fuer Informatik
  14. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  15. +  All rights reserved.
  16. + 
  17. *******************************************************************************/
  18. #include <LEDA/impl/avl_tree.h>
  19.  
  20.  
  21. //----------------------------------------------------------------------------
  22. //  avl_tree:
  23. //
  24. //  rebalancing routines for AVL trees
  25. //
  26. //  S. N"aher (1993)
  27. //----------------------------------------------------------------------------
  28.  
  29.  
  30. void avl_tree::insert_rebal(avl_tree_item v)
  31. {
  32.   // preconditions:  v is new node created by insertion
  33.   //                 v != root
  34.   //                 height(v) == 1, bal(v) == 0;
  35.  
  36.   // bal(v) == height(R) - height(L)           
  37.  
  38.   //                    u
  39.   //                    |
  40.   //                    v
  41.   //                   / \ 
  42.   //                  L   R
  43.   //
  44.  
  45.   
  46.   while ( v != root() )
  47.   {
  48.     avl_tree_item u = v->parent;
  49.  
  50.     int dir = (v == u->child[left]) ? left : right;
  51.  
  52.     int b = u->get_bal();
  53.  
  54.     if (dir==left)   // insertion in left subtree of u 
  55.        b--;
  56.     else             // insertion in right subtree of u
  57.        b++; 
  58.  
  59.     u->set_bal(b);
  60.  
  61.     if (b==0)  break;   // height of u has not changed 
  62.  
  63.     if (b != 1 && b != -1)
  64.     { 
  65.       // u is out of balance (-2 or + 2)
  66.  
  67.       int d = (b < 0) ? -1 : +1;
  68.   
  69.       avl_tree_item w = u->child[dir];
  70.   
  71.       if (w->get_bal() == d)
  72.       { rotation(u,w,dir);
  73.         u->set_bal(0);
  74.         w->set_bal(0);
  75.        }
  76.       else
  77.       { avl_tree_item x = w->child[1-dir];
  78.         double_rotation(u,w,x,dir);
  79.  
  80.         if (x->get_bal() == d)
  81.            u->set_bal(-d);
  82.         else
  83.            u->set_bal(0);
  84.   
  85.         if (x->get_bal() == -d)
  86.            w->set_bal(d);
  87.         else
  88.            w->set_bal(0);
  89.   
  90.         x->set_bal(0);
  91.        }
  92.   
  93.       break;
  94.     }
  95.  
  96.     v = u;
  97.  
  98.   }
  99.  
  100. }
  101.  
  102.  
  103. void avl_tree::del_rebal(avl_tree_item v, avl_tree_item)
  104. {
  105.   // precondition:    p is removed inner node
  106.   //                  v is remaining child of p (already linked to parent u)
  107.   //                  v != root
  108.  
  109.   
  110.   while ( v != root() )
  111.   {
  112.     avl_tree_item u = v->parent;
  113.  
  114.     int dir = (v == u->child[left]) ? left : right;
  115.  
  116.     int b = u->get_bal();
  117.  
  118.     if (dir==left)  // deletion in left  subtree of u
  119.        b++;
  120.     else            // deletion in right subtree of u
  121.        b--;
  122.  
  123.     u->set_bal(b);
  124.  
  125.     if (b == 1 || b == -1) break;   // height of u has not changed
  126.  
  127.     if (b != 0)
  128.     { 
  129.       // u is out of balance (-2 or + 2)
  130.  
  131.       int d = (b < 0) ? -1 : +1;
  132.   
  133.       avl_tree_item w = u->child[1-dir];
  134.   
  135.       if (d * w->get_bal() >= 0)
  136.       { rotation(u,w,1-dir);
  137.         if (w->get_bal() == 0)
  138.           { u->set_bal(d);
  139.             w->set_bal(-d);
  140.             break;
  141.            }
  142.         else
  143.           { u->set_bal(0);
  144.             w->set_bal(0);
  145.            }
  146.         v = w;
  147.        }
  148.       else
  149.       { avl_tree_item x = w->child[dir];
  150.         double_rotation(u,w,x,1-dir);
  151.  
  152.         if (x->get_bal() == d)
  153.            u->set_bal(-d);
  154.         else
  155.            u->set_bal(0);
  156.   
  157.         if (x->get_bal() == -d)
  158.            w->set_bal(d);
  159.         else
  160.            w->set_bal(0);
  161.   
  162.         x->set_bal(0);
  163.         v = x;
  164.        }
  165.     }
  166.  
  167.     else v = u;
  168.  
  169.   }
  170. }
  171.