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 / _rb_tree.c < prev    next >
C/C++ Source or Header  |  1996-09-03  |  5KB  |  186 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA 3.4
  4. +
  5. +  _rb_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/rb_tree.h>
  19.  
  20.  
  21. //----------------------------------------------------------------------------
  22. //  rb_tree:
  23. //
  24. //  rebalancing of red black trees
  25. //
  26. //  S. N"aher (1993)
  27. //----------------------------------------------------------------------------
  28.  
  29.  
  30. void rb_tree::insert_rebal(rb_tree_item v)
  31. {
  32.   // preconditions:  v is new node created by insertion
  33.   //                 v != root
  34.   //
  35.   //                    u
  36.   //                    |
  37.   //                    v
  38.   //                   / \ 
  39.   //                  x   y
  40.   //
  41.  
  42.   rb_tree_item u = v->parent;
  43.  
  44.   root()->set_bal(black);
  45.  
  46.   while (u->get_bal() == red)
  47.   {
  48.     int dir = (v == u->child[left]) ? left : right;
  49.  
  50.     rb_tree_item p = u->parent; 
  51.     int dir1 = (u == p->child[left]) ? left : right;
  52.  
  53.     rb_tree_item w = p->child[1-dir1];
  54.  
  55.     if ( w->get_bal() == red )    // p has two red children (u and w)
  56.        { u->set_bal(black);
  57.          w->set_bal(black);
  58.          if (p == root())  
  59.          { p->set_bal(black); 
  60.            break; 
  61.           }
  62.          p->set_bal(red);
  63.          v = p;
  64.          u = p->parent;
  65.         }
  66.     else 
  67.        if (dir1 == dir)      // rebalancing by one rotation
  68.          { rotation(p,u,dir1);
  69.            p->set_bal(red);
  70.            u->set_bal(black);
  71.            break;
  72.           }       
  73.        else
  74.         { double_rotation(p,u,v,dir1);
  75.           p->set_bal(red);
  76.           v->set_bal(black);
  77.           break;
  78.          }
  79.    }
  80.  
  81. }
  82.  
  83.  
  84.  
  85. void rb_tree::del_rebal(rb_tree_item w, rb_tree_item p)
  86. {
  87.   // precondition:    p is removed inner node
  88.   //                  w is remaining child of p (already linked to parent u)
  89.   //                  w != root
  90.  
  91.  
  92.  
  93.   if (p->get_bal()==red) return;  // case 1 : nothing to do
  94.  
  95.   if (w->get_bal()==red)          // case 2
  96.   { w->set_bal(black); 
  97.     return; 
  98.    } 
  99.  
  100.  
  101.   root()->set_bal(black);
  102.  
  103.   rb_tree_item u = w->parent;
  104.   int dir = (w == u->child[left]) ? left : right;
  105.  
  106.   while (true)
  107.   {
  108.     rb_tree_item w = u->child[1-dir];
  109.   
  110.     // situation: black height of subtree rooted at black node 
  111.     // v = u->child[dir] is by one too small, w = sibling of v
  112.     //
  113.     // => increase black height of v or "move" v towards the root
  114.     //
  115.     //                          |                         |
  116.     //                          u                         u
  117.     //           dir=left:     / \        dir=right:     / \
  118.     //                        /   \                     /   \
  119.     //                       v     w                   w     v
  120.     //                            / \                 / \
  121.     //                           /   \               /   \
  122.     //                          y     x             x     y
  123.    
  124.   
  125.     if ( w->get_bal()==black )                    // case 2: v and w are black
  126.       { rb_tree_item y = w->child[1-dir];
  127.         if ( y->get_bal()==red )                  // case 2.b 
  128.            { rotation(u,w,1-dir);
  129.              w->set_bal(u->get_bal());
  130.              u->set_bal(black);
  131.              y->set_bal(black);
  132.              break;
  133.             }
  134.         else   
  135.            if ( (y=w->child[dir])->get_bal()==red ) // case 2.c 
  136.               { double_rotation(u,w,y,1-dir);
  137.                 y->set_bal(u->get_bal());
  138.                 u->set_bal(black);
  139.                 break;
  140.               }
  141.            else 
  142.               if ( u->get_bal()==red )     // case 2.a2
  143.                  { w->set_bal(red);
  144.                    u->set_bal(black);
  145.                    break; 
  146.                   }
  147.               else                        // case 2.a1
  148.                  { rotation(u,w,1-dir);
  149.                    u->set_bal(red);
  150.                    if ( w == root() )
  151.                       break;
  152.                    else // the only non-terminating case
  153.                       { u = w->parent;
  154.                         dir = (w == u->child[left]) ? left : right;
  155.                        }
  156.                   }
  157.       }     
  158.     else                                  // case 3: v ist black, w ist red
  159.       { rb_tree_item x = w->child[dir];
  160.         rb_tree_item y;
  161.         if ( x->child[1-dir]->get_bal()==red )          // case 3.b
  162.           { double_rotation(u,w,x,1-dir);
  163.             w->child[dir]->set_bal(black);
  164.             break;
  165.            }
  166.         else 
  167.            if ( (y = x->child[dir])->get_bal()==red )   // case 3.c
  168.              { rotation(x,y,dir);
  169.                w->child[dir] = y; 
  170.                double_rotation(u,w,y,1-dir);
  171.                y->set_bal(black);
  172.                break;
  173.               }
  174.            else                                     // case 3.a 
  175.              { rotation(u,w,1-dir);
  176.                w->set_bal(black);
  177.                x->set_bal(red);
  178.                break;
  179.               }
  180.        }
  181.   
  182.    } /* end of loop */
  183.  
  184. }
  185.  
  186.