_rb_tree.c

数据类型和算法库LEDA 数据类型和算法库LEDA

/*******************************************************************************
+
+  LEDA  3.0
+
+
+  _rb_tree.c
+
+
+  Copyright (c) 1992  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 6600 Saarbruecken, FRG     
+  All rights reserved.
+ 
*******************************************************************************/




//  red-black-tree ( rb-tree )
//  implementation of memberfunctions
//  mit verkettung der blaetter

//------------------------------------------------------------------

#include <LEDA/impl/rb_tree.h>


enum left_or_right { left = 0 ,right = 1, undefined = 2 };

enum colour  { node_red = 0 ,node_black = 1 ,leaf_red = 2 ,                                    leaf_black = 3 , unknown = 4 }; 

class rb_tree_node;


rb_tree_node* rb_tree::next_item(rb_tree_node* p) const
{ rb_tree_node* x = p->son[right];
  return (x == list_ptr) ? 0 : x;
 }


rb_tree_node* rb_tree::lookup(GenPtr x) const
{ rb_tree_node* p = find_node(x);
  if ( !p ) return 0;  
  if ( cmp( p->k,x ) == 0 ) return p;
  else return 0;
}

void  rb_tree::change_inf(rb_tree_node* p,GenPtr y) 
{ clear_inf(p->e);
  copy_inf(y);
  p->e = y; 
 }


//------------------------------------------------------------------
// find_node(x) : gibt pointer auf das blatt zurueck , das bei der suche
//                nach dem element mit key x gefunden wird            
//                nil if tree empty
//------------------------------------------------------------------

rb_tree_node* rb_tree::find_node(GenPtr x) const
{ 
  if (root==0) return 0;

  rb_tree_node* p = root;

  if (int_type())
   while (p->is_node()) p = (long(x)<=long(p->k)) ? p->son[left]:p->son[right]; 
  else
   while (p->is_node()) p = (cmp(x,p->k)<=0) ? p->son[left] : p->son[right]; 

  return p;
}

//----------------------------------------------------------------------
// member(x) : true ,falls element with key x im baum , sonst 0
//----------------------------------------------------------------------

int rb_tree::member(GenPtr x) const
{ rb_tree_node* p = find_node(x);
  return ( p  &&  ( cmp(p->k,x) == 0 ) ) ? true : false;
 }

//------------------------------------------------------------------
// access(x) : gibt Eintrag (ref) des elements mit key x zurueck
//------------------------------------------------------------------

GenPtr& rb_tree::access(GenPtr x)
{ rb_tree_node* p = find_node(x);
  if ( p==0  || cmp(x,p->k) != 0 )
    error_handler(1,"rb_tree::access(x): no element with key x in tree");
  return p->e;
}


//----------------------------------------------------------------------
// search :
//----------------------------------------------------------------------
// prog.34 in mehlhorn page 192
// wird fuer insert und delete benoetigt . gibt Stack zurueck, worin 
// pfad von wurzel zum blatt (inkl.) gespeichert ist
//----------------------------------------------------------------------

rb_tree_node* rb_tree::search(GenPtr x)
{
// s.n.: result = inner node with key x (nil if not existing)

  st.clear();

  rb_tree_node* p = root ;

  if (p==0) return nil;

  rb_tree_node* result=nil;

  if (int_type())
     while ( p->is_node())
     { if (long(x) <= long(p->k))
       { if (x == p->k) result = p;
         push(p,left); 
         p = p->son[left];
        } 
       else 
       { push(p,right); 
         p = p->son[right];
        }
      }
  else
     while ( p->is_node())
     { int rel = cmp(x,p->k);
       if (rel <= 0)
       { if (rel == 0) result = p;
         push(p,left); 
         p = p->son[left];
        } 
       else 
       { push(p,right); 
         p = p->son[right];
        }
      }

  push(p,undefined); 

  return result;
}

//----------------------------------------------------------------------
// pop() : private memberfunktion ( fuer insert,delete )
//----------------------------------------------------------------------

void rb_tree::pop(rb_tree_node_ptr& q, int& dir1)
{  stack_el z = st.pop();
   q = z.nodeptr;
   dir1 = z.dir;
}

//----------------------------------------------------------------------
// rotation : private memberfunktion ( fuer insert,delete )
//----------------------------------------------------------------------

void rb_tree::rotation(rb_tree_node* p,rb_tree_node* q, int left_right)
{ p->son[left_right] = q->son[1-left_right];
  q->son[1-left_right] = p;
 }  


//----------------------------------------------------------------------
// double_rotation : private memberfunktion ( fuer insert, delete )
//----------------------------------------------------------------------

void rb_tree::double_rotation(rb_tree_node* p, rb_tree_node* q, rb_tree_node* r,
                              int dir1, int dir2)
{ p->son[dir1] = r->son[dir2];
  q->son[dir2] = r->son[dir1]; 
  r->son[dir1] =q;
  r->son[dir2] =p;
}

