_ab_tree.c

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

  if (s2.root==0) return *this;

  if (root==0) 
  { root=s2.root;
    maximum=s2.maximum;
    minimum=s2.minimum;
    height=s2.height;
    count =s2.count;
   }
  else
  { if (cmp(maximum->k[1],s2.minimum->k[1])>=0) 
                    error_handler(1,"ab_tree: join(S,T) : max(S)>=min(T)"); 

    concat(*this,s2,maximum,maximum->k[1]);

    // link leaves 
    maximum->son[2]=s2.minimum;       
    s2.minimum->son[1]=maximum;

    maximum=s2.maximum;              
   }

  s2.root=0;
  s2.maximum=0;
  s2.minimum=0;
  s2.height=-1;

  return *this;
}


/*---------------------------------------------------------------------
  global functions
----------------------------------------------------------------------*/

void concat(ab_tree& s1,ab_tree& s2,ab_tree_node* current,GenPtr cur_key)
{ 
  // Result in s1

  ab_tree_node* v=s1.root;
  ab_tree_node* w=s2.root;
  int h1=v->height;     
  int h2=w->height;
  int i;

  if(h1==h2)
     { ab_tree_node* z=new ab_tree_node(2,h1+1,0,0,s1.b);
       z->son[1]=v;z->son[2]=w; z->k[1]=cur_key;
       z->son[1]->father=z; z->son[2]->father=z;
       z->son[1]->index=1;z->son[2]->index=2;
       z->same[1]=current;              
       current->same[1]=z;              
       s1.height++;
       s1.root=z;
    }
  else { if (h1>h2)
         {
            for(i=1;i<h1-h2;i++,v=v->son[v->p]);  
            v->son[v->p+1]=w;
            v->son[v->p+1]->father=v;
            v->son[v->p+1]->index=v->p+1;
            v->k[v->p]=cur_key;
	    v->same[v->p]=current;     
	    current->same[1]=v;        
 	    v->p++;
	    if (v->p==s1.b+1)  {s1.split_node(v);  };
        }
        else /* h1<h2 */
        {
	   for(i=1;i<=h2-h1-1;i++,w=w->son[1]);
           for(i=w->p;i>1;i--)
            { w->son[i+1]=w->son[i];
              w->son[i+1]->father=w;
  	      w->son[i+1]->index=i+1;
              w->k[i]=w->k[i-1];
	      w->same[i]=w->same[i-1];   
            };
           w->p++;
           w->son[2]=w->son[1];
           w->son[2]->father=w;
           w->son[2]->index=2;
           w->son[1]=v;
           w->son[1]->father=w;
           w->son[1]->index=1;
           w->k[1]=cur_key;
	   w->same[1]=current;             
	   current->same[1]=w;             
           if (w->p==s2.b+1) {s2.split_node(w);};
	   s1.root =  s2.root;
	   s1.height =  s2.height;
        }
      }

  /* maximum/minimum are now undefined  */

}



/*
void ab_tree::split_at_key(GenPtr y,ab_tree& L,ab_tree& R)
{ ab_tree_node* w = locate(y);
  if (!w) error_handler(1,"ab_tree: split: no item ");
  split_at_item(w,L,R);
 }
*/

