splaytree.h

这是本人精心搜集的关于常用图论算法的一套源码

#include "bt.h"

template <class Record>
class Splay_tree:
public Binary_tree<Record>
{ public:
   Error_code splay(const Record &target); 
  private:        //  Add auxiliary function prototypes here.
   void link_left(Binary_node<Record> *&, Binary_node<Record> *&);
   void link_right(Binary_node<Record> *&, Binary_node<Record> *&);
   void rotate_left(Binary_node<Record> *&);
   void rotate_right(Binary_node<Record> *&); 
};

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