//----------------------------------------------------------------------
// if_root : falls p == root => root = q
//           sonst haenge q an frueheren vater von p ( den vater 
//            erhaelt man durch pop )
//----------------------------------------------------------------------

void rb_tree::if_root(rb_tree_node* p,rb_tree_node* q)
{ 
  int dir;

  if ( p == root ) root = q;
  else { pop(p,dir);
         p->son[dir] = q;
       }
}

//----------------------------------------------------------------------
// insert(x,y) : prog. 35/36/37 in mehlhorn seite 193     
// fuegt element mit key x und entry y ein
// gibt zeiger auf eingefuegten knoten zurueck
//----------------------------------------------------------------------

rb_tree_node* rb_tree::insert( GenPtr x, GenPtr y)
{  
   copy_key(x);
   copy_inf(y);

   rb_tree_node* q = new rb_tree_node(x,y,leaf_black,0,0);
   rb_tree_node* r = new rb_tree_node;
   rb_tree_node* p; 
   rb_tree_node* back = q;  // wird von insert zurueckgegeben
   int dir1,dir2;

   ++ counter;

   if ( !root ) 
   { 
     delete r;
     list_ptr = root = q;
     root->son[right] = root->son[left] = root;  // verkettung
     return back ;
   }

   search(x);       // danach steht im Stack st der suchpfad

   pop(p,dir1);

   if ( cmp(p->k,x) == 0 )  
                                      // falls element mit gleichem
   {                                  // key exist. => ueberschreiben
     delete r;
     delete q;
     --counter;
     p->e = y;
     return p;
   }

   r->gets_red_node();
   if ( cmp(x,p->k) < 0 )
      { r->k = x;
        r->son[left] = q;
        r->son[right]= p;

       q->son[left] = p->son[left];   // verkettung
       q->son[right] = p;
       p->son[left]->son[right] = q;
       p->son[left] = q;
       if ( p == list_ptr ) list_ptr = q;     
                // p->key war minimum , x neues minimum
           
      }
    else 
      { r->k = p->k;
        r->son[left] = p;
        r->son[right]= q;

        q->son[left] = p;            // verkettung
        q->son[right] = p->son[right];
        p->son[right]->son[left] = q;
        p->son[right] = q;
      }

    if ( st.empty() )      //  baum vor einfuegen einelementig
      { 
        r->gets_black_node();
        root = r;
        p->son[right] = p->son[left] = q;  // verkettung
        return back ;
      }

    pop(q,dir2);
    q->son[dir2] = r;
    if ( q->is_black() ) return back; // end of prog.35 in mehlhorn
    
    while (1)
    {
      pop(p,dir1);

      if ( p->son[1-dir1]->is_red() ) //p hat 2 rote soehne=> farbtausch
	 { 
	   p->son[left]->gets_black_node();
           p->son[right]->gets_black_node();
	   p->gets_red_node();
	   if ( p == root )  { p->gets_black_node(); return back; }
	   r = p;
	   pop(q,dir2);
	   if ( q->is_black() )  return back;
         }
      else if (dir1 == dir2)      // rebalancieren  durch eine rotation
        {
          rotation(p,q,dir1);
	  p->gets_red_node();
	  q->gets_black_node();
          if_root(p,q);     
	  return back;
        }       
      else
	{
	  double_rotation(p,q,r,dir1,dir2);
	  p->gets_red_node();
	  r->gets_black_node();
          if_root(p,r);     
	  return back;
	}
    }
}
//----------------------------------------------------------------------
// end of insert
//----------------------------------------------------------------------


//----------------------------------------------------------------------
// del(x) :
// loescht element mit key x und gibt entry dieses elements zurueck,
// falls ein solches existiert , sonst 0 .
//----------------------------------------------------------------------

void rb_tree::del(GenPtr x)
{
  rb_tree_node_ptr u,v,w,p,x1,y;
  int dir1,dir2;

  if ( !root ) return; // error_handler(2, " del , but treesize = 0 ");


  rb_tree_node* pp = search(x);  // danach im Stack st der suchpfad gespeichert 
                                 // pp ist innerer Knoten mit Kopie von x
                                 // (nil, falls keiner existiert)
  
  
  pop(v,dir1);

  if ( cmp(v->k,x) != 0 ) return;   // x nicht gefunden: nichts zu tun


  -- counter;
 
  rb_tree_node* back = v;  // back ist zu entfernendes Blatt

  if ( v == root )                                     // treesize = 1
     {
       root = list_ptr = 0;
       clear_key(back->k);
       clear_inf(back->e);
       delete back;
       return;
     } 

  //s.n.: overwrite possible copy of x in inner node pp

  if (pp && v->son[left]) pp->k = v->son[left]->k;