11.cpp

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

Error_code B_tree<Record, order>::recursive_remove(
   B_node<Record, order> *current, const Record &target)
/*
Pre:  current is either NULL or
      points to the root node of a subtree of a B_tree.
Post: If a Record with Key matching that of target belongs to the subtree,
      a code of success is returned and the corresponding node is removed
      from the subtree so that the properties of a B-tree are maintained.
      Otherwise, a code of not_present is returned.
Uses: Functions search_node, copy_in_predecessor,
      recursive_remove (recursively), remove_data, and restore.
*/
{
   Error_code result;
   int position;
   if (current == NULL) result = not_present;
   else {
      if (search_node(current, target, position) == success) {  //  The target is in the current node.
         result = success;
         if (current->branch[position] != NULL) {     //  not at a leaf node
            copy_in_predecessor(current, position);

            recursive_remove(current->branch[position],
                             current->data[position]);
         }
         else remove_data(current, position);     //  Remove from a leaf node.
      }
      else result = recursive_remove(current->branch[position], target);
      if (current->branch[position] != NULL)
         if (current->branch[position]->count < (order - 1) / 2)
            restore(current, position);
   }
   return result;
}


template <class Record, int order>
void B_tree<Record, order>::remove_data(B_node<Record, order> *current,
                                        int position)
/*
Pre:  current points to a leaf node in a B-tree with an entry at position.
Post: This entry is removed from *current.
*/
{
   for (int i = position; i < current->count - 1; i++)
      current->data[i] = current->data[i + 1];
   current->count--;
}


template <class Record, int order>
void B_tree<Record, order>::copy_in_predecessor(
                    B_node<Record, order> *current, int position)
/*
Pre:  current points to a non-leaf node in a B-tree with an entry at position.
Post: This entry is replaced by its immediate predecessor under order of keys.
*/
{
   B_node<Record, order> *leaf = current->branch[position];  //   First go left from the current entry.
   while (leaf->branch[leaf->count] != NULL)
      leaf = leaf->branch[leaf->count]; //   Move as far rightward as possible.
   current->data[position] = leaf->data[leaf->count - 1];
}


template <class Record, int order>
void B_tree<Record, order>::restore(B_node<Record, order> *current,
                                    int position)
/*
Pre:  current points to a non-leaf node in a B-tree; the node to which
      current->branch[position] points has one too few entries.
Post: An entry is taken from elsewhere to restore the minimum number of
      entries in the node to which current->branch[position] points.
Uses: move_left, move_right, combine.
*/
{
   if (position == current->count)   //  case:  rightmost branch
      if (current->branch[position - 1]->count > (order - 1) / 2)
         move_right(current, position - 1);
      else
         combine(current, position);
   else if (position == 0)       //  case: leftmost branch
      if (current->branch[1]->count > (order - 1) / 2)
         move_left(current, 1);
      else
         combine(current, 1);
   else                          //  remaining cases: intermediate branches
      if (current->branch[position - 1]->count > (order - 1) / 2)
         move_right(current, position - 1);
      else if (current->branch[position + 1]->count > (order - 1) / 2)
         move_left(current, position + 1);
      else
         combine(current, position);
}


template <class Record, int order>
void B_tree<Record, order>::move_left(B_node<Record, order> *current,
                                      int position)
/*
Pre:  current points to a node in a B-tree with more than the minimum
      number of entries in branch position and one too few entries in branch
      position - 1.
Post: The leftmost entry from branch position has moved into
      current, which has sent an entry into the branch position - 1.
*/
{
   B_node<Record, order> *left_branch = current->branch[position - 1],
                         *right_branch = current->branch[position];
   left_branch->data[left_branch->count] = current->data[position - 1];  //  Take entry from the parent.
   left_branch->branch[++left_branch->count] = right_branch->branch[0];
   current->data[position - 1] = right_branch->data[0];  //   Add the right-hand entry to the parent.
   right_branch->count--;
   for (int i = 0; i < right_branch->count; i++) {   //  Move right-hand entries to fill the hole.
      right_branch->data[i] = right_branch->data[i + 1];
      right_branch->branch[i] = right_branch->branch[i + 1];
   }
   right_branch->branch[right_branch->count] =
      right_branch->branch[right_branch->count + 1];
}


template <class Record, int order>
void B_tree<Record, order>::move_right(B_node<Record, order> *current,
                                       int position)
/*
Pre:  current points to a node in a B-tree with more than the minimum
      number of entries in branch position and one too few entries
      in branch position + 1.
Post: The rightmost entry from branch position has moved into
      current, which has sent an entry into the branch position + 1.
*/
{
   B_node<Record, order> *right_branch = current->branch[position + 1],
                         *left_branch = current->branch[position];
   right_branch->branch[right_branch->count + 1] =
      right_branch->branch[right_branch->count];
   for (int i = right_branch->count ; i > 0; i--) {  //  Make room for new entry.
      right_branch->data[i] = right_branch->data[i - 1];
      right_branch->branch[i] = right_branch->branch[i - 1];
   }
   right_branch->count++;
   right_branch->data[0] = current->data[position]; //  Take entry from parent.
   right_branch->branch[0] = left_branch->branch[left_branch->count--];
   current->data[position] = left_branch->data[left_branch->count];
}


template <class Record, int order>
void B_tree<Record, order>::combine(B_node<Record, order> *current,
                                    int position)
/*
Pre:  current points to a node in a B-tree with entries in the branches
      position and position - 1, with too few to move entries.
Post: The nodes at branches position - 1 and position have been combined
      into one node, which also includes the entry formerly in current at
      index  position - 1.
*/
{
   int i;
   B_node<Record, order> *left_branch = current->branch[position - 1],
                         *right_branch = current->branch[position];
   left_branch->data[left_branch->count] = current->data[position - 1];
   left_branch->branch[++left_branch->count] = right_branch->branch[0];
   for (i = 0; i < right_branch->count; i++) {
      left_branch->data[left_branch->count] = right_branch->data[i];
      left_branch->branch[++left_branch->count] =
                                        right_branch->branch[i + 1];
   }
   current->count--;
   for (i = position - 1; i < current->count; i++) {
      current->data[i] = current->data[i + 1];
      current->branch[i + 1] = current->branch[i + 2];
   }
   delete right_branch;
}




// Section 11.4:

enum Color {red, black};

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


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>
class RB_tree: public Search_tree<Record> {
public:
   Error_code insert(const Record & new_entry);
private:  //  Add prototypes for auxiliary functions here.
};


enum RB_code {okay, red_node, left_red, right_red, duplicate};
/*  These outcomes from a call to the recursive insertion function describe
the following results:

okay:      The color of the current root (of the subtree) has not changed;
           the tree now satisfies the conditions for a red-black tree.

red_node:  The current root has changed from black to red; modification
           may or may not be needed to restore the red-black properties.

right_red: The current root and its right child are now both red;
           a color flip or rotation is needed.

left_red:  The current root and its left child are now both red;
           a color flip or rotation is needed.

duplicate: The entry being inserted duplicates another entry; this is
           an error.
*/


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

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