home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_src.lha / LEDA-3.1c-source / src / dict / _rs_tree.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-17  |  1.5 KB  |  58 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _rs_tree.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. #include <LEDA/impl/rs_tree.h>
  18.  
  19.  
  20. void rs_tree::insert_rebal(rs_tree_item v)
  21. {
  22.   rs_tree_item u = v->parent;
  23.  
  24.   int prio = v->get_bal();
  25.  
  26.   if (prio < u->get_bal())
  27.   {
  28.     int dir = (v == u->child[left]) ? left : right;
  29.  
  30.     while (u != &ROOT && prio < u->get_bal())           // rotate v up   
  31.     {                                                //       p
  32.       rs_tree_item p = u->parent;                    //       |
  33.       rs_tree_item r = v->child[1-dir];              //       |
  34.       u->child[dir] = r;                             //       u
  35.       v->child[1-dir] = u;                           //      / \
  36.       u->parent = v;                                 //     /   \
  37.       r->parent = u;                                 //    *     v (prio)
  38.       propagate_modification(5,v,u);                 //         / \
  39.       propagate_modification(4,u,r);                 //        /   \
  40.                                                      //       r     *
  41.       dir = (u == p->child[left]) ? left : right;
  42.       u = p;
  43.      }
  44.   
  45.     // link to parent
  46.   
  47.     u->child[dir] = v;
  48.     v->parent = u;
  49.  
  50.     if (u!=&ROOT) 
  51.        propagate_modification(6,u,v);
  52.   }
  53.  
  54. }
  55.  
  56. void rs_tree::del_rebal(rs_tree_item, rs_tree_item) { }
  57.  
  58.