_ab_tree.c

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

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


#include <LEDA/impl/ab_tree.h>

//---------------------------------------------------------------
//  
//  Michael Wenzel:
//  function insert_at_item added
//
//  double links between leaf and inner node with same key
//
//  delete overwrites copies of keys in inner nodes
//
//  leafs are nodes of degree 1, linked by son[1], son[2]
//
//---------------------------------------------------------------

//------------------------------------------------------------------
// constructors
//------------------------------------------------------------------


ab_tree_node::ab_tree_node(int p_,int height_,int index_,ab_tree_node* father_,int b)
{
    son  = (ab_tree_node**) allocate_words(b+2);   /* array[1..b+1] */
    k    = (GenPtr*) allocate_words(b+1);             /* array[1..b]   */
    same = (ab_tree_node**) allocate_words(b+1);   /* array[1..b]   */


    // position 0 contains the size of the array:

    son[0]  = (ab_tree_node*)(b+2);
    k[0]    = GenPtr(b+1);
    same[0] = (ab_tree_node*)(b+1);

    p=p_;
    height=height_;
    index=index_;
    father=father_;
    for(int i=1;i<=(b+1);son[i++]=0);
    for(i=1;i<=b;k[i++]=0);
    for(i=1;i<=b;same[i++]=0);                
   }


 ab_tree_node::~ab_tree_node() 
  { deallocate_words(son,int(son[0]));    /* first array element gives size */
    deallocate_words(same,int(same[0]));
    deallocate_words(k,int(k[0]));
   }




 ab_tree::ab_tree(int a_,int b_)
 {
   root=maximum=minimum=0;
   count=0;
   height=-1;
   if((a_>=2)&&(b_>=2*a_-1))
    { a=a_;
      b=b_;
     }
   else error_handler(1,"ab_tree: illegal arguments (a,b) in tree constructor");
 }

 ab_tree::ab_tree(const ab_tree& T)
  {
     if (T.root==0) {root=maximum=minimum=0;height=-1;count=0;}
     else { abnode help=0;
	    root = T.copy_ab_tree(T.root,help,T.b);
            maximum=help;
            help=root;
            while (help->p) help=help->son[1];
	    minimum=help;
            height=T.height;
            count=T.count;
          };
     a=T.a;
     b=T.b;
  }

//-----------------------------------------------------------------
// operators
//-----------------------------------------------------------------

 ab_tree& ab_tree::operator=(const ab_tree& T)
  {  if (this == &T) return *this;

     clear();

     if (T.root!=0) 
     { abnode help=0;
       root=copy_ab_tree(T.root,help,T.b);
       maximum=help;
       help=root;
       while (help->p) help=help->son[1];
       minimum=help;
       height=T.height;
       count=T.count;
      };

     a=T.a;
     b=T.b;

     return *this;
  }


//-----------------------------------------------------------------
// member functions
//-----------------------------------------------------------------

void ab_tree::exchange_leaves(ab_tree_node* v, ab_tree_node* w)
{ // exchange leaves v and w

  GenPtr k1 = v->k[1]; 
  int p1 = v->index;
  ab_tree_node* u1 = v->same[1];
  ab_tree_node* f1 = v->father;

  GenPtr k2 = w->k[1]; 
  int p2 = w->index;
  ab_tree_node* u2 = w->same[1];
  ab_tree_node* f2 = w->father;


  f1->son[p1] = w;
  w->index    = p1;
  w->same[1]  = u1;
  w->father   = f1;

  f2->son[p2] = v;
  v->index    = p2;
  v->same[1]  = u2;
  v->father   = f2;

  ab_tree_node* pred1 = v->son[1];
  ab_tree_node* succ1 = v->son[2];

  ab_tree_node* pred2 = w->son[1];
  ab_tree_node* succ2 = w->son[2];

  w->son[1] = pred1;
  if (pred1) pred1->son[2] = w;
  if (succ1!=w) 
  { w->son[2] = succ1;
    succ1->son[1] = w;
   }

  if (pred2==v) pred2 = w;


  v->son[1] = pred2;
  v->son[2] = succ2;
  pred2->son[2] = v;
  if (succ2) succ2->son[1] = v;

  // minimum & maximum:
  if (v==minimum) minimum = w;
  if (w==maximum) maximum = v;

  // overwrite inner copies:
  
  int pos1=1;
  while(u1->same[pos1]!=v) pos1++;

  int pos2=1;
  if (u2) while(u2->same[pos2]!=w) pos2++;

  u1->k[pos1] = k2;
  u1->same[pos1] = w;

  if (u2) 
  { u2->k[pos2] = k1;
    u2->same[pos2] = v;
   }

}

void ab_tree::reverse_items(ab_tree_node* v, ab_tree_node* w)
{ // reverse sequence of leaves: v, ..., w

  if (v==w) return;

  if (cmp(v->k[1],w->k[1])<0) 
  { newline;
    cout << "a = "; print_key(v->k[1]); newline;
    cout << "b = "; print_key(w->k[1]); newline;
    error_handler(1,"ab_tree: illegal reverse_items(a,b)\n");
   }

  ab_tree_node* u;

  for(;;)
  { exchange_leaves(v,w);
    u = pred(v);
    if (u == w) break;
    v = succ(w);
    if (v==u) break;
    w = u;
   }

}

 void ab_tree::clear()
   { if (root!=0) {maximum=minimum=0;del_tree(root);root=0;};
     height=-1;
   }

 void ab_tree::del(GenPtr key)
 { if (!root) return;                      // s.n.

   ab_tree_node* w=locate(key);

   if(w && cmp(w->k[1],key) == 0)  del_item(w);

   else /* error_handler(1,"ab_tree: del(key):key is not in tree") */;
 }


