_bb_tree.c

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

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



//--------------------------------------------------------------------
//  
//  BB[alpha] Trees
//
//  Michael Wenzel   (1989)
//
// Implementation as described in
// Kurt Mehlhorn: Data Structures and Algorithms 1, section III.5.1
//
// -------------------------------------------------------------------
// Aenderungen:
//   - keine virtuellen Funktionen  (M. Wenzel, Nov. 1989)
//   - nicht rekursiv               (M. Wenzel, Nov. 1989)
//   - virtuelle compare-Funktion   (M. Wenzel, Nov. 1989)
//--------------------------------------------------------------------



#undef TEST
#undef DUMP

#include <LEDA/impl/bb_tree.h>

#ifdef TEST
#define DPRINT(x) cout << string x
#else
#define DPRINT(x)   
#endif

#ifdef DUMP
#define DDUMP(x) cout << string x
#else
#define DDUMP(x)   
#endif



enum children { left = 0 , right = 1 };

enum leaf_or_node { Leaf = 0 , Node = 1 } ;


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


  bb_tree::bb_tree(float a)   : st(BSTACKSIZE)
  { 
    root = first = iterator = 0;
    anzahl=0;
    if ((a<=0.25) || (a>1-SQRT1_2))
      error_handler(3,"alpha not in range");
    alpha=a;
    d = 1/(2-alpha) ;
  }

  bb_tree::bb_tree(const bb_tree& w)  : st(BSTACKSIZE)
  { 
    bb_item p;
    bb_item l=0;
    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;
  }

// -------------------------------------------------------------
// locate()
// liefert item mit key(item) >= y und
//              und key(it)   <= key(it) fuer alle it
//                                          mit key(it) >= y
//         0, falls nicht existiert

bb_item bb_tree::locate(GenPtr y)  const

{ DPRINT(("locate %d in Baum %d\n",int(y),int(this)));
  bb_item current;
  if (root==0) return 0;  // by s.n
  current=root;
  while (!current->blatt())
   { DDUMP(("current %d\n",int(current->key())));
     if (cmp(y,current->key())<=0) current=current->sohn[left];
     else current=current->sohn[right];   }
  return (cmp(y,current->key())<=0) ? current : 0 ;
}  

// -------------------------------------------------------------
// located()
// liefert item mit key(item) <= y und
//              und key(it)   >= key(it) fuer alle it
//                                       mit key(it) <= y

bb_item bb_tree::located(GenPtr y)  const

{ bb_item current;
  if (root==0) return 0;  // by s.n
  current=root;
  while (!current->blatt())
   if (cmp(y,current->key())<=0) current=current->sohn[left];
   else current=current->sohn[right];
  if (cmp(y,current->key())==0) return current;
  current = current->sohn[left];
  return (cmp(y,current->key())>=0) ? current : 0 ;
}  

// -------------------------------------------------------------
// lookup()
// liefert item mit key(item)=y , falls existiert
//                            0 , sonst

bb_item bb_tree::lookup(GenPtr y) const

{ bb_item current = locate(y);
  if (current==0) return 0;
  return (cmp(y,current->key())==0) ? current : 0;
}  

// -------------------------------------------------------------  
// member()
// liefert 1 , falls item existiert mit key(item)=y
//         0 , sonst

int bb_tree::member(GenPtr y)

{ bb_item current = locate(y);
  if (current==0) return 0;
  return (cmp(y,current->key())==0);
}  

// ------------------------------------------------------------
// translate()
// liefert info(item) , falls item existiert mit item = locate(y) 
//                  0 , sonst

GenPtr bb_tree::translate(GenPtr y)

{ bb_item current = locate(y);
  if (current==0) return 0;
  return (cmp(y,current->key())==0) ? current->inf : 0;
}  

// ------------------------------------------------------------
// change_obj()
// liefert item mit key(item) = y und setzt info(item) auf x
//                                    , falls existiert
//         0                          , sonst

bb_item bb_tree::change_obj(GenPtr y,GenPtr x)

{ bb_item current = lookup(y);
  if ( current != 0 )
  { current->inf = x ;  
    return current; }
  else return 0;
}  

// ------------------------------------------------------------
// search()
// nachher: st = ( pk ,..., p1 ) mit 
//          pk = locate(y) , p1 = root 
//          p1 , ... , pk ist Suchpfad nach y
// liefert inneren Knoten k mit key(k) = y , falls existiert
//         0                               , sonst

bb_item bb_tree::search(GenPtr y)

{ DPRINT(("search %d in Baum %d\n",int(y),int(this)));
  st.clear();
  bb_item current = root;
  bb_item k = 0;

  if (!root) return 0;         // Baum leer
  while (!current->blatt())
  { DDUMP(("current %d\n",int(current->key())));
    if (cmp(y,current->key())<=0)
    { if (cmp(y,current->key())==0) k=current;
      st.push(current);
      current = current->sohn[left];          }
    else
    { st.push(current);
      current = current->sohn[right];         }
						   }
  st.push(current);
  DDUMP(("Blatt %d\n",int(current->key())));
  return k;
}

