10.cpp

《数据结构与程序设计》书本所有源代码！！！！

void Buildable_tree<Record>::connect_trees(
                             const List<Binary_node<Record>*> &last_node)
/*
Pre:  The nearly-completed binary search tree has been initialized.  The List
      last_node has been initialized and contains links to the last node
      on each level of the tree.
Post: The final links have been added to complete the binary search tree.
Uses: Methods of class List
*/
{
   Binary_node<Record> *high_node, //  from last_node with NULL right child
                       *low_node;  //  candidate for right child of high_node
   int high_level = last_node.size() - 1,
       low_level;
   while (high_level > 2) {       //  Nodes on levels 1 and 2 are already OK.
      last_node.retrieve(high_level, high_node);
      if (high_node->right != NULL)
         high_level--;            //  Search down for highest dangling node.
      else {                      //  Case: undefined right tree
         low_level = high_level;
         do {               //  Find the highest entry not in the left subtree.
            last_node.retrieve(--low_level, low_node);
         } while (low_node != NULL && low_node->data < high_node->data);
         high_node->right = low_node;
         high_level = low_level;
      }
   }
}




// Section 10.4:

enum Balance_factor { left_higher, equal_height, right_higher };


template <class Record>
struct AVL_node: public Binary_node<Record> {
//    additional data member:
   Balance_factor balance;
//    constructors:
   AVL_node();
   AVL_node(const Record &x);
//    overridden virtual functions:
   void set_balance(Balance_factor b);
   Balance_factor get_balance() const;
};


template <class Record>
void AVL_node<Record>::set_balance(Balance_factor b)
{
   balance = b;
}

template <class Record>
Balance_factor AVL_node<Record>::get_balance() const
{
   return balance;
}


template <class Entry>
struct Binary_node {
//    data members:
   Entry data;
   Binary_node<Entry> *left;
   Binary_node<Entry> *right;
//    constructors:
   Binary_node();
   Binary_node(const Entry &x);

//    virtual methods:
   virtual void set_balance(Balance_factor b);
   virtual Balance_factor get_balance() const;

};


template <class Entry>
void Binary_node<Entry>::set_balance(Balance_factor b)
{
}

template <class Entry>
Balance_factor Binary_node<Entry>::get_balance() const
{
   return equal_height;
}


template <class Record>
class AVL_tree: public Search_tree<Record> {
public:
   Error_code insert(const Record &new_data);
   Error_code remove(const Record &old_data);
 private: //  Add auxiliary function prototypes here.
};


template <class Record>
Error_code AVL_tree<Record>::insert(const Record &new_data)
/*
Post: If the key of new_data is already in the AVL_tree, a code
      of duplicate_error is returned.
      Otherwise, a code of success is returned and the Record new_data
      is inserted into the tree in such a way that the properties of
      an AVL tree are preserved.
Uses: avl_insert.
*/
{
   bool taller;
   return avl_insert(root, new_data, taller);
}


template <class Record>
Error_code AVL_tree<Record>::avl_insert(Binary_node<Record> *&sub_root,
           const Record &new_data, bool &taller)
/*
Pre:  sub_root is either NULL or points to a subtree of the AVL_tree
Post: If the key of new_data is already in the subtree, a
      code of duplicate_error is returned.
      Otherwise, a code of success is returned and the Record new_data
      is inserted into the subtree in such a way that the
      properties of an AVL tree have been preserved.
      If the subtree is increased in height, the parameter taller is set to
      true; otherwise it is set to false.
Uses: Methods of struct AVL_node; functions avl_insert
      recursively, left_balance, and right_balance.
*/
{
   Error_code result = success;
   if (sub_root == NULL) {
      sub_root = new AVL_node<Record>(new_data);
      taller = true;
   }
   else if (new_data == sub_root->data) {
      result = duplicate_error;
      taller = false;
   }
   else if (new_data < sub_root->data) {         //  Insert in left subtree.
      result = avl_insert(sub_root->left, new_data, taller);
      if (taller == true)
         switch (sub_root->get_balance()) {//  Change balance factors.
         case left_higher:
            left_balance(sub_root);
            taller = false;        //  Rebalancing always shortens the tree.
            break;
         case equal_height:
            sub_root->set_balance(left_higher);
            break;
         case right_higher:
            sub_root->set_balance(equal_height);
            taller = false;
            break;
         }
   }
   else {                                       //  Insert in right subtree.
      result = avl_insert(sub_root->right, new_data, taller);
      if (taller == true)
         switch (sub_root->get_balance()) {
         case left_higher:
            sub_root->set_balance(equal_height);
            taller = false;
            break;
         case equal_height:
            sub_root->set_balance(right_higher);
            break;
         case right_higher:
            right_balance(sub_root);
            taller = false;        //  Rebalancing always shortens the tree.
            break;
         }
   }
   return result;
}


template <class Record>
void AVL_tree<Record>::rotate_left(Binary_node<Record> *&sub_root)
/*
Pre:  sub_root points to a subtree of the AVL_tree.
      This subtree has a nonempty right subtree.
Post: sub_root is reset to point to its former right child, and the former
      sub_root node is the left child of the new sub_root node.
*/
{
   if (sub_root == NULL || sub_root->right == NULL)     //  impossible cases
      cout << "WARNING: program error detected in rotate_left" << endl;
   else {
      Binary_node<Record> *right_tree = sub_root->right;
      sub_root->right = right_tree->left;
      right_tree->left = sub_root;
      sub_root = right_tree;
   }
}