ab_tree_node* ab_tree::expand(ab_tree_node* v,int i)

// expand v by returning an additional son to the right of w
// --> w is the i-th son of v
// s.n.: if i==0 then  new leftmost son
// expand does not test a<=number of sons(v)<=b
// m.w. expand does not set same links for new leaves

 {
   // move the nodes right to w to give an additional son to 
   // the right of w

   int l=(v->p);

   if (i < l)
   {
     v->son[l+1]=v->son[l];
     v->son[l+1]->index=l+1;
     l--;
    }

   while(i < l) 
   { 
     v->k[l+1] = v->k[l];
     v->same[l+1] = v->same[l];

     v->son[l+1]=v->son[l];
     v->son[l+1]->index=l+1;

     l--;
    };

   if (v->height>1)
      v->son[i+1] = new ab_tree_node(0,v->height-1,i+1,v,b);
   else  
      v->son[i+1] = new ab_tree_node(0,v->height-1,i+1,v,1);

   (v->p)++;

   return v->son[i+1];
}                     
                     

void ab_tree::split_node(ab_tree_node* v)
{
 /* adding a child increases the degree of v by 1. If v->p<=b after
    adding the new leave, then we are done . Otherwise we have to 
    split v. Splitting can propagate ==> Loop 

    m.w. changes same links between nodes                          */

  ab_tree_node* y;

  while (v->p==b+1) 
  {
    if (v!=root)  y = v->father;
    else 
    { y=new ab_tree_node(1,v->height+1,0,0,b);
      root=y;height++;
      y->son[1]=v;
      v->index=1;
      v->father=y;
     };


    register ab_tree_node* u;

    u = expand(y,v->index);   // u <-- new right brother of v

    int down =(int)((b+1)/2) ;
    int up = (b+1)- down;


    if (u->index <= b)
    { y->k[u->index] = y->k[v->index];
      y->same[u->index] = y->same[v->index];
     }

    y->k[v->index] = v->k[down];
    y->same[v->index]  = v->same[down];
    y->same[v->index]->same[1] = y;    
 

    // split v, i.e. take the rightmost (b+1)/2 children and keys
    // away from v and incorporate them into u and store key v->k[(b+1)/2]
    // in y ( = father(v))  between the pointers to v and u i.e. at position
    // v->index

    // m.w. change same links of v to y and u

    register int j;

    for (j=1;j<up;j++)    
    {
      u->son[j] = v->son[down+j];
      u->son[j]->index=j;
      u->son[j]->father=u;
      u->k[j] = v->k[down+j];
      u->same[j] = v->same[down+j]; 
      u->same[j]->same[1] = u;      

      v->son[down+j] = 0;      // muss das sein ?
      v->same[down+j] = 0;          
      v->k[down+j] = 0;

     };

    u->son[up]=v->son[b+1];
    u->son[up]->index=up;
    u->son[up]->father=u;

    v->son[b+1] = 0;          // und das?
    v->same[down] = 0;                 
    v->k[down] = 0;

    v->p = down;             // change number of children
    u->p = up;

    v = y;
  }

};

ab_tree_node* ab_tree::insert(GenPtr key, GenPtr inf)
{

 if (root==0) { root=new ab_tree_node(0,0,0,0,1);
                copy_key(key);
                copy_inf(inf);
                root->inf = inf;
                root->k[1]= key;
                height=0;
                maximum=minimum=root;
                count++;
                return root;
               }

 // insert_at_item calls copy_key & copy_inf

 ab_tree_node* p = locate(key);
 if (p==nil) p = maximum;
 return insert_at_item(p,key,inf);

};

ab_tree_node* ab_tree::insert_at_item(ab_tree_node* w, GenPtr key, GenPtr inf)
{ 
  // insert a new item (key,inf) left or right of leaf w  (according to key(w))

   copy_inf(inf);

   ab_tree_node* v;

    if (cmp(w->k[1],key)!=0)
    {
      copy_key(key);

     if ( w!=minimum && cmp(w->son[1]->k[1],key) > 0)
      { cout << "INSERT_AT: WRONG POSITION\n";
        cout << "insert:   key = "; print_key(key); cout << "\n";
        if (w!=maximum) 
           cout << "succ-pos: key = "; print_key(w->son[2]->k[1]); cout << "\n";
        cout << "position: key = "; print_key(w->k[1]); cout << "\n";
        cout << "pred-pos: key = "; print_key(w->son[1]->k[1]); cout << "\n";
        error_handler(1,"ab_tree::insert_at : wrong position "); 
       }

     if ( w!=maximum && cmp(w->son[2]->k[1],key) < 0)
      { cout << "INSERT_AT: WRONG POSITION\n";
        cout << "insert:   key = "; print_key(key); cout << "\n";
        cout << "succ-pos: key = "; print_key(w->son[2]->k[1]); cout << "\n";
        cout << "position: key = "; print_key(w->k[1]); cout << "\n";
        if (w!=minimum)
           cout << "pred-pos: key = "; print_key(w->son[1]->k[1]); cout << "\n";
        error_handler(1,"ab_tree::insert_at : wrong position "); 
       }


        count++;
        if (root==w) {   v=new ab_tree_node(2,1,0,0,b);
                         root=v;height=1;
                         ab_tree_node* u;
                         if (cmp(key,w->k[1])<0)
                             {   
                                 u=new ab_tree_node(0,0,1,v,1);
                                 v->son[1]=u;u->k[1]=key; u->inf=inf;