_rb_tree.c

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

 

  if ( v == list_ptr ) list_ptr = v->son[right];
  v->son[left]->son[right] = v->son[right];           // verkettung
  v->son[right]->son[left] = v->son[left];
  
  pop(u,dir1);
  if (st.empty() )                                      // u = root
     {
       root = u->son[1-dir1];
       if ( root->is_node() )      // tree hat zwei blaetter
         root->gets_black_node();
       else                       // tree besteht nur noch aus root
	 root->gets_black_leaf();

       delete(u);
       clear_key(back->k);
       clear_inf(back->e);
       delete back;
       return;
     }

  pop(p,dir2);
  w = u->son[1-dir1];
  p->son[dir2] = w;
  if (u->is_red() || w->is_red() )    // situation 1 , 2
    { 
      if ( w->is_red() ) w->gets_black_node(); 
      delete(u);
      clear_key(back->k);
      clear_inf(back->e);
      delete back;
      return; 
    } 
  delete(u);

  // situation 3 : schwarztiefe des unterbaums mit wurzel v um 
  //               zu niedrig
  //  =>  tiefe im unterbaum mit wurzel v um 1 erhoehen 
  //      bzw. v wandert weiter nach oben
  // bem: u ist vater von v , w der bruder von v
 
v = w;
u = p;
dir1 = dir2;
  while(1)
{
  w = u->son[1-dir1];
  if ( w->is_black() )              // fall2 , v und bruder w sind black
  {  if ( w->son[1-dir1]->is_red() )  // fall 2.b 
        {
            rotation(u,w,1-dir1);
	    w->c = u->col();
	    u->gets_black_node();
	    (w->son[1-dir1])->gets_black_node();
	    if_root(u,w);
            clear_key(back->k);
            clear_inf(back->e);
            delete back;
	    return;
        }
     else   if ( ( y = w->son[dir1] )->is_red() ) // 2.c 
        { 
	    double_rotation(u,w,y,1-dir1,dir1);
	    y->c = u ->col();
	    u->gets_black_node();
	    if_root(u,y);
            clear_key(back->k);
            clear_inf(back->e);
            delete back;
	    return;
        }
     else if ( u->is_red() )     // fall 2.a2
	{
	    w->gets_red_node();
	    u->gets_black_node();
            clear_key(back->k);
            clear_inf(back->e);
            delete back;
            return; 
	}
     else {                      // fall 2.a1
	    rotation(u,w,1-dir1);
	    u->gets_red_node();
	    if ( u == root )
	         { 
		   root = w ;
                   clear_key(back->k);
                   clear_inf(back->e);
                   delete back;
		   return;
                 }
	    else {
		   pop(u,dir1);
		   u->son[dir1] = w;
		   v = w;
                 }
            // einziger fall , der nicht sofort (d.h.nach einfach- 
	    // oder doppelrotation) terminiert ; v wandert zur wurzel
          }
  }     
else                      // fall 3 ; v ist black, w ist red
  { x1 = w->son[dir1];
    if ( x1->son[1-dir1]->is_red() )              // fall 3.b
      { 
        double_rotation(u,w,x1,1-dir1,dir1);
        w->son[dir1]->gets_black_node();
	if_root(u,x1);
        clear_key(back->k);
        clear_inf(back->e);
        delete back;
        return;
      }
    else if ( ( y = x1->son[dir1] )->is_red() )   // fall 3.c
      {
        rotation(x1,y,dir1);
        w->son[dir1] = y; 
	double_rotation(u,w,y,1-dir1,dir1);
        y->gets_black_node();
	if_root(u,y);
        clear_key(back->k);
        clear_inf(back->e);
        delete back;
	return;
      }
    else                                         // fall 3.a 
      { 
        rotation(u,w,1-dir1);
	w->gets_black_node();
	x1->gets_red_node ();
	if_root(u,w);
        clear_key(back->k);
        clear_inf(back->e);
        delete back;
	return;
      }
  }  // end of fall 1,2,3
} // end of while(1)
} // end of del


//------------------------------------------------------------------
// operator=
//------------------------------------------------------------------

rb_tree& rb_tree::operator=(const rb_tree& t)
{
   if (this == &t) return *this;

   clear();

   if ( t.root )   
   { rb_tree_node* pre = 0;
     root = t.copy_tree(t.root,pre);
     list_ptr = root;
     while (list_ptr->son[left]) list_ptr = list_ptr->son[left];
     list_ptr->son[left] = pre;
     pre->son[right] = list_ptr;
     counter = t.counter;
   }

   return *this; 
}

//------------------------------------------------------------------
// rb_tree(rb_tree&) constructor :
//------------------------------------------------------------------

  rb_tree::rb_tree(const rb_tree& t)  : st(32)
  { root  = list_ptr = 0 ;
    if ( t.root ) 
    { rb_tree_node* pre = 0;
      root = t.copy_tree(t.root,pre);
      list_ptr = root;
      while (list_ptr->son[left]) list_ptr = list_ptr->son[left];
      list_ptr->son[left] = pre;
      pre->son[right] = list_ptr;
      counter = t.counter; 
     }
  }

