_ps_tree.c

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

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


//--------------------------------------------------------------------
//  
//  Priority Search Trees
//
//  Renate Lassen   (1990)
//
// Implementation follows
// Kurt Mehlhorn: Data Structures and Algorithms 3, section III.5.1.2
//
// -------------------------------------------------------------------

#include <LEDA/impl/ps_tree.h>


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

// -------------------------------------------------------------
// lrot() , rrot() , ldrot() , rdrot()
// Rotationen am Knoten p

void ps_tree::lrot(ps_item p, ps_item q)
{ 
  x_typ xh ,yh;

//  cout << "lrot\n";
//  cout << "p :" << p->split_value_x() << "\n";
//  cout << "q :" << q->split_value_x() << "\n";
  ps_item h = p->sohn[right];
//  cout << "h :" << h->split_value_x() << "\n";
  xh = h->x_value();
  yh = h->y_value();
  
  p->sohn[right] = h->sohn[left];
  h->sohn[left] = p;
   
  if (!q) root=h;
  else
  {
   if ( p == q->sohn[left] )   q->sohn[left]=h;
   else q->sohn[right]=h;
  }; 
  
  h->x_val = p->x_value();
  h->y_val = p->y_value();
  p->x_val = p->y_val = 0;

  if (cmp(xh,yh,h->split_value_x(),h->split_value_y())>0)  
      sink(h->sohn[right],xh,yh);
  else  sink(p->sohn[right],xh,yh); 
    
  fill(p);
  
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=p->groesse()+h->sohn[right]->groesse();
}

void ps_tree::rrot(ps_item p, ps_item q)
{ 
  x_typ xh, yh;
  
  //cout << "rrot\n"; 
 // cout << "p :" << p->split_value_x() << "\n";
 // cout << "q :" << q->split_value_x() << "\n";
  ps_item h = p->sohn[left];
 // cout << "h :" << h->split_value_x() << "\n";
  xh=h->x_value();
  yh=h->y_value();
  
  p->sohn[left] = h->sohn[right];
  h->sohn[right] = p;

  if (!q) root=h;
  else
  {
   if ( p == q->sohn[left] ) q->sohn[left] = h;
   else q->sohn[right] = h; 
  };

  h->x_val = p->x_value();
  h->y_val = p->y_value();
  p->x_val = p->y_val = 0;
  
  if (cmp(xh,yh,h->split_value_x(),h->split_value_y())<=0)  
      sink(h->sohn[left],xh,yh);
  else sink(p->sohn[left],xh,yh);
  
  fill(p);

  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=p->groesse()+h->sohn[left]->groesse();
}

void ps_tree::ldrot(ps_item p, ps_item q)
{ 
    
  //cout << "ldrot\n";
  ps_item h = p->sohn[right];
  ps_item t = h->sohn[left];
  rrot(h,p);
  lrot(p,q);
 // cout << "p:" << p->split_value_x() << "\n";
 // cout << "h:" << h->split_value_x() << "\n";
}

void ps_tree::rdrot(ps_item p, ps_item q)
{

  //cout << "rdrot\n";
  ps_item h = p->sohn[left];
  ps_item t = h->sohn[right];
  lrot(h,p);
  rrot(p,q);
 // cout << "p:" << p->split_value_x() << "\n";
  //cout << "h:" << h->split_value_x() << "\n";
  //cout << "t:" << t->split_value() << "\n";
}
 
// ------------------------------------------------------------------
// fill(ps_item)
// fuellt Knoten bei Rotation wieder auf 
  
void ps_tree::fill(ps_item p)
{

 int leer=0;
 int diff=0;
 //cout << "fill\n";
 while (!p->blatt() && leer!=1)
 {
  diff=cmp(p->sohn[left]->y_value(),p->sohn[right]->y_value()); 
  //cout << "diff = " << diff << "\n";
  if (diff==0) leer=1;                                           // Kinder von p gefuellt ?
  else if ( (diff<0 && p->sohn[left]->y_value()!=0) 
            || (diff>0 && p->sohn[right]->y_value()==0))
       {
        p->x_val = p->sohn[left]->x_value();
        p->y_val = p->sohn[left]->y_value();
        p->sohn[left]->x_val = p->sohn[left]->y_val = 0;   
  //cout <<"gefuellt von links :"<<p->split_value()<<":"<<p->x_value()<<":"<<p->y_value()<<"\n";
        p = p->sohn[left];
       }
       else if ( (diff>0 && p->sohn[right]->y_value()!=0) 
                 || (diff<0 && p->sohn[left]->y_value()==0)) 
            {
            p->x_val = p->sohn[right]->x_value();
            p->y_val = p->sohn[right]->y_value();
            p->sohn[right]->x_val = p->sohn[right]->y_val = 0;   
            p->sohn[right]->x_val = p->sohn[right]->y_val =0;
            p = p->sohn[right];
            };
 };
}

// ------------------------------------------------------------------
// sink() 
// laesst Paar (x,y) im Unterbaum mit Wurzel p herabsinken.
   
