btree.cpp

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

 
template <class Record, int order>
void B_tree<Record, order>::print()
{
   recursive_print(root, 0);
}
 
template <class Record, int order>
B_tree<Record, order>::B_tree()
{
   root = NULL;
}
 
template <class Record, int order>
B_tree<Record, order>::~B_tree()
{
//   This needs to be written some time!
}
 
template <class Record, int order>
Error_code B_tree<Record, order>::search_tree(Record &target)
/* 
 
Post:
If there is an entry in the B-tree whose key matches that in target,
the parameter target is replaced by the corresponding Record from
the B-tree and a code of success is returned.  Otherwise
a code of not_present is returned.
Uses: recursive_search_tree
 
*/

{
   return recursive_search_tree(root, target);
}
 
template <class Record, int order>
Error_code B_tree<Record, order>::insert(const Record &new_entry)
/* 
 
Post: If the Key of new_entry is already in the B_tree,
      a code of duplicate_error is returned.
      Otherwise, a code of success is returned and the Record new_entry
      is inserted into the B-tree in such a way that the properties of a B-tree
      are preserved.
Uses: Methods of struct B_node and the auxiliary function push_down.
 
*/
{
   Record median;
   B_node<Record, order> *right_branch, *new_root;
   Error_code result = push_down(root, new_entry, median, right_branch);

   if (result == overflow) {  //  The whole tree grows in height.
                             //  Make a brand new root for the whole B-tree.
      new_root = new B_node<Record, order>;
      new_root->count = 1;
      new_root->data[0] = median;
      new_root->branch[0] = root;
      new_root->branch[1] = right_branch;
      root = new_root;
      result = success;
   }
   return result;
}
 
template <class Record, int order>
Error_code B_tree<Record, order>::remove(const Record &target)
/* 
 
Post: If a Record with Key matching that of target belongs to the
      B_tree, a code of success is returned and the corresponding node
      is removed from the B-tree.  Otherwise, a code of not_present
      is returned.
Uses: Function recursive_remove
 
*/

{
   Error_code result;
   result = recursive_remove(root, target);
   if (root != NULL && root->count == 0) {  //  root is now empty.
      B_node<Record, order> *old_root = root;
      root = root->branch[0];
      delete old_root;
   }
   return result;
}