splaynod.cpp

来自「数据结构与程序设计教材源码 数据结构与程序设计教材源码」· C++ 代码 · 共 146 行

 
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_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>
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>
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;
}