iavl.h

数据结构c++语言描述 Borland C++实现

   // define a stack to hold path taken from root
   // to physically deleted node
   // we will not run out of stack space unless
   // the number of elements is much more than 2^60
   Stack<IAVLNode<E,K>*> S(100);

   // set p to point to node with key k
   IAVLNode<E,K> *p = root; // search pointer
   while (p && p->data != k){// move to a child of p
      S.Add(p);
      if (k < p->data) {
         p->LeftSize--;
         p = p->LeftChild;}
      else p = p->RightChild;
      }
   if (!p) {Reset(1, k);
            throw BadInput();} // not found

   e = p->data;  // save element to delete

   // restructure tree
   // handle case when p has two children
   if (p->LeftChild && p->RightChild) {// two children
      // convert to zero or one child case
      // find largest element in left subtree of p
      S.Add(p);
      IAVLNode<E,K> *s = p->LeftChild;
      while (s->RightChild) {// move to larger element
         S.Add(s);
         s = s->RightChild;}

      // move largest from s to p
      p->data = s->data;
      p->LeftSize--;
      p = s;}

   // p has at most one child
   // save child pointer in c
   IAVLNode<E,K> *c;
   if (p->LeftChild) c = p->LeftChild;
   else c = p->RightChild;

   // delete p
   if (p == root) root = c;
   else {// is p a left or right child?
         if (p == S.Top()->LeftChild)
              S.Top()->LeftChild = c;
         else S.Top()->RightChild = c;}
   E f = p->data; // f may not equal e
   delete p;

   // rebalance tree and correct balance factors
   // use stack to retrace path to root
   // set q to parent of deleted node
   IAVLNode<E,K> *q;
   try {S.Delete(q);}
   catch (OutOfBounds)
      {return *this;} // root was deleted

   while (q)
      if (f <= q->data) {
         // deleted from left subtree of q
         // height of left subtree reduced by 1
         q->bf--;
         if (q->bf == -1) // height of q is unchanged
                          // nothing more to do
                          return *this;
         if (q->bf == -2) {// q is unbalanced
            // classify imbalance and rotate
            IAVLNode<E,K> *B = q->RightChild,
                          *PA;  // q is A node
                                // PA is parent of A
            try {S.Delete(PA);}
            catch (OutOfBounds)
               {PA = 0;}       // A is root
            
            switch (B->bf) {
               case 0:    // L0 imbalance
                  RRrotate(PA,q,B);
                  B->bf = 1;
                  q->bf = -1;  // q is A node
                  return *this;
               case 1:    // L1 imbalance
                  RLrotate(PA,q,B);
                  break;  // must continue on path to root
               case -1:   // L-1 imbalance
                  RRrotate(PA,q,B);
               }
            q = PA;
            }
         else {// q->bf is 0
            try {S.Delete(q);}
            catch (OutOfBounds)
               {return *this;}
            }
        }
      else {// f > q->data
         // deleted from right subtree of q
         // height of right subtree reduced by 1
         q->bf++;
         if (q->bf == 1) // height of q is unchanged
                          // nothing more to do
                          return *this;
         if (q->bf == 2) {// q is unbalanced
            // classify imbalance and rotate
            IAVLNode<E,K> *B = q->LeftChild,
                          *PA;  // q is A node
                                // PA is parent of A
            try {S.Delete(PA);}
            catch (OutOfBounds)
               {PA = 0;}       // A is root
            
            switch (B->bf) {
               case 0:    // R0 imbalance
                  LLrotate(PA,q,B);
                  B->bf = -1;
                  q->bf = 1;  // q is A node
                  return *this;
               case 1:    // R1 imbalance
                  LLrotate(PA,q,B);
                  break;  // must continue on path to root
               case -1:   // R-1 imbalance
                  LRrotate(PA,q,B);
               }
            q = PA;
            }
         else {// q->bf is 0
            try {S.Delete(q);}
            catch (OutOfBounds)
               {return *this;}
            }
        }

   return *this;
}


