atree.java~27~

av平衡树

/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2006</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
public class ATree {
      ATNode root;  // root node
    public    ATree() {root = null;}

    boolean Search( double k )
    {      // Search for element that matches k.
           // pointer p starts at the root and moves through
           // the tree looking for an element with key k
           ATNode p = root;
           while (p!=null) // examine p->data
              if (k < p.data) p = p.LeftChild;
              else if (k > p.data) p = p.RightChild;
                   else {// found element
                          return true;}
           return false;

    }
    public int High(){return High(root);}
    private int High(ATNode a){
        if(a==null)return 0;
        else {
            int n,l,r;
            l=High(a.LeftChild );
            r=High(a.RightChild );
            n=l;
            if(n<r)n=r;
            return ++n;

        }
    }
    void Insert(double e)throws Exception
    {     // Insert e if not duplicate.
           ATNode p = root,  // search pointer
                        pp = null,    // parent of p
                        A = null,     // node with bf != 0
                        PA=null;        // parent of A
           // find place to insert
           // also record most recent node with bf != 0
           // in A and its parent in PA
           while (p!=null) {// examine p->data
              if (p.bf!=0) {// new candidate for A node
                A = p;
                PA = pp;}
              pp = p;
              // move p to a child
              if (e < p.data) p = p.LeftChild;
              else if (e > p.data) p = p.RightChild;
                   else throw new Exception("bad input"); // duplicate
              }

           // get a node for e and attach to pp
           ATNode r = new ATNode (e);
           if (root!=null) {// tree not empty
              if (e < pp.data) pp.LeftChild = r;
              else pp.RightChild = r;}
           else {// insertion into empty tree
                 root = r;
                return;
             }

           // see if we must rebalance or simply change
           // balance factors
           if (A !=null) // 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
                       ATNode 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
                   ATNode 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;
}
    void Delete(double k)throws Exception {
            // Delete element with key k and put it in e.
         // Throw BadInput exception if there is no element
         // with key k.
          // 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 S=new Stack (100);
           // set p to point to node with key k
           ATNode p = root; // search pointer
           while (p!=null && p.data != k){// move to a child of p
              S.Add(p);
              if (k < p.data) p = p.LeftChild;
              else p = p.RightChild;
              }
           if (p==null) throw new Exception(); // no element with key k
          // e = p.data;  // save element to delete

           // restructure tree
           // handle case when p has two children
           if (p.LeftChild!=null && p.RightChild!=null) {// two children
              // convert to zero or one child case
              // find largest element in left subtree of p
              S.Add(p);
              ATNode s = p.LeftChild;
              while (s.RightChild!=null) {// move to larger element
                 S.Add(s);
                 s = s.RightChild;}

              // move largest from s to p
              p.data = s.data;
              p = s;}

           // p has at most one child
           // save child pointer in c
           ATNode c;
           if (p.LeftChild!=null) 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;}
           double f = p.data; // f may not equal e


           // rebalance tree and correct balance factors
           // use stack to retrace path to root
           // set q to parent of deleted node
           ATNode q=null;
           try {S.Delete(q);}
           catch (Exception e)
              {return ;} // root was deleted

           while (q!=null)
              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 ;
                 if (q.bf == -2) {// q is unbalanced
                    // classify imbalance and rotate
                    ATNode B = q.RightChild,
                                PA=null;  // q is A node
                                       // PA is parent of A
                    try {S.Delete(PA);}
                    catch (Exception e)
                       {PA = null;}       // 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 ;
                       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 (Exception e)
                       {return ;}
                    }
                }
              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 ;
                 if (q.bf == 2) {// q is unbalanced
                    // classify imbalance and rotate
                    ATNode B = q.LeftChild,
                               PA=null;  // q is A node
                                       // PA is parent of A
                    try {S.Delete(PA);}
                    catch (Exception e)
                       {PA = null;}       // 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 ;
                       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 (Exception e)
                       {return ;}
                    }
                }

}
    void Ascend() {InOutput(root);
                 System.out.println() ;}
   // void PostOut() {PostOutput(root);
   //                 cout << endl;}


   public void DeleteAll()
   {//Delete all nodes in AVL tree with root t.
         root=null;
   }
    //void InOutput(AVLNode<E,K> *t);
    //void PostOutput(AVLNode<E,K> *t);
  private  void FixBF(ATNode q,ATNode r, double 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;
            }
    }
       private  void RRrotate(ATNode PA, ATNode A , ATNode 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;
        if (PA!=null) // 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;
        }
        void LLrotate(ATNode PA, ATNode A , ATNode 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;
       if (PA!=null) // 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;
        }
   private  void RLrotate(ATNode PA, ATNode A , ATNode B){
            // RL rotation around A.  PA is parent of A
       // and B left child of A.

         ATNode C = B.LeftChild;

         // restructure subtree at A
         A.RightChild = C.LeftChild;
         B.LeftChild = C.RightChild;
         C.LeftChild = A;
         C.RightChild = B;
         if (PA!=null) // 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!=0) {B.bf = 0;
                      A.bf = 1;}
              else // b = 0
                 B.bf = A.bf = 0;
         C.bf = 0;
    }
  private   void LRrotate(ATNode PA, ATNode A , ATNode B){
            // LR rotation around A.  PA is parent of A
     // and B left child of A.
       ATNode C = B.RightChild;
       // restructure subtree at A
       A.LeftChild = C.RightChild;
       B.RightChild = C.LeftChild;
       C.LeftChild = B;
       C.RightChild = A;
       if (PA!=null) // 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!=0) {B.bf = 1;
                    A.bf = 0;}
            else // b = 0
               B.bf = A.bf = 0;
       C.bf = 0;

    }

  private  void InOutput(ATNode t)
    {// Output in ascending order.
     // Use an inorder traversal.
       if (t!=null) {InOutput(t.LeftChild);
               System.out.print( t.data + " ");
               InOutput(t.RightChild);
              }
}
    public static void main(String[] args) {
        ATree a = new ATree();
        try{System.out.println( a.High()) ;
            a.Insert(1);System.out.println( a.High()) ;
            a.Ascend() ;
           a.Insert(2);System.out.println( a.High()) ;
            a.Ascend() ;a.Insert(6);System.out.println( a.High()) ;
            a.Ascend() ;a.Insert(4);
           a.Ascend() ;a.Insert(5);
            a.Ascend() ;
            a.Delete(1) ;a.Ascend() ;
          //  a.Delete(1) ;a.Ascend() ;
            a.Insert(1);
            a.Ascend() ;
        }catch(Exception e){}
    }
}