tbtree.java

av平衡树

/**
 * <p>Title: </p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2006</p>
 *
 * <p>Company: </p>
 *
 * @author not attributable
 * @version 1.0
 */
// 2-3 tree



class TBTree {
    Node23 root;  // root node
      double Null;             // denotes null element
   public  TBTree( double NullElement)
         {Null = NullElement;
          root = null;
          }

     boolean Search(double k)
     {// Search for element that matches k.
      // Put matching element in e.
      // Return false if no matching element.

        // pointer p starts at the root and moves through
        // the tree looking for an element with key k
        Node23 p = root;
        while (p!=null) // examine p->data
           if (k < p.LData) p = p.LChild;
           else if (p.RData == Null)  // p is a 2-node
                   if (k == p.LData) {// found match
                                      // e = p.LData;
                                       return true;
                                       }
                   else // k > p->LData
                      p = p.MChild;
                else  // p is a 3-node
                   if (k > p.LData && k < p.RData)
                      p = p.MChild;
                   else if (k > p.RData)
                           p = p.RChild;
                        else {// k matches one of the elements
                             // if (k == p.LData)
                               //  e = p.LData;
                             // else e = p.RData;
                              return true;
                              }

        // no match was found
        return false;
     }

  void Insert(double e)throws Exception
  {// Insert e if not duplicate.
    // Throw BadInput exception if e is either Null or a duplicate.
   if (e == Null)  // cannot insert null element
      throw new Exception ();
   // insert recursively
   ReturnPair23 r = Insert(root, e);

   if (r.element != Null) {// root has split
      // create new root, this is a 2-node
      Node23 NewRoot = new Node23();
      NewRoot.LChild = root;
      NewRoot.MChild = r.NodePtr;
      NewRoot.LData = r.element;
      NewRoot.RData = Null;
      root = NewRoot;
      }
}


      void Ascend()
      {InOutput(root);
          System.out.println();
      }
      void PostOut()
      {PostOutput(root);
          System.out.println();
      }
     // private:

     // void Erase(Node23<E,K> *t);
ReturnPair23 Insert(Node23 p, double e)throws Exception
  {// Insert e into the 2-3 tree with root p.
   // Throw BadInput exception if e is a duplicate.
   // Return the pair (element, pointer) to be inserted in
   // parent of p in case node p splits.  Return a pair
   // with element = Null in case p does not split.
   ReturnPair23 r=new ReturnPair23() ;
   if (p!=null) // p is not empty
      if (p.RData == Null) // p is a 2-node
         if (e < p.LData) {// insert in p->LChild
            r = Insert(p.LChild, e);
            if (r.element != Null) {// p->LChild did split
               // insert r into p as LData and MChild
               p.RData = p.LData ;
               p.RChild = p.MChild;
               p.LData = r.element ;
               p.MChild = r.NodePtr;
               // p does not split
               r.element = Null;
               }
            return r;
            }
         else if (e > p.LData) {// insert in p->MChild
                 r = Insert(p.MChild, e);
                 if (r.element != Null) {// p->MChild did split
                    // insert r into p as RData and RChild
                    p.RData = r.element;
                    p.RChild = r.NodePtr;
                    // p does not split
                    r.element = Null;
                    }
                 return r;
                 }
              else  // e = p->LData, duplicate
                    throw new Exception ();
      else // p is a 3-node
         if (e < p.LData) {// insert in p->LChild
            r = Insert(p.LChild, e);
            if (r.element != Null) {// p->LChild did split
               // now p will split
               // create a new 2-node q for p->RData
               Node23 q = new Node23();
               q.LData = p.RData;
               q.MChild = p.RChild;
               q.LChild = p.MChild;
               q.RData = Null;

               // p becomes a 2-node with LData = r.element
               // and the pair (p->LData, q) is to be
               // inserted in the parent of p
               p.RData = Null;
               //Swap(p.LData, r.element);
               double d=p.LData ;
               p.LData =r.element ;
               r.element =d;
               p.MChild = r.NodePtr;
               r.NodePtr = q;
               }
            return r;
            }
         else if (e > p.RData) {// insert in p->RChild
                 r = Insert(p.RChild, e);
                 if (r.element != Null) {// p->RChild did split
                    // now p will split
                    // create a new 2-node q for r.element
                    Node23 q = new Node23();
                    q.LData = r.element;
                    q.MChild = r.NodePtr;
                    q.LChild = p.RChild;
                    q.RData = Null;

                    // p becomes a 2-node
                    // and the pair (p->MData, q) is to be
                    // inserted in the parent of p
                    r.element = p.RData;
                    r.NodePtr = q;
                    p.RData = Null;  // p is now a 2-node
                    }
                 return r;
                 }
              else
              if (e > p.LData && e < p.RData) {
                      // insert in p->MChild
                      r = Insert(p.MChild, e);
                      if (r.element != Null) {// p->MChild did split
                         // now p will split
                         // create a new 2-node q for p->RData
                         Node23 q = new Node23();
                         q.LData = p.RData;
                         q.MChild = p.RChild;
                         q.LChild = r.NodePtr;
                         q.RData = Null;

                         // p becomes a 2-node
                         // and the pair (r.element, q) is to be
                         // inserted in the parent of p
                         p.RData = Null;  // p is now a 2-node
                         r.NodePtr = q;
                         }
                      return r;
                      }
                    else  // duplicate
                         throw new Exception ();
   else {// p is empty
         // create a pair to insert in parent of p
         r.element = e;
        // System.out.println("kjfj") ;
         r.NodePtr = null;
         return r;
         }
 //  return r;
}

  boolean  FixLeftChild(Node23 p)
{// The left child of p has become
// deficient.  Fix deficiency.  Return true iff
// p becomes deficient as a result of the fix.

  Node23 lp = p.LChild, // left child of p
              mp = p.MChild; // middle child of p

  // the left child of p must have been
  // a 2-node before the deletion
  if (mp.RData == Null) {
     // middle child of p is a 2-node; combine lp,
     // p->LData, and mp; lp becomes a 3-node
     lp.LData = p.LData;
     lp.RData = mp.LData;
     lp.MChild = mp.LChild;
     lp.RChild = mp.MChild;
     //delete mp;
     if (p.RData == Null)  // p was a 2-node
        // p becomes deficient
        return true;
     else  {// p was a 3-node
            // p becomes a 2-node
            p.LData = p.RData;
            p.RData = Null;
            p.MChild = p.RChild;
            return false;
            }
     }
  else {
     // middle child of p is a 3-node, borrow from it
     lp.LData = p.LData;
     lp.MChild = mp.LChild;
     p.LData = mp.LData;
     mp.LChild = mp.MChild;
     mp.MChild = mp.RChild;
     mp.LData = mp.RData;
     mp.RData = Null;  // mp is now a 2-node