tbtree.java~4~

av平衡树

     }
}


boolean FixMiddleChild(Node23 p)
{// The middle 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; // midle child of p

  // p->MChild must have been
  // a 2-node before the deletion
  if (lp.RData == Null) {
     // left child of p is a 2-node; combine lp,
     // p->LData and mp; lp becomes a 3-node
     lp.RData = p.LData;
     lp.RChild = mp.LChild;
     //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 {
     // left child of p is a 3-node, borrow from it
     mp.LData = p.LData;
     mp.MChild = mp.LChild;
     mp.LChild = lp.RChild;
     p.LData = lp.RData;
     lp.RData = Null;  // left child is now a 2-node

     // p is not deficient
     return false;
     }
}

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

  Node23 rp = p.RChild, // right child of p
              mp = p.MChild; // midle child of p

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

  return false;
}

boolean DeleteLargest(Node23 p)
{// Delete the largest element in the subtree with root p.
// Put this element in e.  Return true iff p becomes deficient.
  if (p.LChild!=null) // p is not a leaf
     if (p.RData == Null)  // p is a 2-node
        if (DeleteLargest(p.MChild))
           return FixMiddleChild(p);
        else return false;
     else  // p is a 3-node
        if (DeleteLargest(p.RChild))
           return FixRightChild(p);
        else return false;
  else  // p is a leaf
     if (p.RData == Null)  {// p is a 2-node
      //  e = p.LData;
        return true;  // p has become deficient
        }
     else {// p is a 3-node
          // e = p->RData;
           p.RData = Null;
           return false;  // p is not deficient
           }
}

      void Delete(double k)throws Exception
        {if (Delete(k, root)) {
            // root has become deficient

            root = root.LChild;

            }
         }

      boolean Delete(double k, Node23 p)throws Exception
{// Delete element with key k from the 2-3 tree
 // with root p.  Put deleted element in e.
 // Throw BadInput exception if there is no element
 // with key k.
 // Return true iff p is deficient (i.e., has no element)
 // following the deletion.
   if (p==null)  // empty subtree
      throw new Exception ();
         // return false;
   if (k < p.LData) // delete from left subtree
      if (Delete(k, p.LChild))
         // p->LChild has become deficient
         return FixLeftChild(p);
      else return false;  // p is not deficient
   else if (k == p.LData) {// p->LData is element to delete
           //e = p.LData
               ;
           if (p.LChild!=null) // p is not a leaf
              // delete largest element in p->LChild
              // and place in p->LData
              if (DeleteLargest(p.LChild))
                 // p->LChild has become deficient
                 return FixLeftChild(p);
              else return false;  // p is not deficient
           else if (p.RData == Null)
                   // deletion from a 2-node leaf
                   return true;
                else {// deletion from a 3-node leaf
                      p.LData = p.RData;
                      p.RData = Null;
                      return false;
                      }
           }
        else if (p.RData == Null)  // p is a 2-node
                if (Delete(k, p.MChild))
                   // p->MChild has become deficient
                   return FixMiddleChild(p);
                else return false;  // p is not deficient
             else  // p is a 3-node
                if (k > p.RData)
                   if (Delete(k, p.RChild))
                      // p->RChild has become deficient
                      return FixRightChild(p);
                   else return false;  // p is not deficient
                else if (k < p.RData)
                        if (Delete(k,  p.MChild))
                           return FixMiddleChild(p);
                        else return false;
                     else {// p->RData is element to delete
                           //e = p.RData;
                           if (p.LChild!=null) // p is not a leaf
                              // delete largest element in p->MChild
                              // and place in p->RData
                              if (DeleteLargest(p.MChild))
                                 // p->MChild has become deficient
                                 return FixMiddleChild(p);
                              else return false;  // p is not deficient
                           else {// deletion from a 3-node leaf
                                 p.RData = Null;
                                 return false;
                                 }
                           }
}

    //  void InOutput(Node23<E,K> *t);
      //void PostOutput(Node23<E,K> *t);


/**********************************************************
void TwoThree<E,K>::Erase(Node23<E,K> *t)
{// Delete all nodes in 2-3 tree with root t.
 // Use a postorder traversal.
   if (t) {// t has a left and middle subtree
           Erase(t->LChild);
           Erase(t->MChild);

           // erase right subtree if it exists
           if (t->RData != Null) Erase(t->RChild);

           delete t;
           }
}
*************************************************************/










void InOutput(Node23 t)
{// Output in ascending order.
 // Use an inorder traversal.
   if (t!=null) {InOutput(t.LChild);
           System.out.print( t.LData +" ");
           InOutput(t.MChild);
           if (t.RData != Null) {
              System.out.print( t.RData +" ");
              InOutput(t.RChild);
              }
          }
}
      /*********************************************************
template<class E, class K>
void TwoThree<E,K>::PostOutput(Node23<E,K> *t)
{// Output in postorder.
   if (t) {PostOutput(t->LChild);
           PostOutput(t->MChild);
           cout << t->LData << " ";
           if (t->RData != Null) {
              PostOutput(t->RChild);
              cout << t->RData << " ";
              }
          }
}
********************************************/
}
      class ReturnPair23 {


            double element;
            Node23 NodePtr;  // pointer to associated subtree
}