_bb_tree.c

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

	    if (cmp(y,root->key())<0)
	    { DDUMP(("links von Wurzel\n"));
	      bb_item p=new bb_node(y,x,Leaf,root,root);
	      DDUMP(("Blatt[%d] %d %d %d %d\n",(int)p,(int)p->key(),(int)p->info(),(int)p->sohn[left],(int)p->sohn[right]));
	      root->sohn[left]=p;
	      root->sohn[right]=p;
	      bb_item s=new bb_node(y,x,Node,p,root);
	      DDUMP(("Knoten[%d] %d %d %d %d\n",(int)s,(int)s->key(),(int)s->info(),(int)s->sohn[left],(int)s->sohn[right]));
	      first=p;
	      root=s;
	      st.push(s);
	      anzahl++; 
	      inserted = p;
	     }
	    else if (cmp(y,root->key())>0)         // hier rechts einfuegen
		 { DDUMP(("rechts von Wurzel\n"));
		   bb_item p=new bb_node(y,x,Leaf,root,root);
		   root->sohn[left]=p;
		   root->sohn[right]=p;
		   bb_item s=new bb_node(root->key(),root->inf,Node,root,p);
		   root=s;
		   st.push(s);
		   anzahl++;
		   inserted = p;
		  }
		 else { DPRINT(("gleicher Schluessel vorhanden\n"));
			root->inf = x;
			inserted = root;
		       }
	  else                           // root ist innerer Knoten
	  { bb_item father;
	    search(y);                   // fuelle Suchstack 
	    bb_item t=st.pop();
	    father = st.top();
					 // einfuegen
	    if (cmp(y,t->key())<0)
	    { DDUMP(("insert links von Blatt\n"));
	      help = t->sohn[left];
	      bb_item  p = new bb_node(y,x,Leaf,help,t);
	      t->sohn[left]=p;
	      if (first==t) first=p;
	      help->sohn[right]=p;
	      bb_item s=new bb_node(y,x,Node,p,t);
	      if (cmp(s->key(),father->key())<=0) father->sohn[left]=s;
	      else father->sohn[right]=s;
	      anzahl++; 
	      inserted = p;
	      st.push(s);
	    }
	    else if (cmp(y,t->key())>0)     
		 { DDUMP(("insert rechts von Blatt -> neues Maximum\n"));
		   help=t->sohn[right];
		   bb_item p=new bb_node(y,x,Leaf,t,help);
		   t->sohn[right]=p;
		   help->sohn[left]=p;
		   bb_item s=new bb_node(t->key(),t->inf,Node,t,p);

		   father->sohn[right] = s;
		   anzahl++;
		   inserted = p;
		   st.push(s);
		 }
		 else { DPRINT(("gleicher Schluessel vorhanden\n"));
			t->inf = x;
			st.clear();     // keine Rebalancierung notwendig
			inserted = t;
		      }
	  }
	  return inserted;
      }


// ------------------------------------------------------------------
// insert()
// fuegt ein neues Item (y,x) in den Baum ein
//       mittels sinsert
// balanciert Baum mit ueblichen Rotationen
// gibt eingefuegtes Blatt zurueck

bb_item bb_tree::insert(GenPtr y, GenPtr x)
{ 
  bb_item inserted;
  bb_item t,father;

/*
  copy_key(y);
  copy_inf(x);
*/

  inserted = sinsert(y,x);
  if (!st.empty())
    st.pop();                       // pop father of leaf
  
				    // rebalancieren
  while (!st.empty())
  { t=st.pop();
    father = st.empty() ? 0 : st.top();
    t->gr++;  
    float i = t->bal();
    DDUMP(("rebal cur=%d groesse=%d bal=%f\n",int(t->key()),t->groesse(),i));
    if (i < alpha)
      if (t->sohn[right]->bal()<=d) lrot(t,father);
      else ldrot(t,father);
    else if (i>1-alpha) 
           if (t->sohn[left]->bal() > d ) rrot(t,father);
	   else rdrot(t,father);
  }
  DDUMP(("eingefuegtes Blatt hat key %d und info %d\n",int(inserted->key()),int(inserted->info())));
  return inserted;
}

// ------------------------------------------------------------------
// sdel()
// loescht Item it im Baum mit key(it)=y , falls existiert
//         und gibt Zeiger auf it zurueck
// 0 , sonst
// fuellt Keller mit zu rebalancierenden Knoten