template <class Record>
void AVL_tree<Record>::right_balance(Binary_node<Record> *&sub_root)
/*
Pre:  sub_root points to a subtree of an AVL_tree that
      is doubly unbalanced on the right.
Post: The AVL properties have been restored to the subtree.
Uses: Methods of struct AVL_node;
      functions  rotate_right and rotate_left.
*/
{
   Binary_node<Record> *&right_tree = sub_root->right;
   switch (right_tree->get_balance()) {
   case right_higher:                            //  single rotation left
      sub_root->set_balance(equal_height);
      right_tree->set_balance(equal_height);
      rotate_left(sub_root);
      break;
   case equal_height:  //  impossible case
      cout << "WARNING: program error detected in right_balance" << endl;
   case left_higher:                            //  double rotation left
      Binary_node<Record> *sub_tree = right_tree->left;
      switch (sub_tree->get_balance()) {
      case equal_height:
         sub_root->set_balance(equal_height);
         right_tree->set_balance(equal_height);
         break;
      case left_higher:
         sub_root->set_balance(equal_height);
         right_tree->set_balance(right_higher);
         break;
      case right_higher:
         sub_root->set_balance(left_higher);
         right_tree->set_balance(equal_height);
         break;
      }
      sub_tree->set_balance(equal_height);
      rotate_right(right_tree);
      rotate_left(sub_root);
      break;
   }
}




// Section 10.5:

template <class Record>
class Splay_tree:public Search_tree<Record> {
public:
   Error_code splay(const Record &target);
 private: //  Add auxiliary function prototypes here.
};


template <class Record>
void Splay_tree<Record>::link_right(Binary_node<Record> *&current,
                                    Binary_node<Record> *&first_large)
/*
Pre:  The pointer first_large points to an actual Binary_node
      (in particular, it is not NULL).  The three-way invariant holds.
Post: The node referenced by current (with its right subtree) is linked
      to the left of the node referenced by first_large.
      The pointer first_large is reset to current.
      The three-way invariant continues to hold.
*/
{
   first_large->left = current;
   first_large = current;
   current = current->left;
}


template <class Record>
void Splay_tree<Record>::link_left(Binary_node<Record> *&current,
                                   Binary_node<Record> *&last_small)
/*
Pre:  The pointer last_small points to an actual Binary_node
      (in particular, it is not NULL).  The three-way invariant holds.
Post: The node referenced by current (with its left subtree) is linked
      to the right of the node referenced by last_small.
      The pointer last_small is reset to current.
      The three-way invariant continues to hold.
*/
{
   last_small->right = current;
   last_small = current;
   current = current->right;
}


template <class Record>
void Splay_tree<Record>::rotate_right(Binary_node<Record> *&current)
/*
Pre:  current points to the root node of a subtree of a Binary_tree.
      This subtree has a nonempty left subtree.
Post: current is reset to point to its former left child, and the former
      current node is the right child of the new current node.
*/
{
   Binary_node<Record> *left_tree = current->left;
   current->left = left_tree->right;
   left_tree->right = current;
   current = left_tree;
}


template <class Record>
void Splay_tree<Record>::rotate_left(Binary_node<Record> *&current)
/*
Pre:  current points to the root node of a subtree of a Binary_tree.
      This subtree has a nonempty right subtree.
Post: current is reset to point to its former right child, and the former
      current node is the left child of the new current node.
*/
{
   Binary_node<Record> *right_tree = current->right;
   current->right = right_tree->left;
   right_tree->left = current;
   current = right_tree;
}


template <class Record>
Error_code Splay_tree<Record>::splay(const Record &target)
/*
Post: If a node of the splay tree has a key matching that of target,
      it has been moved by splay operations to be the root of the
      tree, and a code of entry_found is returned.  Otherwise,
      a new node containing a copy of target is inserted as the root
      of the tree, and a code of entry_inserted is returned.
*/
{
   Binary_node<Record> *dummy = new Binary_node<Record>;
   Binary_node<Record> *current = root,
                       *child,
                       *last_small = dummy,
                       *first_large = dummy;

 //  Search for target while splaying the tree.
   while (current != NULL && current->data != target)
      if (target < current->data) {
         child = current->left;
         if (child == NULL || target == child->data)    //  zig move
            link_right(current, first_large);
         else if (target < child->data) {           //  zig-zig move
            rotate_right(current);
            link_right(current, first_large);
         }
         else {                                     //  zig-zag move
            link_right(current, first_large);
            link_left(current, last_small);
         }
      }

      else {                              //  case: target > current->data
         child = current->right;
         if (child == NULL || target == child->data)
            link_left(current, last_small);             //  zag move
         else if (target > child->data) {           //  zag-zag move
            rotate_left(current);
            link_left(current, last_small);
         }
         else {                                     //  zag-zig move
            link_left(current, last_small);
            link_right(current, first_large);
         }
      }

 //  Move root to the current node, which is created if necessary.
   Error_code result;
   if (current == NULL) {        //  Search unsuccessful: make a new root.
      current = new Binary_node<Record>(target);
      result = entry_inserted;
      last_small->right = first_large->left = NULL;
   }

   else {                        //  successful search
      result = entry_found;
      last_small->right = current->left;  //   Move remaining central nodes.
      first_large->left = current->right;
   }

   root = current;               //  Define the new root.
   root->right = dummy->left;    //  root of larger-key subtree
   root->left = dummy->right;    //  root of smaller-key subtree
   delete dummy;
   return result;
}

/*************************************************************************/