rbtree.cpp

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

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>
void RB_tree<Record>::prenode(void (*f)(Binary_node<Record> *&))
{
   rb_prenode(root, f);
}
 
template <class Record>
void rb_prenode(Binary_node<Record> *current, void (*f)(Binary_node<Record> *&))
{
   if (current != NULL) {
      (*f)(current);
      rb_prenode(current->left, f);
      rb_prenode(current->right, f);
   }
}