Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
_rb_tree.c
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 5k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

_rb_tree.c：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  _rb_tree.c
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  13. #include <LEDA/impl/rb_tree.h>
  16. //----------------------------------------------------------------------------
  17. //  rb_tree:
  18. //
  19. //  rebalancing of red black trees
  20. //
  21. //----------------------------------------------------------------------------
  24. void rb_tree::insert_rebal(rb_tree_item v)
  25. {
  26.   // preconditions:  v is new node created by insertion
  27.   //                 v != root
  28.   //
  29.   //                    u
  30.   //                    |
  31.   //                    v
  32.   //                   / 
  33.   //                  x   y
  34.   //
  36.   rb_tree_item u = v->parent;
  38.   while (u->get_bal() == red)
  39.   {
  40.     int dir = (v == u->child[left]) ? left : right;
  42.     rb_tree_item p = u->parent; 
  43.     int dir1 = (u == p->child[left]) ? left : right;
  45.     rb_tree_item w = p->child[1-dir1];
  47.     if ( w->get_bal() == red )    // p has two red children (u and w)
  48.        { u->set_bal(black);
  49.          w->set_bal(black);
  50.          if (p == root())  
  51.          { p->set_bal(black); 
  52.            break; 
  53.           }
  54.          p->set_bal(red);
  55.          v = p;
  56.          u = p->parent;
  57.         }
  58.     else 
  59.        if (dir1 == dir)      // rebalancing by one rotation
  60.          { rotation(p,u,dir1);
  61.            p->set_bal(red);
  62.            u->set_bal(black);
  63.            break;
  64.           }       
  65.        else
  66.         { double_rotation(p,u,v,dir1);
  67.           p->set_bal(red);
  68.           v->set_bal(black);
  69.           break;
  70.          }
  71.    }
  73. }
  77. void rb_tree::del_rebal(rb_tree_item w, rb_tree_item p)
  78. {
  79.   // precondition:    p is removed inner node
  80.   //                  w is remaining child of p (already linked to parent u)
  81.   //                  w != root
  85.   if (p->get_bal()==red) return;  // case 1 : nothing to do
  87.   if (w->get_bal()==red)          // case 2
  88.   { w->set_bal(black); 
  89.     return; 
  90.    } 
  93.   rb_tree_item u = w->parent;
  94.   int dir = (w == u->child[left]) ? left : right;
  96.   while (true)
  97.   {
  98.     rb_tree_item w = u->child[1-dir];
  99.   
  100.     // situation: black height of subtree rooted at black node 
  101.     // v = u->child[dir] is by one too small, w = sibling of v
  102.     //
  103.     // => increase black height of v or "move" v towards the root
  104.     //
  105.     //                          |                         |
  106.     //                          u                         u
  107.     //           dir=left:     /         dir=right:     / 
  108.     //                        /                        /   
  109.     //                       v     w                   w     v
  110.     //                            /                  / 
  111.     //                           /                  /   
  112.     //                          y     x             x     y
  113.    
  114.   
  115.     if ( w->get_bal()==black )                    // case 2: v and w are black
  116.       { rb_tree_item y = w->child[1-dir];
  117.         if ( y->get_bal()==red )                  // case 2.b 
  118.            { rotation(u,w,1-dir);
  119.              w->set_bal(u->get_bal());
  120.              u->set_bal(black);
  121.              y->set_bal(black);
  122.              break;
  123.             }
  124.         else   
  125.            if ( (y=w->child[dir])->get_bal()==red ) // case 2.c 
  126.               { double_rotation(u,w,y,1-dir);
  127.                 y->set_bal(u->get_bal());
  128.                 u->set_bal(black);
  129.                 break;
  130.               }
  131.            else 
  132.               if ( u->get_bal()==red )     // case 2.a2
  133.                  { w->set_bal(red);
  134.                    u->set_bal(black);
  135.                    break; 
  136.                   }
  137.               else                        // case 2.a1
  138.                  { rotation(u,w,1-dir);
  139.                    u->set_bal(red);
  140.                    if ( w == root() )
  141.                       break;
  142.                    else // the only non-terminating case
  143.                       { u = w->parent;
  144.                         dir = (w == u->child[left]) ? left : right;
  145.                        }
  146.                   }
  147.       }     
  148.     else                                  // case 3: v ist black, w ist red
  149.       { rb_tree_item x = w->child[dir];
  150.         rb_tree_item y;
  151.         if ( x->child[1-dir]->get_bal()==red )          // case 3.b
  152.           { double_rotation(u,w,x,1-dir);
  153.             w->child[dir]->set_bal(black);
  154.             break;
  155.            }
  156.         else 
  157.            if ( (y = x->child[dir])->get_bal()==red )   // case 3.c
  158.              { rotation(x,y,dir);
  159.                w->child[dir] = y; 
  160.                double_rotation(u,w,y,1-dir);
  161.                y->set_bal(black);
  162.                break;
  163.               }
  164.            else                                     // case 3.a 
  165.              { rotation(u,w,1-dir);
  166.                w->set_bal(black);
  167.                x->set_bal(red);
  168.                break;
  169.               }
  170.        }
  171.   
  172.    } /* end of loop */
  174. }