_iv_tree.c

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

      if (!x_nodelist(root)->empty()) 
	 error_handler(1,"noch Intervalle in zu loeschender Wurzel!\n");
      anzahl=0; 
      delete root;
      root=0; 
      return 1; 
    }
    else
    {
     error_handler(0,"Element nicht im Baum\n");  
     return 0;
    }
  else // Baum nicht trivial
  {
    iv_item p,father;
    iv_item pp=search(y);
    if (st.size()==2)                            // Sohn der Wurzel
    { 
      p=st.pop();
      father=st.pop();

      int v1 = cmp(y,split_value(father));
      if (cmp(y,split_value(p))!=0)
      {
        return 0;
      }
      anzahl--;
      if (v1<=0)
      {
        root=root->son[_right];
	if(!x_nodelist(father)->empty())
	  nodelist_swap(father,root);
      }
      else
      {
        root=root->son[_left];
	if(!x_nodelist(father)->empty())
	  {
	    if (!root->son[_right]) 
	       nodelist_swap(father,root);
            else
	    if ((root->son[_right])&&(x_nodelist(father)->size()==2))
            {
	       nodelist_swap(father,root->son[_right]);
	       reorganize_nodelist(root,root->son[_right]);
            }
            else
	       nodelist_swap(father,root->son[_right]);
          } 
      }
      if (!x_nodelist(father)->empty() || !x_nodelist(p)->empty())
	error_handler(1,"Knotenlisten beim Loeschen nicht leer\n");
      delete father;
      delete p;
    }
    else                                // Blatt mit Tiefe >= 2     
    {
      iv_item p=st.pop();
      if (cmp(y,split_value(p))!=0)
      { 
	return 0;
      }
      iv_item q = st.pop();
      father = st.top();
      int v1 = cmp(y,split_value(father));
      int v2 = cmp(y,split_value(q));
      anzahl--;
      if (v1<=0)
        if (v2<=0)
	{
	  father->son[_left]=q->son[_right];
	  if(!x_nodelist(q)->empty())
	    nodelist_swap(q,father->son[_right]);
        }
        else
	{
	  father->son[_left]=q->son[_left];
	  if(!x_nodelist(q)->empty())
	  {
	    if (!father->son[_left]->son[_right])
	       nodelist_swap(q,father->son[_left]);
            else
	    if ((father->son[_left]->son[_right])&&(x_nodelist(q)->size()==2))
            {
	       nodelist_swap(q,father->son[_left]->son[_right]);
	       reorganize_nodelist(father->son[_left],father->son[_left]->son[_right]);
            }
            else
	       nodelist_swap(q,father->son[_left]->son[_right]);
          } 
        }
      else
	if (v2<=0)
	{
	  father->son[_right]=q->son[_right];
	  if(!x_nodelist(q)->empty())
	    nodelist_swap(q,father->son[_right]);
        }
        else
	{
	  father->son[_right]=q->son[_left];
	  if(!x_nodelist(q)->empty())
	  {
	    if (!father->son[_right]->son[_right])
	       nodelist_swap(q,father->son[_right]);
            else
	    if ((father->son[_right]->son[_right])&&(x_nodelist(q)->size()==2))
            {
	       nodelist_swap(q,father->son[_right]->son[_right]);
	       reorganize_nodelist(father->son[_right],father->son[_right]->son[_right]);
            }
            else
	       nodelist_swap(q,father->son[_right]->son[_right]);
          } 
        }
      if (!x_nodelist(p)->empty())
	error_handler(1,"Knotenlisten von p beim Loeschen nicht leer");
      delete p;
      delete q;
    }
  }
  
  // REBALANCIEREN
  iv_item p;
  iv_item father;
  while (!st.empty())
  { p = st.pop();
    father = st.empty() ? 0 : st.top() ;
    p->gr--;              
    float i=p->bal();
    if (i<alpha)
      if (p->son[_right]->bal() <= d)
       lrot(p,father);
      else
       ldrot(p,father);
    else
    if (i>1-alpha)
      if(p->son[_left]->bal() > d)
       rrot(p,father);
      else
       rdrot(p,father);
  }
  return 1;
}


// ------------------------------------------------------------------
// iv_query(x_typ,x_typ)
// gibt alle Intervalle in einer Liste zurueck, die das mit 
// den Parametern uebergebene Intervall schneiden.