// -----------------------------------------------------------
// ord()
// liefert item it mit
//              |{key(it') < key(it) | it' item im Baum}| = k-1
//         0 , falls kein solches item existiert
	
bb_item bb_tree::ord(int k)

{ DPRINT(("ord %d\n",k));
  if (k>anzahl || k<=0) return 0;
  bb_item cur=root;
  while (!cur->blatt())
  { DDUMP(("ord loop k=%d key=%d\n",k,int(cur->key())));
    int l=cur->sohn[left]->groesse();
    if (k>l)
    { k -= l;
      cur=cur->sohn[right];           }
    else cur=cur->sohn[left]; 
  }
  return cur;
}
    
// ------------------------------------------------------------
// move_iterator()
// bewegt Iterator eine Stelle weiter
// falls am Ende , Iterator = 0

bb_item bb_tree::move_iterator()

  { 
    if (!root) 
    { iterator = 0;
      return 0;      }
    
    if (!iterator) iterator = first;
    else if (iterator->sohn[right]==first) iterator = 0;
	 else iterator = iterator->sohn[right];
    return iterator;
  }
    
// ------------------------------------------------------------
// lrot() , rrot() , ldrot() , rdrot()
// Rotationen am Knoten p

void bb_tree::lrot(bb_item p, bb_item q)
{ DDUMP(("lrot p=%d \n",int(p->key())));
  bb_item h = p->sohn[right];
  p->sohn[right] = h->sohn[left];
  h->sohn[left] = p;
  if (!q) root=h;
  else
    if (cmp(p->key(),q->key())>0) q->sohn[right]=h;
    else q->sohn[left]=h;
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=p->groesse()+h->sohn[right]->groesse();
}

void bb_tree::rrot(bb_item p, bb_item q)
{ DDUMP(("rrot p=%d\n",int(p->key())));
  bb_item h = p->sohn[left];
  p->sohn[left] = h->sohn[right];
  h->sohn[right] = p;
  if (!q) root=h;
  else
  { if (cmp(p->key(),q->key())>0) q->sohn[right] = h;
    else q->sohn[left] = h; }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=p->groesse()+h->sohn[left]->groesse();
}

void bb_tree::ldrot(bb_item p, bb_item q)
{ DDUMP(("ldrot p=%d\n",int(p->key())));
  bb_item h = p->sohn[right];
  bb_item g = h->sohn[left];
  p->sohn[right] = g->sohn[left];
  h->sohn[left] =  g->sohn[right];
  g->sohn[left] = p;
  g->sohn[right] = h;
  if (!q) root=g;
  else
  { if (cmp(p->key(),q->key())>0) q->sohn[right] =g ;
    else q->sohn[left] = g ; }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  g->gr=p->groesse()+h->groesse();
}

void bb_tree::rdrot(bb_item p, bb_item q)
{ DDUMP(("rdrot p=%d\n",int(p->key())));
  bb_item h = p->sohn[left];
  bb_item g = h->sohn[right];
  p->sohn[left] = g->sohn[right];
  h->sohn[right] =  g->sohn[left];
  g->sohn[right] = p;
  g->sohn[left] = h;
  if (!q) root=g;
  else
  { if (cmp(p->key(),q->key())>0) q->sohn[right] =g ;
    else q->sohn[left] = g ; }
  p->gr=p->sohn[left]->groesse()+p->sohn[right]->groesse();
  h->gr=h->sohn[left]->groesse()+h->sohn[right]->groesse();
  g->gr=p->groesse()+h->groesse();
}
 
// ------------------------------------------------------------------
// sinsert()
// fuegt ein neues Item (y,x) in den Baum ein
//                 , falls noch kein Item it vorhanden mit key(it)=y
// change_obj(y,x) ,sonst
// fuellt Keller mit zu rebalancierenden Knoten 
// gibt eingefuegtes Blatt zurueck

      bb_item bb_tree::sinsert(GenPtr y,GenPtr x=0)
      { DPRINT(("sinsert %d [%d] in Baum %d\n",int(y),int(x),int(this)));
	bb_item inserted;
	bb_item help;

	if (!alpha) error_handler(5,"alpha nicht gesetzt");
	if (iterator)  error_handler(6,"insert while tree listed");

	st.clear();                           // loesche Suchpfad

	if (!root) { DDUMP(("Baum war leer\n"));
		     bb_item p=new  bb_node(y,x);
		     p->sohn[left]=p;
		     p->sohn[right]=p;
		     root=p; 
		     first=p;
		     first->sohn[left]=first;
		     first->sohn[right]=first;
		     anzahl=1; 
		     inserted = p;
		   }
	else
	  if (root->blatt())