twothree.h

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

// 2-3 tree

#ifndef TwoThree_
#define TwoThree_

#include "node23.h"
#include "ret23.h"
#include "stack.h"
#include "xcept.h"
#include "swap.h"

template<class E, class K>
class TwoThree {
   public:
      TwoThree(E NullElement)
         {Null = NullElement;
          root = 0;
          }
      ~TwoThree() {Erase(root);}
      bool Search(const K& k, E& e) const;
      TwoThree<E,K>& Insert(const E& e);
      TwoThree<E,K>& Delete(const K& k, E& e)
         {if (Delete(k, e, root)) {
             // root has become deficient
             Node23<E,K> *t = root;
             root = root->LChild;
             delete t;
             }
          return *this;
          }
      void Ascend() {InOutput(root);
                     cout << endl;}
      void PostOut() {PostOutput(root);
                      cout << endl;}
   private:
      Node23<E,K> *root;  // root node
      E Null;             // denotes null element
      void Erase(Node23<E,K> *t);
      ReturnPair23<E,K> Insert(Node23<E,K> *p, const E& e);
      bool FixLeftChild(Node23<E,K> *p);
      bool FixMiddleChild(Node23<E,K> *p);
      bool FixRightChild(Node23<E,K> *p);
      bool DeleteLargest(Node23<E,K> *p, E& e);
      bool Delete(const K& k, E& e, Node23<E,K> *p);
      void InOutput(Node23<E,K> *t);
      void PostOutput(Node23<E,K> *t);
};

template<class E, class K>
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;
           }
}

template<class E, class K>
bool TwoThree<E,K>::Search(const K& k, E &e) const
{// 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<E,K> *p = root;
   while (p) // 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;
}

template<class E, class K>
TwoThree<E,K>& TwoThree<E,K>::Insert(const E& e)
{// Insert e if not duplicate.
 // Throw BadInput exception if e is either Null or a duplicate.
   if (e == Null)  // cannot insert null element
      throw BadInput();

   // insert recursively
   ReturnPair23<E,K> r = Insert(root, e);

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

   return *this;
}

template<class E, class K>
ReturnPair23<E,K> TwoThree<E,K>::
                  Insert(Node23<E,K> *p, const E& e)
{// 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<E,K> r;
   if (p) // 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 BadInput();
      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<E,K> *q = new Node23<E,K>;
               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);
               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<E,K> *q = new Node23<E,K>;
                    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<E,K> *q = new Node23<E,K>;
                         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 BadInput();
   else {// p is empty
         // create a pair to insert in parent of p
         r.element = e;
         r.NodePtr = 0;
         return r;
         }
}
         

template<class E, class K>
bool TwoThree<E,K>::FixLeftChild(Node23<E,K> *p)
{// The left child of p has become
 // deficient.  Fix deficiency.  Return true iff