//------------------------------------------------------------------
// copy_tree(p) kopiert baum mit wurzel p und gibt pointer auf wurzel
// der kopie zurueck. pre enthaelt letztes erzeugtes Blatt ( Blaetter 
// werden von links nach rechts erzeugt!
//------------------------------------------------------------------

rb_tree_node* rb_tree::copy_tree( rb_tree_node* p, rb_tree_node_ptr& pre) const
{
  rb_tree_node* q = new rb_tree_node(p);  // q = p

  if ( p->is_node() )  // internal node: copy subtrees 
  {
    q->son[left] = copy_tree(p->son[left],pre);
    q->son[right] = copy_tree(p->son[right],pre);
  }
  else   //leaf: chaining with last created leaf "pre"
  {
    copy_key(q->k);
    copy_inf(q->e);

    if (pre) pre->son[right] = q; 
    q->son[left] = pre;
    pre = q;

   }

  return q;
}

//------------------------------------------------------------------
// clear
//------------------------------------------------------------------

void rb_tree::clear() 
{
   st.clear();

   if ( root )
   { del_tree(root);
     root = list_ptr = 0;
     counter = 0;
   }
}

//------------------------------------------------------------------
// del_tree(p) : loeschen des unterbaums mit wurzel p
//------------------------------------------------------------------

void rb_tree::del_tree(rb_tree_node* p)
{
  if ( p->is_node() )
  { del_tree(p->son[left]);
    del_tree(p->son[right]);
   }
  else
  { clear_key(p->k);
    clear_inf(p->e);
   }

  delete(p);
}

//-----------------------------------------------------------------
// test auf schwarztiefe und bildhafte darstellung des baums nur
// im Trace-modus moeglich
//-----------------------------------------------------------------

#ifdef TEST1

int rb_tree::deep_test(rb_tree_node* p) const
{
  if ( p->is_node() )
  {
    int i = deep_test(p->son[left]);
    if ( i && i == deep_test( p->son[right] ) )
        // falls i=0  => fehler im  linken sohn
        return ( p->is_black() ? i+1  : i ) ;
    else return false ;    // fehler => return false = 0
  }
  else return 1;           // p ist blatt ( immer black )      
}

int rb_tree::black_deep_test() const
{
  if ( root )    // falls treesize > 0
    return ( deep_test(root) ? true : false ) ;
  else return true;
}

//------------------------------------------------------------------
// print()    : ausgeben des rb_trees ( um 90 grad gedreht )
//              nur fuer type = int  
// print_tree(p) : ausgeben des unterbaums mit wurzel p
//------------------------------------------------------------------
 
void rb_tree::print_tree(rb_tree_node* p,int h) const
{  
       if ( p->is_node() ) print_tree(p->son[right],h+1);

       for( int j=1; j <= h ; j++ ) cout << "     ";

       switch (p->col())   {
          case node_black   : cout << " b "; break;
          case leaf_black   : cout << " b "; break;
          case node_red     : cout << " r "; break;
          case leaf_red     : cout << " r "; break;
          case unknown      : cout << " u "; break;
          default           : cout << " ? "; break;
       }
       cout << int(key(p)) ;
       if ( p->is_leaf() )
       {
         cout << string(" succ : %d",int(key(p->son[right]))) ;
         cout << string(" pred : %d\n",int(key(p->son[left]))) ;
       }
       else cout << "\n";

       if ( p->is_node() ) print_tree(p->son[left],h+1);
}

void rb_tree::print() const
{
  cout << "tree.size : " << size() << "\n";
  if ( root ) print_tree(root,1);
}
        
#endif TEST1


void rb_tree::draw(DRAW_RB_NODE_FCT draw_red_node,
                   DRAW_RB_NODE_FCT draw_black_node,
                   DRAW_RB_EDGE_FCT draw_edge, 
                   rb_tree_node* r, 
                   double x1, double x2, double y, 
                   double ydist, double last_x)
{ 

 double x = (x1+x2)/2;

 if (r==nil) return;

 if (last_x != 0) draw_edge(last_x,y+ydist,x,y);

 if (r->is_red()) 
    draw_red_node(x,y,r->k);
 else 
    draw_black_node(x,y,r->k);

 if (r->is_node()) 
 { draw(draw_red_node,draw_black_node,draw_edge,r->son[0],x1,x,y-ydist,ydist,x);
   draw(draw_red_node,draw_black_node,draw_edge,r->son[1],x,x2,y-ydist,ydist,x);
  }
}


void rb_tree::draw(DRAW_RB_NODE_FCT draw_red_node,
                   DRAW_RB_NODE_FCT draw_black_node, 
                   DRAW_RB_EDGE_FCT draw_edge, 
                   double x1, double x2, double y, double ydist)
{ draw(draw_red_node,draw_black_node,draw_edge,root,x1,x2,y,ydist,0); }


//------------------------------------------------------------------
// end of rb_tree.c
//------------------------------------------------------------------