rbnode.cpp

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

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