interval_list iv_tree::iv_query(x_typ x, x_typ y)
{
 interval_list query_list;
 if (!root)
 {
   error_handler(0,"Baum ist leer");
   return query_list;
 } 
 if (y<x)
 { 
  error_handler(0,"kein Intervall\n");
  return query_list;
 }
 split_pair xp(x,-MAXINT);
 split_pair yp(y,MAXINT);
 split_item xi = &xp;
 split_item yi = &yp;
 iv_item v = root;
 int done=0;
 // Bestimmung der P-Menge mit Hilfe von search-Schleife nach x,
 // unterwegs Abzweig zu search nach y
 // alle zwischen den Pfaden liegenden Knoten werden mit get_all
 // abgearbeitet
 // jeder Knoten wird mit Hilfe von check_iv() nach den in den 
 // Knotenmengen vorhandenen Intervallen, die die Schnittbegingung
 // erfuellen abgearbeitet.
 while (!v->blatt())
 {
   check_nodelist(query_list,v,x,y);
   if (cmp(xi,split_value(v))<=0) // xi <= split(v)
   {
     if ((cmp(yi,split_value(v))>0) && !done)
     {
       y_search(query_list,v->son[_right],yi,x,y);
       done=1;
     }
     else
     {
       if (done)  // klappert den gesamten Unterbaum von v der C-Menge ab
         get_all_in_tree(query_list,v->son[_right]);
     }
     v=v->son[_left];
   }
   else  // xi > split(v)
   {
     v=v->son[_right];
   }
 }
 check_nodelist(query_list,v,x,y);
 return query_list;
}

// ------------------------------------------------------------------
// y_search()
// verzweigt vom Knoten v aus, in einen neuen Suchpfad nach dem y-
// Wert des query-Intervalls und fuehrt auch dort die P-checks durch

void iv_tree::y_search(interval_list& il, iv_item v, split_item ys,
		       x_typ x, x_typ y)
{
 while (!v->blatt())
 {
   check_nodelist(il,v,x,y);
   if (cmp(ys,split_value(v))<=0) // ys <= split(v)
     v=v->son[_left];
   else  // ys > split(v)
   {
     get_all_in_tree(il,v->son[_left]);
     // klappert den gesamten Unterbaum von v der C-Menge ab
     v=v->son[_right];
   }
 }
 check_nodelist(il,v,x,y);
}
  
// ------------------------------------------------------------------
// check_nodelist()
// ueberprueft entsprechend der in MEHLHORN III dargestellten Fall-
// unterscheidung fuer P-Knoten die jeweilige x- oder y-Knotenliste
// oder uebernimmt alle Eintraege.

void iv_tree::check_nodelist(interval_list& il, iv_item v, x_typ x, x_typ y)
{
  if ((split_value(v)->cmp(x,split_value(v)->key1)<=0)
  && (split_value(v)->cmp(split_value(v)->key1,y)<=0))
  // dann ist split(v) im query-Intervall, das damit alle Intervalle
  // der Knotenliste schneidet.
    take_all_iv(il,v);
  else
  if (split_value(v)->cmp(x,split_value(v)->key1)>0)
  // Intervall oberhalb des split(v)
    check_y_iv(il,v,x);
  else
  // Intervall unterhalb des split(v)
    check_x_iv(il,v,y);
}


// ------------------------------------------------------------------
// get_all_in_tree()
// uebernimmt alle im Unterbaum des Knotens v abgespeicherten Inter-
// valle in die uebergebene Liste
// entspricht einer Teilmenge der C-Menge

void iv_tree::get_all_in_tree(interval_list& il, iv_item v)
{
  take_all_iv(il,v);
  if (!v->blatt())
  { 
    get_all_in_tree(il,v->son[_left]);
    get_all_in_tree(il,v->son[_right]);
  }
}

// ------------------------------------------------------------------
// take_all_iv()
// uebernimmt an einem Knoten alle abgespeicherten Intervalle
// in die mituebergebene Liste.

void iv_tree::take_all_iv(interval_list& il, iv_item v)
{
  dic_item it;
  forall_items(it,*(v->x_nodelist()))
  {
    interval_item help = x_nodelist(v)->key(it);
    interval_item ii = new interval(help->koo1, help->koo2);
    il.append(ii);
  }
}


