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 describethe 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_treePost: 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;}/*************************************************************************/