void ab_tree::split_at_item(ab_tree_node* w,ab_tree& L,ab_tree& R)
  {
    if(((a!=L.a)||(a!=R.a))||((b!=L.b)||(b!=R.b)))
       error_handler(1,"ab_tree: incompatible trees in split operation");
    
    /* initialisation   */
    L.root=L.minimum=L.maximum=0;L.height=-1;
    R.root=R.minimum=R.maximum=0;R.height=-1;

    if(root==0) return;

    if (w==0) 
    { R.root = root;
      R.height = height;
      R.maximum = maximum;
      R.minimum = minimum;
      R.count = count;
      root = 0;
      height = -1;
      maximum = 0;
      minimum = 0;
      count = 0;
      return;
     }

    if (w==maximum) 
    { L.root = root;
      L.height = height;
      L.maximum = maximum;
      L.minimum = minimum;
      L.count = count;
      root = 0;
      height = -1;
      maximum = 0;
      minimum = 0;
      count = 0;
      return;
     }

    ab_tree_node* l;
    ab_tree_node* r;    // pointers to the roots of the left and right subtree


    /* parameters for concat  */

    ab_tree_node* current_l=0 ;
    GenPtr           current_l_key=0;

    ab_tree_node* current_r=0;  
    GenPtr           current_r_key=0;

    int i;


    /* w is a pointer to the leave y  */
    ab_tree_node* v;

    /* store leaf to split at         */
    ab_tree_node* leaf=w;


     l = w;
     r = 0;

      do{
         v=w->father;
         int index_of_w = w->index; 

       /* now we have construct the  left and right subtrees and the pointers
          to the roots  --> we must construct two trees with these roots*/

        if ((L.root==0)&&(l!=0))  { L.root=l;
			            L.height=l->height; 
			            L.root->father=0;
			            L.root->index=0;
			          }
        else { if ((L.root!=0)&&(l!=0))
                 {  ab_tree L1(L.a,L.b);
	            L1.root=l;
                    L1.height=l->height;
                    L1.root->father=0;
                    L1.root->index=0;
	            concat(L1,L,current_l,current_l_key);
	            L.root  = L1.root;
                    L.height= L1.height;
                    L.count = L1.count;

                    L1.root=0;
	         }
             }
       if ((R.root==0)&&(r!=0))  {R.root=r;
		        	  R.height=r->height;
			          R.root->father=0;
			          R.root->index=0;
                                  R.root->p=r->p;
			         }
       else { if ((R.root!=0)&&(r!=0))
                { ab_tree R1(R.a,R.b);
	  	  R1.root=r;
		  R1.height=r->height;
                  R1.root->father=0;
                  R1.root->index=0;
                  R1.root->p=r->p;
		  concat(R,R1,current_r,current_r_key);
                  R1.root=0;
	        }
            }
        if (v!=0)
        {
         if (index_of_w==1)     /* w is leftmost son of v */
         { l=0;
           r=v;
           current_r=v->same[1];
           current_r_key=v->k[1];
	   r->same[1]->same[1]=0;        
	   for(i=2;i<r->p;i++) 
            {  r->son[i-1]=r->son[i];
   	       r->son[i-1]->index=i-1;
 	       r->k[i-1]=r->k[i];
	       r->same[i-1]=r->same[i];  
    	    }
           r->son[r->p-1]=r->son[r->p];    /* last son */
           r->son[r->p-1]->index=r->p-1;
           r->son[r->p]=0;
           r->p--; 
           r->k[r->p]=0;
	   r->same[r->p]=0;      
           if (r->p==1) r=r->son[1];
         } 
         else {if ( index_of_w==v->p )
                 {  r=0;
                    l=v;
		    l->son[l->p]=0;  /* last son */
		    l->p--;
		    current_l=l->same[index_of_w-1];
		    current_l_key=current_l->k[1];
                    l->k[l->p]=0;
		    l->same[l->p]->same[1]=0;   
		    l->same[l->p]=0;            
                    if (l->p==1) l=l->son[1];
		} 
               else  /* if w is not the leftmost or rightmost son of v*/
               {  
                 r=v;
                 l=new ab_tree_node(index_of_w-1,v->height,0,0,R.b);
 		 current_l=v->same[index_of_w-1];
 		 current_l_key=current_l->k[1];
		 current_r=v->same[index_of_w];   
		 current_r_key=current_r->k[1];
		 // current_r=(v->k[index_of_w])-1;   ERROR: liefert neuen Schluessel ;
                 for(i=1;i<index_of_w-1;i++)
   		  {
		   l->son[i]=v->son[i];
		   l->son[i]->index=i;
                   l->son[i]->father=l;
		   l->k[i]=v->k[i];
		   l->same[i]=v->same[i];  
		   l->same[i]->same[1]=l;  
		  };
		 l->son[index_of_w-1]=v->son[index_of_w-1];
		 l->son[index_of_w-1]->index=index_of_w-1;
                 l->son[index_of_w-1]->father=l;

                 r->son[index_of_w] = 0;   // changed

    		 for (i=1;i<r->p-index_of_w;i++)
		  {
		   r->son[i]=r->son[i+index_of_w];
                   r->son[i+index_of_w]=0;
             	   r->son[i]->index=i;
                   r->son[i]->father=r;
		   r->k[i]=r->k[i+index_of_w];
		   r->same[i]=r->same[i+index_of_w]; 
                   r->k[i+index_of_w]=0;
		   r->same[i+index_of_w]=0;
		  };
	         r->son[r->p-index_of_w]=r->son[r->p];  /* last son */
                 r->son[r->p]=0;
		 r->son[r->p-index_of_w]->index=i;
                 r->son[r->p-index_of_w]->father=r;
		 r->p=r->p-index_of_w;
                 if (l->p==1) l=l->son[1];
                 if (r->p==1) r=r->son[1];
                };
               };
              };

 /* initialisation for the next iteration  */
  w=v;
 }
 while (w!=0);


 /* unlink leaves    m.w.         */
 leaf->same[1]=0;
 leaf->son[2]->son[1]=0;
 leaf->son[2]=0;

 /* redefine maximum and minimum  */
 L.minimum=minimum;
 ab_tree_node* help=L.root;
 while (help->p) help=help->son[help->p];
 L.maximum=help;
 help=R.root;
 while (help->son[1]!=0) help=help->son[1];
 R.minimum=help;
 R.maximum=maximum;

 maximum=minimum=root=l=r=0;
 height=-1; 
 count = 0;

 delete l;
 delete r;

}

