_avl_tree.c

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

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


#include <LEDA/impl/avl_tree.h>

enum boolean { FALSE , TRUE };

z_liste avl_tree::listpointer = 0;
z_liste avl_tree::head = 0;

avl_tree_node* avl_tree::copy_tree(avl_tree_node_ptr s)
{ if (s)
  { avl_tree_node* t = new avl_tree_node(s->k,s->i,s->bal);
    copy_key(s->k);
    copy_inf(s->i);
    t->left=copy_tree(s->left);
    t->right=copy_tree(s->right);
    return t;
  }
  return NULL;
}


void avl_tree::del_tree()
{ for (avl_tree_node* q=first_item() ; q ; )
  { avl_tree_node* p=q;
    q = next_item(q);
    delete p ;
    count -=1;
   }
   root=NULL;
}

avl_tree_node* avl_tree::next_item(avl_tree_node* it) const
{
  if (head && head->inhalt==it) 
    { listpointer=head;
      avl_tree_node*  q=(head=head->next ) ? head->inhalt  :NULL;
      delete listpointer;
      return q;
     }
  else 
    if (it->right) 
      return it->right;
    else 
      { avl_tree_node_ptr q=root , p=NULL;
        while (q && q != it) 
        { if (cmp(q->k,it->k) > 0) 
            { p=q;
              q=q->left;
             }
          else 
            q=q->right;
         }
        if (q) return p; else return NULL;
       }
}


avl_tree_node* avl_tree::first_item() const
{ fillup_liste(root);
  avl_tree_node* q=head ? head->inhalt :NULL;
  return q;
}


void avl_tree::fillup_liste(avl_tree_node* wu) const
{ if (wu)                            //durchlaeuft Baum (Zeiger auf Wurzel)
  { fillup_liste(wu->left);          //in symmetrischer Ordnung und legt Liste
    z_liste linkel= new liste;       //aller Knoten an Kopf=head
    linkel->inhalt=wu;
    linkel->next=NULL;
    if (head==NULL) 
       head=listpointer=linkel;
    else 
       { listpointer->next=linkel;
         listpointer=listpointer->next;
        }
    fillup_liste(wu->right);
   }
}


avl_tree_node* avl_tree::min() const
{ if (root)  
  { for (avl_tree_node* q=root ; q->left ; q=q->left);
    return q;
   }
  else return NULL;
}


avl_tree_node* avl_tree::max() const
{ if (root)  
  { for (avl_tree_node* q=root ; q->right ; q=q->right) ;
    return q;
   }
  else return NULL;
}


void avl_tree::del(GenPtr k)
{ int h_diff=FALSE;
  del_search(k,root,h_diff);
}


void avl_tree::del_search(GenPtr k,avl_tree_node_ptr& p,int& h)
{
avl_tree_node * q;                //del_search ist rekursive Funktion , die
if (p == NULL) h=FALSE;           //den Baum auf einen Knoten x mit Schluessel k
else if (cmp(k , p->k) < 0 ) {    //durchsucht und eventuell balanciert ,wenn
        del_search(k,p->left,h);  //ein Knoten geloescht wurde
        if (h) balance_left(p,h); //balance_left steht fuer loeschen im linken 
     }                            //Teilbaum, balance_right entsprechend fuer 
                                  //rechts
else if (cmp(k , p->k) > 0 ) {
        del_search(k,p->right,h);
        if (h) balance_right(p,h);
     }
else {
   q=p;                        //in q steht der Knoten ,welcher geloescht wird
   if (q->right == NULL) {
      p=q->left;               //wenn kein rechter Teilbaum exiestiert , ruecke
      h=TRUE;                  //linken Nachfolger an Stelle von p
   }
   else if (q->left == NULL) {
           p=q->right;        //analog zu rechten Teilbaum , in beiden Faellen
           h=TRUE;            //h=TRUE (bleibt in h bestehen da call by referenz
        }
   else {
     GenPtr khelp=p->k;      //wenn linker und rechter Teilbaum bestehen tausche
     GenPtr ihelp=p->i;      //info und key mit q , der mit dem rechtestem Blatt im linken
     q=del_element(p->left,h);  //Blatt im linken Teilbaum besetzt ist (liefert
     p->k=q->k;                 //del_element)
     p->i=q->i;
     q->k=khelp;
     q->i=ihelp;
     if (h) balance_left(p,h);

  }
count -=1;
delete q;
}
}


avl_tree_node* avl_tree::del_element(avl_tree_node_ptr& p ,int& h)
{ avl_tree_node *q;               //liefert rechtesten Knoten von p
  if (p->right)                   //Aufruf fuer Leftpointer
    { q=del_element(p->right,h);
      if (h) balance_right(p,h);
      return q;
     }
  else 
    { q=p;
      p=p->left;      //und rueckt linken Teilbaum von zuloeschen Element
      h=TRUE;         //an dessen Stelle
      return q;
     }
}


void avl_tree::balance_left(avl_tree_node_ptr& p ,int& h)
{
avl_tree_node_ptr v,w;
int b1,b2;
switch (p->bal) {                   //balanciert Baum in AVL-Ausgeglichenheit
       case -1: p->bal=0;
                break;

       case  0: p->bal=1;
                h=FALSE;
                break;

       case  1: v=p->right;
                if ((b1=v->bal) >= 0) {   //Linksrotation
                   p->right=v->left;
                   v->left=p;
                   if (b1 == 0) {
                      p->bal=1;
                      v->bal=-1;
                      h=FALSE;
                   }
                   else {
                      p->bal=0;
                      v->bal=0;
                   }
                   p=v;
                }
                else {
                   w=v->left;
                   b2=w->bal;
                   v->left=w->right;       //Doppelrotation nach Links
                   w->right=v;
                   p->right=w->left;
                   w->left=p;
                   if (b2 == 1) p->bal=-1; else p->bal=0;
                   if (b2 == -1) v->bal=1; else v->bal=0;
                   w->bal=0;
                   p=w;
                }
                break;
}
}