// ------------------------------------------------------------------
// check_y_iv()
// ueberprueft an einem Knoten alle Intervalle der y-Knotenliste
// auf Schnittbedingung mit dem uebergebenen x-Wert des query-
// Intervalls und haengt bei erfuellter Schnittbedingung das In-
// tervall an die mituebergebene Liste an.

  void iv_tree::check_y_iv(interval_list& il, iv_item v, x_typ x)
  { 
      if (!y_nodelist(v)->empty())
      {
	dic_item maxit = y_nodelist(v)->max();
	if (split_value(v)->cmp(y_nodelist(v)->key(maxit)->koo1,x)>=0) 
	{
	  dic_item it = maxit;
	  int intersect = 1;
	  while(it && intersect) 
	  {
	    if (split_value(v)->cmp(y_nodelist(v)->key(it)->koo1,x)>=0) 
	    {
	     interval_item help = y_nodelist(v)->key(it); 
	     interval_item ii = new interval(help->koo2, help->koo1);
	     // die Intervalle der y-Knotenliste haben 1. Komponente
	     // y und 2. Komponente x, zur Rueckgabe ist aber die
	     // umgekehrte Reihenfolge verlangt.
	     il.append(ii);
	    }
	    else
	     intersect = 0;
	    it = y_nodelist(v)->pred(it);
          }
        }
      }
  }

// ------------------------------------------------------------------
// check_x_iv()
// ueberprueft an einem Knoten alle Intervalle der x-Knotenliste
// auf Schnittbedingung mit dem uebergebenen y-Wert des query-
// Intervalls und haengt bei erfuellter Schnittbedingung das In-
// tervall an die mituebergebene Liste an.

  void iv_tree::check_x_iv(interval_list& il, iv_item v, x_typ y)
  { 
      if (!x_nodelist(v)->empty())
      {
	dic_item minit = x_nodelist(v)->min();
	if (split_value(v)->cmp(x_nodelist(v)->key(minit)->koo1,y)<=0) 
	{
	  dic_item it = minit; 
	  int intersect = 1;
	  while(it && intersect) 
	  {
	    if (split_value(v)->cmp(x_nodelist(v)->key(it)->koo1,y)<=0) 
	    {
	     interval_item help = x_nodelist(v)->key(it); 
	     interval_item ii = new interval(help->koo1, help->koo2);
	     // die Intervalle der x-Knotenliste haben 1. Komponente
	     // x und 2. Komponente y.
	     il.append(ii);
	    }
	    else
	     intersect = 0;
	    it = x_nodelist(v)->succ(it);
          }
        }
      }
  }


//-----------------------------------------------------------------------
// void print_split(iv_item) 
// gibt split_value von p aus

  void iv_tree::print_split(iv_item it)   
  { 
    if (it)
      { it->split_value()->print();
        if (it->blatt()) text(" (blatt)\n");
        else text("(Knoten)\n");
       }
    else
      cout << " Knoten leer!\n";
  }




//-----------------------------------------------------------------------
// void pr_iv_tree(iv_item p;int blancs)
// gibt den Baum mit Wurzel p aus

void iv_tree::pr_iv_tree(iv_item p,int blancs)
{
 if (p==0)
 {
  for (int j=1;j<=blancs;j++) cout << " ";
  cout << "NIL\n";
  return;
 }
 else
 {
  pr_iv_tree(p->son[_left],blancs+10); 
  for (int j=1;j<=blancs;j++) cout << " ";
  
  cout << "(" << p->split_value()->key1 << "," << p->split_value()->key2;
  cout << ") ";
  pr_iv_list(p);
  pr_iv_tree(p->son[_right],blancs+10); 
 }
}
 
//-----------------------------------------------------------------------
// void pr_iv_list(iv_item p)
// gibt die Intervalliste eines Knotens p aus

void iv_tree::pr_iv_list(iv_item p)
{
  dic_item it;
  forall_items(it,*(p->x_nodelist()))
  { cout << "[" << x_nodelist(p)->key(it)->koo1;
    cout << "," << x_nodelist(p)->key(it)->koo2 << "]"; 
    cout << "#" << x_nodelist(p)->inf(it) << ";";
   }
  cout << "  *  ";
  forall_items(it,*(p->y_nodelist()))
  { cout << "[" << y_nodelist(p)->key(it)->koo1;
    cout << "," << y_nodelist(p)->key(it)->koo2<< "]"; 
    cout << "#" << y_nodelist(p)->inf(it) << ";";
   }
  cout << "\n";
}

//-----------------------------------------------------------------------
// void pr_list()
// gibt die zurueckgegebene Intervalliste der query aus

void iv_tree::pr_list(interval_list& il)
{
  cout << "Liste: \n";
  if(il.empty()) cout << " leer\n";
  list_item it;
  forall_list_items(it,il)
    il.contents(it)->print(); 
}
    

//-----------------------------------------------------------------------
// Funktion fuer Destruktor
//-----------------------------------------------------------------------
  
void iv_tree::deltree(iv_item p)
{
 if (p)
 {
  if (!p->blatt())
  {
   deltree(p->son[_left]);
   deltree(p->son[_right]);
  }
  delete(p);
 }
}