void ab_tree::pr_ab_tree(ab_tree_node* localroot,int blancs) const

{ 
  if (localroot==0)
   { for(int j=1;j<=blancs;j++) cout<<" ";
     cout << "NIL\n";
     return;
    }
  
  if (localroot->p == 0) 
   { for(int j=1;j<=blancs;j++) cout<<" ";
     print_key(localroot->k[1]); 
/*
     ab_tree_node* s= localroot->same[1];
     cout << " same = "; 
     if (s) print_key(s->k[1]); 
     else cout << "NIL";
*/
     cout << "\n";
    }

   else
    { for(int i=1;i<localroot->p;i++)
      { pr_ab_tree(localroot->son[i],blancs+10);
        for(int j=1;j<=blancs;j++) cout<<" ";
        print_key(localroot->k[i]); 
/*
        cout << " same = "; 
        print_key(localroot->same[i]->k[1]); 
*/
        cout << "\n";
       };
      pr_ab_tree(localroot->son[localroot->p],blancs+10);
    }
} 
 
ab_tree_node* ab_tree::copy_ab_tree(ab_tree_node* localroot,
                                    abnode& last_leaf,int b) const
{ 
  ab_tree_node* r;

  if (localroot->p == 0)   //leaf
   { r=new ab_tree_node(localroot->p,localroot->height,localroot->index,0,1); 

     r->k[1]= localroot->k[1];
     r->inf = localroot->inf;

     copy_key(r->k[1]);
     copy_inf(localroot->inf);

     r->son[1]=last_leaf;
     if (last_leaf) last_leaf->son[2] = r;
     last_leaf = r;               

    }
  else
   { r=new ab_tree_node(localroot->p,localroot->height,localroot->index,0,b); 

     for(int i=1;i<localroot->p;i++)
     { r->son[i]=copy_ab_tree(localroot->son[i],last_leaf,b);
       r->son[i]->father=r;
       r->k[i]=localroot->k[i];
       last_leaf->same[1]=r;        
       r->same[i]=last_leaf;        
      }

     r->son[localroot->p]=copy_ab_tree(localroot->son[localroot->p],last_leaf,b);
     r->son[localroot->p]->father=r;
   }

  return r;
}
        
void ab_tree::del_tree(ab_tree_node* localroot)
{ // deletes subtree  rooted at localroot

  int k = localroot->p;

  for(int i=1;i<=k;i++) del_tree(localroot->son[i]);

  if (k==0) //leaf
  { clear_key(localroot->k[1]);
    clear_inf(localroot->inf);
   }

  delete localroot;
}

void ab_tree::change_inf(ab_tree_node* p, GenPtr x) 
{ clear_inf(p->inf);
  copy_inf(x);
  p->inf = x;
 }