ps_item ps_tree::sink(ps_item q, x_typ x, x_typ y)
{
 x_typ xh, yh, xneu=x;
 x_typ yneu=y;
 ps_item p =q;
 ps_item inserted; 
 
 while(!p->blatt() && cmp(p->x_value(),0)!=0)
 {
  //cout << "sink\n";
  //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  if (cmp(p->y_value(),0)!=0 && cmp(y,p->y_value())<0)
  {                                                    // Tausch
   xh=p->x_value();
   yh=p->y_value();
   p->x_val=x;
   p->y_val=y;
   x=xh;
   y=yh;
   if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
  //cout << "inserted in Tausch\n";
  //cout << inserted->split_value() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"\n";
  };
  //cout << "hallo\n";
  if (cmp(x,y,p->split_value_x(),p->split_value_y())<=0)   p=p->sohn[left];
  else 
  {
   p=p->sohn[right]; 
  //cout << p->split_value_x() << ":" << p->split_value_y() <<":"<< p->x_value() << ":" << p->y_value() <<"\n";
  };
 };
 p->x_val=x;
 p->y_val=y;
 if (cmp(p->x_value(),xneu)==0 && cmp(p->y_value(),yneu)==0) inserted=p;
 // cout << "inserted" << inserted->split_value_y() <<":"<< inserted->x_value() << ":" << inserted->y_value() <<"\n";
 return inserted;
}

// ------------------------------------------------------------------
// search(x_typ,x_typ)
// sucht Knoten, der das Paar (x,y) enthaelt,
// oder Blatt, an dem neues Blatt fuer x angehaengt werden soll.

 
ps_item ps_tree::search(x_typ x,x_typ y)
{
 ps_item p = root;
 ps_item q = 0;

// cout << "search\n";
 if (root->blatt())
 {
  st.push(root);
  return p;
 }
 else
 {
  st.push(p);
  while ( !p->blatt() && p!=0 )
  {
   if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
   {
    p=0;
   }
   else 
   { 
    if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
    else p=p->sohn[right]; 
    st.push(p);
   }
  }
  return p;
 }
}  

  
// ------------------------------------------------------------------
// locate(x_typ x,x_typ y)
// gibt Knoten oder Blatt mit Inhalt (x,y), falls existiert,
//                                      0 , sonst.
 
ps_item ps_tree::locate(x_typ x,x_typ y)
{
 ps_item p = root;
 ps_item q = 0;

 //cout << "locate\n";
 while ( q==0 && p!=0 && cmp(y,p->y_value())>=0 )
 {
  st.push(p);
  if ( cmp(x,p->x_value())==0 && cmp(y,p->y_value())==0) 
  {
   q=p;
  }
  else 
  { 
   if ( cmp(x,y,p->split_value_x(),p->split_value_y())<=0 ) p=p->sohn[left];
   else p=p->sohn[right]; 
  }
 }
 return q;
}

// ------------------------------------------------------------------
// delleaf(ps_item)
// loescht Blatt von Paar (x,y) und Vater des Blattes.
// ( Zwei Blaetter mit gemeinsamen Vater sind nie beide gefuellt. )
  
void ps_tree::delleaf(ps_item q)
{
 ps_item p;	
 ps_item t;	
 ps_item father;
 x_typ xh,yh;

 //cout << "delleaf\n";
 q->x_val=0;
 q->y_val=0;
 p=st.pop();
 father=st.pop();
 if (q==father->sohn[left] ) father->sohn[left]=0;
 else father->sohn[right]=0;
 delete (q);                                           // loescht Blatt
 t= st.empty() ? 0 : st.top();
 xh=father->x_value();
 yh=father->y_value();
 //cout << "xh: " << xh << "\n";
 //cout << "yh: " << yh << "\n";
  
 if ( father->sohn[left]!=0) q=father->sohn[left];
 else q=father->sohn[right];
 if (t!=0)
 {
  if (father==t->sohn[left])  t->sohn[left]=q;
  else  t->sohn[right]=q;
 }
 else root=q;
 delete(father);                                       // loescht Vater
 
 //cout << "q-x_value: " << q->x_value() << "\n";
 //cout << "q-y_value: " << q->y_value() << "\n";
 //cout << "q-split_value: " << q->split_value() << "\n";
 sink(q,xh,yh);
}
  
// ------------------------------------------------------------------
// insert(x_typ x,x_typ y)
// fuegt ein neues Item (x,y) in den Baum ein
//                 , falls noch nicht vorhanden, 
// Fehlermeldung   ,sonst
// gibt Zeiger auf eingefuegtes Blatt zurueck

ps_item ps_tree::insert(x_typ x,x_typ y)
{ 
 ps_item p;
 ps_item t;
 ps_item father;
 
 if (!root)                                     // neuer Baum
 {  
  ps_item p=new ps_node(x,y,x,y);
  root=p; 
  anzahl=1; 
  return p;
 }
 else
 {
  p=search(x,y);