twothree.h

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

 // p becomes deficient as a result of the fix.

   Node23<E,K> *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

      // p is not deficient
      return false;
      }
}

template<class E, class K>
bool TwoThree<E,K>::FixMiddleChild(Node23<E,K> *p)
{// The middle child of p has become
 // deficient.  Fix deficiency.  Return true iff
 // p becomes deficient as a result of the fix.

   Node23<E,K> *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;
      }
}

template<class E, class K>
bool TwoThree<E,K>::FixRightChild(Node23<E,K> *p)
{// The right child of p has become
 // deficient.  Fix deficiency.  Return true iff
 // p becomes deficient as a result of the fix.

   Node23<E,K> *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;
}

template<class E, class K>
bool TwoThree<E,K>::DeleteLargest(Node23<E,K> *p, E& e)
{// Delete the largest element in the subtree with root p.
 // Put this element in e.  Return true iff p becomes deficient.
   if (p->LChild) // p is not a leaf
      if (p->RData == Null)  // p is a 2-node
         if (DeleteLargest(p->MChild, e))
            return FixMiddleChild(p);
         else return false;
      else  // p is a 3-node
         if (DeleteLargest(p->RChild, e))
            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
            }
}

template<class E, class K>
bool TwoThree<E,K>::Delete(const K& k, E& e, Node23<E,K> *p)
{// 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)  // empty subtree
      throw BadInput();

   if (k < p->LData) // delete from left subtree
      if (Delete(k, e, 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) // p is not a leaf
              // delete largest element in p->LChild
              // and place in p->LData
              if (DeleteLargest(p->LChild, p->LData))
                 // 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, e, 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, e, 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, e, p->MChild))
                           return FixMiddleChild(p);
                        else return false;
                     else {// p->RData is element to delete
                           e = p->RData;
                           if (p->LChild) // p is not a leaf
                              // delete largest element in p->MChild
                              // and place in p->RData
                              if (DeleteLargest(p->MChild, p->RData))
                                 // 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;
                                 }
                           }
}

template<class E, class K>
void TwoThree<E,K>::InOutput(Node23<E,K> *t)
{// Output in ascending order.
 // Use an inorder traversal.
   if (t) {InOutput(t->LChild);
           cout << t->LData << " ";
           InOutput(t->MChild);
           if (t->RData != Null) {
              cout << 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 << " ";
              }
          }
}

#endif