template<class E, class K>
IndexedAVLtree<E,K>& IndexedAVLtree<E,K>::
                     IndexedDelete(int k, E& e)
{// Delete k'th and put it in e.
 // Throw BadInput exception if there is no k'th element.

   // define a stack to hold path taken from root
   // to physically deleted node
   // we will not run out of stack space unless
   // the number of elements is much more than 2^60
   Stack<IAVLNode<E,K>*> S(100);

   // set p to point to node with k'th element
   IAVLNode<E,K> *p = root; // search pointer
   while (p && p->LeftSize != k) {
      S.Add(p);
      if (k < p->LeftSize) {
         p->LeftSize--;
         p = p->LeftChild;}
      else {k -= p->LeftSize;
            p = p->RightChild;}
      }
   if (!p) {// no element to delete, reset LeftSize
            p = root;
            while (p)
               if (k < p->LeftSize) {
                  p->LeftSize--;
                  p = p->LeftChild;}
               else {k -= p->LeftSize;
                     p = p->RightChild;}

             throw BadInput();
             }

   e = p->data;  // save element to delete

   // restructure tree
   // handle case when p has two children
   if (p->LeftChild && p->RightChild) {// two children
      // convert to zero or one child case
      // find largest element in left subtree of p
      S.Add(p);
      IAVLNode<E,K> *s = p->LeftChild;
      while (s->RightChild) {// move to larger element
         S.Add(s);
         s = s->RightChild;}

      // move largest from s to p
      p->data = s->data;
      p->LeftSize--;
      p = s;}

   // p has at most one child
   // save child pointer in c
   IAVLNode<E,K> *c;
   if (p->LeftChild) c = p->LeftChild;
   else c = p->RightChild;

   // delete p
   if (p == root) root = c;
   else {// is p a left or right child?
         if (p == S.Top()->LeftChild)
              S.Top()->LeftChild = c;
         else S.Top()->RightChild = c;}
   E f = p->data; // f may not equal e
   delete p;

   // rebalance tree and correct balance factors
   // use stack to retrace path to root
   // set q to parent of deleted node
   IAVLNode<E,K> *q;
   try {S.Delete(q);}
   catch (OutOfBounds)
      {return *this;} // root was deleted

   while (q)
      if (f <= q->data) {
         // deleted from left subtree of q
         // height of left subtree reduced by 1
         q->bf--;
         if (q->bf == -1) // height of q is unchanged
                          // nothing more to do
                          return *this;
         if (q->bf == -2) {// q is unbalanced
            // classify imbalance and rotate
            IAVLNode<E,K> *B = q->RightChild,
                          *PA;  // q is A node
                                // PA is parent of A
            try {S.Delete(PA);}
            catch (OutOfBounds)
               {PA = 0;}       // A is root
            
            switch (B->bf) {
               case 0:    // L0 imbalance
                  RRrotate(PA,q,B);
                  B->bf = 1;
                  q->bf = -1;  // q is A node
                  return *this;
               case 1:    // L1 imbalance
                  RLrotate(PA,q,B);
                  break;  // must continue on path to root
               case -1:   // L-1 imbalance
                  RRrotate(PA,q,B);
               }
            q = PA;
            }
         else {// q->bf is 0
            try {S.Delete(q);}
            catch (OutOfBounds)
               {return *this;}
            }
        }
      else {// f > q->data
         // deleted from right subtree of q
         // height of right subtree reduced by 1
         q->bf++;
         if (q->bf == 1) // height of q is unchanged
                          // nothing more to do
                          return *this;
         if (q->bf == 2) {// q is unbalanced
            // classify imbalance and rotate
            IAVLNode<E,K> *B = q->LeftChild,
                          *PA;  // q is A node
                                // PA is parent of A
            try {S.Delete(PA);}
            catch (OutOfBounds)
               {PA = 0;}       // A is root
            
            switch (B->bf) {
               case 0:    // R0 imbalance
                  LLrotate(PA,q,B);
                  B->bf = -1;
                  q->bf = 1;  // q is A node
                  return *this;
               case 1:    // R1 imbalance
                  LLrotate(PA,q,B);
                  break;  // must continue on path to root
               case -1:   // R-1 imbalance
                  LRrotate(PA,q,B);
               }
            q = PA;
            }
         else {// q->bf is 0
            try {S.Delete(q);}
            catch (OutOfBounds)
               {return *this;}
            }
        }

   return *this;
}

template<class E, class K>
void IndexedAVLtree<E,K>::
     InOutput(IAVLNode<E,K> *t)
{// Output in ascending order.
 // Use an inorder traversal.
   if (t) {InOutput(t->LeftChild);
           cout << t->data << " ";
           InOutput(t->RightChild);
          }
}

template<class E, class K>
void IndexedAVLtree<E,K>::
     PostOutput(IAVLNode<E,K> *t)
{// Output in postorder.
   if (t) {PostOutput(t->LeftChild);
           PostOutput(t->RightChild);
           cout << t->data << " ";
          }
}

#endif;