iavl.h

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

// indexed AVL tree

#ifndef IndexedAVLtree_
#define IndexedAVLtree_

#include "avlnode2.h" 
#include "xcept.h" 
#include "stack.h" 

template<class E, class K>
class IndexedAVLtree {
   public:
      IndexedAVLtree() {root = 0;}
      ~IndexedAVLtree() {Erase(root);}
      bool Search(const K& k, E& e) const;
      bool IndexedSearch(int k, E& e) const;
      IndexedAVLtree<E,K>& Insert(const E& e);
      IndexedAVLtree<E,K>& Delete(const K& k, E& e);
      IndexedAVLtree<E,K>& IndexedDelete(int k, E& e);
      void Ascend() {InOutput(root);
                     cout << endl;}
      void PostOut() {PostOutput(root);
                      cout << endl;}
   protected:
      IAVLNode<E,K> *root;  // root node
      void Reset(int r, const K& k);
      void Erase(IAVLNode<E,K> *t);
      void InOutput(IAVLNode<E,K> *t);
      void PostOutput(IAVLNode<E,K> *t);
      void FixBF(IAVLNode<E,K> *,
                 IAVLNode<E,K>*, const E&);
      void RRrotate(IAVLNode<E,K> *,
                    IAVLNode<E,K>*, IAVLNode<E,K> *);
      void LLrotate(IAVLNode<E,K> *,
                    IAVLNode<E,K>*, IAVLNode<E,K> *);
      void RLrotate(IAVLNode<E,K> *,
                    IAVLNode<E,K>*, IAVLNode<E,K> *);
      void LRrotate(IAVLNode<E,K> *,
                    IAVLNode<E,K>*, IAVLNode<E,K> *);
};


template<class E, class K>
void IndexedAVLtree<E,K>::Erase(IAVLNode<E,K> *t)
{// Delete all nodes in AVL tree with root t.
 // Use a postorder traversal.
   if (t) {Erase(t->LeftChild);
           Erase(t->RightChild);
           delete t;
          }
}

template<class E, class K>
void IndexedAVLtree<E,K>::FixBF(IAVLNode<E,K> *q,
                    IAVLNode<E,K> *r, const E &e)
{// Balance factors from q to r were originally 0.
 // They need to be changed to +1 or -1.
 // Use e to find path from q to r.

   while (q != r)
      if (e < q->data) {
         // height of left subtree has increased
         q->bf = 1;
         q = q->LeftChild;}
      else {
         // height of right subtree has increased
         q->bf = -1;
         q = q->RightChild;}
}

template<class E, class K>
void IndexedAVLtree<E,K>::
     LLrotate(IAVLNode<E,K> *PA,
              IAVLNode<E,K> *A, IAVLNode<E,K> *B)
{// LL rotation around A.  PA is parent of A
 // and B left child of A.

   // restructure subtree at A
   A->LeftChild = B->RightChild;
   B->RightChild = A;
   A->LeftSize -= B->LeftSize;
   if (PA) // A is not the root
           if (A == PA->LeftChild)
              PA->LeftChild = B;
           else PA->RightChild = B;
   else root = B;

   // set balance factors
   A->bf = B->bf = 0;
}

template<class E, class K>
void IndexedAVLtree<E,K>::
     RRrotate(IAVLNode<E,K> *PA,
              IAVLNode<E,K> *A, IAVLNode<E,K> *B)
{// RR rotation around A.  PA is parent of A
 // and B right child of A.

   // restructure subtree at A
   A->RightChild = B->LeftChild;
   B->LeftChild = A;
   B->LeftSize += A->LeftSize;
   if (PA) // A is not the root
           if (A == PA->LeftChild)
              PA->LeftChild = B;
           else PA->RightChild = B;
   else root = B;

   // set balance factors
   A->bf = B->bf = 0;
}

template<class E, class K>
void IndexedAVLtree<E,K>::
     LRrotate(IAVLNode<E,K> *PA,
              IAVLNode<E,K> *A, IAVLNode<E,K> *B)
{// LR rotation around A.  PA is parent of A
 // and B left child of A.

   IAVLNode<E,K> *C = B->RightChild;

   // restructure subtree at A
   A->LeftChild = C->RightChild;
   B->RightChild = C->LeftChild;
   C->LeftChild = B;
   C->RightChild = A;
   A->LeftSize -= B->LeftSize + C->LeftSize;
   C->LeftSize += B->LeftSize;
   if (PA) // A is not the root
           if (A == PA->LeftChild)
              PA->LeftChild = C;
           else PA->RightChild = C;
   else root = C;

   // set balance factors
   int b = C->bf;
   if (b == 1) {B->bf = 0;
                A->bf = -1;}
   else if (b) {B->bf = 1;
                A->bf = 0;}
        else // b = 0
           B->bf = A->bf = 0;
   C->bf = 0;

}