void avl_tree::balance_right(avl_tree_node_ptr& p ,int& h)
{
avl_tree_node_ptr v,w;
int b1,b2;               //Analog zu balance_left
switch (p->bal) {
       case  1: p->bal=0;
                break;

       case  0: p->bal=-1;
                h=FALSE;
                break;

       case -1: v=p->left;
                if ((b1=v->bal) <= 0) {
                   p->left=v->right;
                   v->right=p;            //Rechtsrotation
                   if (b1 == 0) {
                      p->bal=-1;
                      v->bal=1;
                      h=FALSE;
                   }
                   else {
                      p->bal=0;
                      v->bal=0;
                   }
                   p=v;
                }
                else {
                   w=v->right;
                   b2=w->bal;
                   v->right=w->left;      //Doppelrotation nach rechts
                   w->left=v;
                   p->left=w->right;
                   w->right=p;
                   if (b2 == -1) p->bal=1; else p->bal=0;
                   if (b2 == 1) v->bal=-1; else v->bal=0;
                   w->bal=0;
                   p=w;
                }
                break;
}
}


avl_tree_node* avl_tree::insert(GenPtr k,GenPtr in)
{ int h_diff=FALSE;
  avl_tree_node *q=ins_element(k,in,root,h_diff);
  return q;
}

avl_tree_node_ptr avl_tree::ins_element(GenPtr k, GenPtr i ,avl_tree_node_ptr& p, int& h)
{
avl_tree_node_ptr r,v,w;
                               //ins_element ist rekursive Funktion , die
if (p == NULL) {               //den Baum auf Knoten mit Schluessel k
   p=new avl_tree_node(k,i);   //durchsucht ,einen Neuen Knoten anlegt bei
   h=TRUE;                     //nicht vorhanden sein , und Baum balanciert
   copy_key(k);                //oder info tauscht
   copy_inf(i);
   count += 1;
   return p;
}
else if (cmp(k , p->k) < 0 ) {
        r=ins_element(k ,i ,p->left ,h);       //durchsucht linken Teilbaum
        if (h) {
           switch (p->bal) {
             case 1: p->bal=0;
                     h=FALSE;
                     break;

             case 0: p->bal=-1;
                     break;

            case -1: v=p->left;
                     if (v->bal == -1) {
                        p->left=v->right;
                        v->right=p;           //Rechtsrotation
                        p->bal=0;
                        p=v;
                     }
                     else {
                        w=v->right;
                        v->right=w->left;
                        w->left=v;           //Doppelrotation nach rechts
                        p->left=w->right;
                        w->right=p;
                        if (w->bal == -1) p->bal=1; else p->bal=0;
                        if (w->bal == 1) v->bal=-1; else v->bal=0;
                        p=w;
                     }
                     p->bal=0;
                     h=FALSE;
                     break;
           } /*Ende vom switch*/
        }  /*Ende von if h=TRUE */
        return r;
} /*Ende von Left-Pointer */
else if (cmp( k , p->k) > 0 ) {
        r=ins_element(k ,i ,p->right ,h);    //durchsucht rechten Teilbaum
        if (h) {
           switch (p->bal) {
              case -1: p->bal=0;
                       h=FALSE;
                       break;

              case  0: p->bal=1;
                       break;

              case  1: v=p->right;
                       if (v->bal == 1) {
                          p->right=v->left;  //Linksrotation
                          v->left=p;
                          p->bal=0;
                          p=v;
                       }
                       else {
                         w=v->left;
                         v->left=w->right;
                         w->right=v;
                         p->right=w->left;
                         w->left=p;         //Doppelrotation nach links
                         if (w->bal == 1) p->bal=-1; else p->bal=0;
                         if (w->bal == -1) v->bal=1; else v->bal=0;
                         p=w;
                      }
                      p->bal =0;
                      h=FALSE;
                      break;
           } /* Ende vom switch */
        } /* Ende von if h=TRUE ... */
        return r;
}
else {
   h=FALSE;
   clear_inf(p->i);
   p->i=i;
   copy_inf(i);
   return p;
 }
}



void avl_tree::change_inf(avl_tree_node* p,GenPtr in)
{ clear_inf(p->i);
  p->i=in;
  copy_inf(in);
 }


avl_tree::avl_tree(const avl_tree& x)
{ root=copy_tree(x.root);
  count=x.count;
  head=x.head;
  listpointer=x.listpointer;
}

avl_tree& avl_tree::operator=(const avl_tree& x)
{ if (this == &x) return *this;
  if (!empty())  del_tree();
  root=copy_tree(x.root);
  count=x.count;
  head=x.head;
  listpointer=x.listpointer;
  return (*this);
}


avl_tree_node* avl_tree::search(GenPtr k) const
{ avl_tree_node *q=root; 
  while (q)
  { int b = cmp(k,q->k);
    if (b==0) break;
    q = (b > 0 ) ? q->right : q->left;
   }
  return q;
}