rbtree.txt

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

enum Color {red, black};
 
template <class Entry>
struct Binary_node {
   Entry data;
   Binary_node<Entry> *left;
   Binary_node<Entry> *right;
   virtual Color get_color() const { return red; }
   virtual void set_color(Color c) { }
   Binary_node()                   { left = right = NULL; }
   Binary_node(const Entry &x)     { data = x; left = right = NULL; }
};


template <class Record>
struct RB_node: public Binary_node<Record> {
   Color color;
   RB_node(const Record &new_entry) { color = red; data = new_entry;
                                     left = right = NULL; }
   RB_node()                { color = red; left = right = NULL; }
   void set_color(Color c)  { color = c; }
   Color get_color() const  { return color; }
};


enum RB_code {okay, red_node, left_red, right_red, duplicate};

template <class Record>
class RB_tree: public Search_tree<Record> {
public:
   Error_code insert(const Record & new_entry);
 
   void prenode(void (*visit)(Binary_node<Record> *&));
   RB_code rb_insert(Binary_node<Record> *&, const Record &);
   RB_code modify_left(Binary_node<Record> *&, RB_code &);
   RB_code modify_right(Binary_node<Record> *&, RB_code &);
   RB_code rotate_left(Binary_node<Record> *&current);
   RB_code rotate_right(Binary_node<Record> *&current);
   RB_code flip_color(Binary_node<Record> *current);
   RB_code double_rotate_right(Binary_node<Record> *&current);
   RB_code double_rotate_left(Binary_node<Record> *&current);
 
private:  //  Add prototypes for auxiliary functions here.
};

template <class Record>
Error_code RB_tree<Record>::insert(const Record &new_entry)
/* 
 
Post: If the key of new_entry is already in the RB_tree, a code of duplicate_error
      is returned.  Otherwise, a code of success is returned and the Record new_entry is
      inserted into the tree in such a way that the properties of an RB-tree
      have been preserved.
Uses: Methods of struct RB_node and recursive function rb_insert.
 
*/

{
   RB_code status = rb_insert(root, new_entry);
   switch (status) {   //  Convert private RB_code to public Error_code.
      case red_node:   //  Always split the root node to keep it black.
         root->set_color(black); 
                  /*  Doing so prevents two red nodes at the top
                  of the  tree and a resulting attempt to rotate
                  using a parent node that does not exist. */

      case okay:
         return success;

      case duplicate:
         return duplicate_error;

      case right_red:
      case left_red:
         cout << "WARNING: Program error detected in RB_tree::insert" << endl;
         return internal_error;
   }
}




template <class Record>
RB_code RB_tree<Record>::rb_insert(Binary_node<Record> *&current,
                                   const Record &new_entry)
/* 
 
Pre:  current is either NULL or points to the
      first node of a subtree of an RB_tree
Post: If the key of new_entry is already in the
      subtree, a code of duplicate
      is returned.  Otherwise, the Record new_entry is
      inserted into the subtree
      pointed to by current.  The properties of a red-black tree have been
      restored, except possibly at the root current and one of its children,
      whose status is given by the output RB_code.
Uses: Methods of class RB_node,
      rb_insert recursively, modify_left, and modify_right.
 
*/

{
 
   RB_code status,
           child_status;
   if (current == NULL) {
      current = new RB_node<Record>(new_entry);
      status = red_node;
   }
   else if (new_entry == current->data)
      return duplicate;
   else if (new_entry < current->data) {
      child_status = rb_insert(current->left, new_entry);
      status = modify_left(current, child_status);
   }
   else {
      child_status = rb_insert(current->right, new_entry);
      status = modify_right(current, child_status);
   }
   return status;
}
 
template <class Record>
RB_code RB_tree<Record>::modify_left(Binary_node<Record> *&current,
                                     RB_code &child_status)
/* 
 
Pre:   An insertion has been made in the left subtree of *current that
       has returned the value of child_status  for this subtree.
Post: Any color change or rotation needed for the tree rooted at current 
       has been made, and a status code is returned.
Uses: Methods of struct RB_node, with rotate_right,
      double_rotate_right, and flip_color.
 
*/

{
   RB_code status = okay;
   Binary_node<Record> *aunt = current->right;
   Color aunt_color = black;
   if (aunt != NULL) aunt_color = aunt->get_color();
   switch (child_status) {
   case okay:
      break;         //  No action needed, as tree is already OK.
   case red_node:
      if (current->get_color() == red)
         status = left_red;
      else
         status = okay;        //  current is black, left is red, so OK.
      break;
 
   case left_red:
      if (aunt_color == black) status = rotate_right(current);
      else                     status = flip_color(current);
      break;
   case right_red:
      if (aunt_color == black) status = double_rotate_right(current);
      else                     status = flip_color(current);
      break;
   }
   return status;
}
 
template <class Record>
RB_code RB_tree<Record>::modify_right(Binary_node<Record> *&current,
                                      RB_code &child_status)
{
   RB_code status = okay;
   Binary_node<Record> *left_child = current->left;

   switch (child_status) {
   case okay: break;
   case red_node:
      if (current->get_color() == red)
         status = right_red;
      else
         status = okay;
      break;

   case right_red:
      if (left_child == NULL)
         status = rotate_left(current);
      else if (left_child->get_color() == red)
         status = flip_color(current);
      else
         status = rotate_left(current);
      break;

   case left_red:
      if (left_child == NULL)
         status = double_rotate_left(current);
      else if (left_child->get_color() == red)
         status = flip_color(current);
      else
         status = double_rotate_left(current);
      break;
   }
   return status;
}
 
template <class Record>
RB_code RB_tree<Record>::rotate_left(Binary_node<Record> *&current)
/* 
 
Pre:  current points to a subtree of an RB_tree. The 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.
 
*/

{
   if (current == NULL || current->right == NULL)     //  impossible cases
      cout << "WARNING: program error in detected in rotate_left\n\n";
   else {
      Binary_node<Record> *right_tree = current->right;
      current->set_color(red);
      right_tree->set_color(black);
      current->right = right_tree->left;
      right_tree->left = current;
      current = right_tree;
   }
   return okay;
}
 
template <class Record>
RB_code RB_tree<Record>::rotate_right(Binary_node<Record> *&current)
{
   if (current == NULL || current->left == NULL) //  impossible cases
      cout << "WARNING: program error in detected in rotate_right\n\n";
   else {
      Binary_node<Record> *left_tree = current->left;
      current->set_color(red);
      left_tree->set_color(black);
      current->left = left_tree->right;
      left_tree->right = current;
      current = left_tree;
   }
   return okay;
}
 
template <class Record>
RB_code RB_tree<Record>::flip_color(Binary_node<Record> *current)
{
   Binary_node<Record> *left_child = current->left,
      *right_child = current->right;
   current->set_color(red);
   left_child->set_color(black);
   right_child->set_color(black);
   return red_node;
}
 
template <class Record>
RB_code RB_tree<Record>::double_rotate_right(Binary_node<Record> *&current)
{
   rotate_left(current->left);
   rotate_right(current);
   return okay;
}
 
template <class Record>
RB_code RB_tree<Record>::double_rotate_left(Binary_node<Record> *&current)
{
   rotate_right(current->right);
   rotate_left(current);
   return okay;
}