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 / _rs_tree.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  2KB  |  69 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _rs_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/rs_tree.h>
  19.  
  20. //----------------------------------------------------------------------------
  21. //  rs_tree:
  22. //
  23. //  rebalancing of randomized search trees
  24. //
  25. //  S. N"aher (1993)
  26. //----------------------------------------------------------------------------
  27.  
  28.  
  29. void rs_tree::insert_rebal(rs_tree_item v)
  30. {
  31.   rs_tree_item u = v->parent;
  32.  
  33.   int prio = v->get_bal();
  34.  
  35.   ROOT.set_bal(prio);
  36.  
  37.   if (prio < u->get_bal())
  38.   {
  39.     int dir = (v == u->child[left]) ? left : right;
  40.  
  41.     while (prio < u->get_bal())                   /* rotate v up        */
  42.     {                                                /*       p            */
  43.       bin_tree_node* p = u->parent;                  /*       |            */
  44.       bin_tree_node* r = v->child[1-dir];            /*       |            */
  45.       u->child[dir] = r;                             /*       u            */
  46.       v->child[1-dir] = u;                           /*      / \           */
  47.       u->parent = v;                                 /*     /   \          */
  48.       r->parent = u;                                 /*    *     v (prio)  */
  49.       propagate_modification(5,v,u);                 /*         / \        */
  50.       propagate_modification(4,u,r);                 /*        /   \       */
  51.                                                      /*       r     *      */
  52.       dir = (u == p->child[left]) ? left : right;
  53.       u = p;
  54.      }
  55.   
  56.     // link to parent
  57.   
  58.     u->child[dir] = v;
  59.     v->parent = u;
  60.  
  61.     if (u != &ROOT) 
  62.        propagate_modification(6,u,v);
  63.   }
  64.  
  65. }
  66.  
  67. void rs_tree::del_rebal(rs_tree_item, rs_tree_item) { }
  68.  
  69.