template<class E, class K>
void IndexedAVLtree<E,K>::
     RLrotate(IAVLNode<E,K> *PA,
              IAVLNode<E,K> *A, IAVLNode<E,K> *B)
{// RL rotation around A.  PA is parent of A
 // and B left child of A.

   IAVLNode<E,K> *C = B->LeftChild;

   // restructure subtree at A
   A->RightChild = C->LeftChild;
   B->LeftChild = C->RightChild;
   C->LeftChild = A;
   C->RightChild = B;
   B->LeftSize -= C->LeftSize;
   C->LeftSize += A->LeftSize;
   if (PA) // A is not the root
           if (A == PA->LeftChild)
              PA->LeftChild = C;
           else PA->RightChild = C;
   else root = C;

   // set balance factors
   int b = C->bf;
   if (b == 1) {B->bf = -1;
                A->bf = 0;}
   else if (b) {B->bf = 0;
                A->bf = 1;}
        else // b = 0
           B->bf = A->bf = 0;
   C->bf = 0;

}

template<class E, class K>
bool IndexedAVLtree<E,K>::
     Search(const K& k, E &e) const
{// Search for element that matches k.

   // pointer p starts at the root and moves through
   // the tree looking for an element with key k
   IAVLNode<E,K> *p = root;
   while (p) // examine p->data
      if (k < p->data) p = p->LeftChild;
      else if (k > p->data) p = p->RightChild;
           else {// found element
                 e = p->data;
                 return true;}
   return false;
}


template<class E, class K>
bool IndexedAVLtree<E,K>::
     IndexedSearch(int k, E& e) const
{// Put the k'th element in e.
 // Return false iff there is no k'th element
   IAVLNode<E,K> *p = root;
   while (p)
      if (k < p->LeftSize) p = p->LeftChild;
      else if (k > p->LeftSize) {
   	      k -= p->LeftSize;
              p = p->RightChild;}
           else {e = p->data;
                return true;}
   return false;
}

template<class E, class K>
IndexedAVLtree<E,K>& IndexedAVLtree<E,K>::
                     Insert(const E& e)
{// Insert e if not duplicate.
   IAVLNode<E,K> *p = root,  // search pointer
                 *pp = 0,    // parent of p
                 *A = 0,     // node with bf != 0
                 *PA;        // parent of A
   // find place to insert
   // also record most recent node with bf != 0
   // in A and its parent in PA
   K k = e;   // extract key
   while (p) {// examine p->data
      if (p->bf) {// new candidate for A node
        A = p;
        PA = pp;}
      pp = p;
      // move p to a child
      if (k < p->data) {
         // insert will be in left subtree of p
         p->LeftSize++;
         p = p->LeftChild;}
      else if (k > p->data) p = p->RightChild;
           else {Reset(-1,k);       // reset LeftSize
                 throw BadInput();} //duplicate
      }

   // get a node for e and attach to pp
   IAVLNode<E,K> *r = new IAVLNode<E,K> (e);
   if (root) {// tree not empty
      if (e < pp->data) pp->LeftChild = r;
      else pp->RightChild = r;}
   else {// insertion into empty tree
         root = r;
         return *this;}

   // see if we must rebalance or simply change
   // balance factors
   if (A) // possible rebalancing needed
          if (A->bf < 0) // bf = -1 before insertion
             if (e < A->data) {// insertion in left subtree
                // height of left subtree has increased by 1
                // new bf of A is 0, no rebalancing
                A->bf = 0;
                // fix bf on path from A to r
                FixBF(A->LeftChild,r,e);}
             else {// insertion in right subtree
                // bf of A is -2, rebalance
                IAVLNode<E,K> *B = A->RightChild;
                if (e > B->data) {// RR case
                   FixBF(B->RightChild,r,e);
                   RRrotate(PA,A,B);}
                else {// RL case
                   FixBF(B->LeftChild,r,e);
                   RLrotate(PA,A,B);}
                }
          else // bf = +1 before insertion
             if (e > A->data) {// insertion in right subtree
                // height of right subtree has increased by 1
                // new bf of A is 0, no rebalancing
                A->bf = 0;
                // fix bf on path from A to r
                FixBF(A->RightChild,r,e);}
             else {// insertion in left subtree
                // bf of A is +2, rebalance
                IAVLNode<E,K> *B = A->LeftChild;
                if (e < B->data) {// LL case
                   FixBF(B->LeftChild,r,e);
                   LLrotate(PA,A,B);}
                else {// LR case
                   FixBF(B->RightChild,r,e);
                   LRrotate(PA,A,B);}
                }
   else // A is NULL, no rebalancing
      FixBF(root,r,e);

   return *this;
}

template<class E, class K>
void IndexedAVLtree<E,K>::
     Reset(int r, const K& k)
{// Add r to LeftSize on path to k.
   IAVLNode<E,K> *p = root;
   while (p)
      if (k < p->data) {
         p->LeftSize += r;
         p = p->LeftChild;}
      else if (k > p->data) p = p->RightChild;
           else return;
}

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