bb_item bb_tree::sdel(GenPtr y)
{ DPRINT(("delete %d aus Baum %d\n",int(y),int(this)));

  if (!alpha) error_handler(5,"alpha nicht gesetzt");
  if (iterator)  error_handler(6,"Baum gelistet beim Loeschen");

  st.clear();
  if (root==0) return 0;                         // s.n.

  if (root->blatt())                             // Wurzel loeschen
    if (cmp(y,root->key())==0)
      { DDUMP(("Wurzel loeschen\n"));
        bb_item p = root;
        first=iterator=0;
        anzahl=0; 
        root=0; 
        return p; 
       }
    else 
      { DPRINT(("Element nicht im Baum\n"));  
        return 0; }
  else 
  { bb_item p,father;
    bb_item pp=search(y);

    if (st.size()==2)                            // Sohn der Wurzel
    { DDUMP(("Sohn der Wurzel loeschen\n"));
      p=st.pop();
      father=st.pop();

      int v1 = cmp(y,father->key());
      if (cmp(y,p->key())!=0) { DPRINT(("Element nicht im Baum\n"));
                                return 0; }
      anzahl--;

      if (v1<=0)
        root=root->sohn[right];
      else
        root=root->sohn[left];

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

      st.push(father);
      return p; 
    }
    else                                // Blatt mit Tiefe >= 2     
    { bb_item q=st.pop();

      if (cmp(y,q->key())!=0)
      { DDUMP(("Schluessel nicht vorhanden\n"));
	return 0;   }

      bb_item p = st.pop();
      father=st.top();
      DDUMP(("Blatt %d mit Vater %d , Grossvater %d\n",int(q->key()),int(p->key()),int(father->key())));
      int v2 = cmp(y,p->key());
      int v1 = cmp(y,father->key());
      anzahl--;
      if (v1<=0)
        if (v2<=0)
        { father->sohn[left]=p->sohn[right];
          if (first==q) { first=first->sohn[right];
			  q->sohn[right]->sohn[left]=first; }
	}
        else father->sohn[left]=p->sohn[left];
      else if (v2<=0) father->sohn[right]=p->sohn[right];
           else  father->sohn[right]=p->sohn[left];
      q->sohn[right]->sohn[left]=q->sohn[left];
      q->sohn[left]->sohn[right]=q->sohn[right];
      if ( pp && (p!=pp) && p->sohn[left] )
      { pp->ke = q->sohn[left]->key() ;
        DPRINT(("inneren Knoten mit %d ueberschrieben und Info %d bleibt\n",int(pp->key()),int(pp->info())));
      }
      st.push(p);
      return q;
    }
  }
#if defined(__GNUG__)
  return 0; // never reached ?
#endif
}

// ------------------------------------------------------------------
// del()
// loescht Item it im Baum mit key(it)=y , falls existiert
//         und gibt Zeiger auf it zurueck
// 0 , sonst
// mittels sdel                                     
// rebalanciert Baum danach

bb_item bb_tree::del(GenPtr y)
{
  bb_item p,father;
  bb_item deleted = sdel(y);
  if (!deleted)
    return 0;
  if (!st.empty())
    delete(st.pop());

					 // rebalancieren
  while (!st.empty())
  { p = st.pop();
    father = st.empty() ? 0 : st.top() ;
    p->gr--;              
    float i=p->bal();
    DDUMP(("rebal cur=%d groesse=%d bal=%f\n",int(p->key()),p->groesse(),i));
    if (i<alpha)
      if (p->sohn[right]->bal() <= d) lrot(p,father);
      else ldrot(p,father);
    else if (i>1-alpha)
           if(p->sohn[left]->bal() > d) rrot(p,father);
           else rdrot(p,father);
  }
  return deleted;
} 

// -----------------------------------------------------------------
// Gleichheitsoperator
// weist this Kopie der Baumes w zu

bb_tree& bb_tree::operator=(const bb_tree& w)
{ DDUMP(("operator = wurzel%d\n",(int)w.root->key()));
  bb_item p;
  bb_item l=0;
  if (anzahl!=0) deltree(root); 
  st.clear();
  anzahl=w.anzahl;
  alpha=w.alpha;
  d=w.d;
  iterator=0;
  if (w.root)
  { if (!w.root->blatt())
    { p=new bb_node(w.root);
      first=copytree(p,w.root,l);
      first->sohn[left]=l ;
      l->sohn[right]=first ; }
    else
    { p=new bb_node(w.root);
      first=p; }
    root= p;                       }
  else root = 0;
  DDUMP(("root=%d, first=%d\n",int(root->key()),int(first->key())));
  return *this;
}

bb_item bb_tree::copytree(bb_item p, bb_item q,bb_item& ll) 
{ DDUMP(("copytree %d\n",(int)p->key()));
  bb_item a;
  bb_item r;
  bb_item s;
  if (p->blatt())
  { if (ll==0) p->sohn[left]=0;
    else
    { p->sohn[left]=ll;
      ll->sohn[right]=p; }
    p->sohn[right]=0;
    a=p;
    ll=p; 
    DDUMP(("ll gesetzt %d\n",int(ll->key()))); }
  else {
    r=new bb_node(q->sohn[left]);
    p->sohn[left]=r;
    a=copytree(p->sohn[left],q->sohn[left],ll);
    s=new bb_node(q->sohn[right]);
    p->sohn[right]=s;
    copytree(p->sohn[right],q->sohn[right],ll); }
  return a; 
}

// ------------------------------------------------------------------
// Destruktoren

void bb_tree::clear()
{ if (root)
  { DPRINT(("clear %d\n",int(root->key())));
    deltree(root);
   }
  else DPRINT(("clear\n"));
  root=0;
  anzahl=0;
  first=0;
}

void bb_tree::deltree(bb_item p)
{ if (p)
  { DDUMP(("deltree : current=%d\n",int(p->key())));
    if (!p->blatt())
    {  deltree(p->sohn[left]);
       deltree(p->sohn[right]); 
     }
    delete(p);
  }
}


void bb_tree::draw(DRAW_BB_NODE_FCT draw_node,
                   DRAW_BB_EDGE_FCT draw_edge, 
                   bb_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);

 draw_node(x,y,r->key());

 if (!r->blatt()) 
 { draw(draw_node,draw_edge,r->sohn[0],x1,x,y-ydist,ydist,x);
   draw(draw_node,draw_edge,r->sohn[1],x,x2,y-ydist,ydist,x);
  }
}


void bb_tree::draw(DRAW_BB_NODE_FCT draw_node,
                   DRAW_BB_EDGE_FCT draw_edge, 
                   double x1, double x2, double y, double ydist)
{ draw(draw_node,draw_edge,root,x1,x2,y,ydist,0); }