[an error occurred while processing this directive] [an error occurred while processing this directive]

B-Trees

Requirements

In this sub-project, you will implement two classes:

  1. A B+-Tree: Tree, and
  2. A B+-Tree Node: B_tree_node.

Class Specification

UML Class Diagram

B_tree
- tree_root:B_tree_node
+ create():B_tree
+ size():Integer
+ empty():Boolean
+ root():B_tree_node
+ count( in obj:Type ):Integer
+ insert( in obj:Type )
+ destroy()


Description

This class stores a finite ordered set of n (zero or more) elements stored in B+-tree nodes. If there are zero elements in the tree, the tree is said to be empty. Each element is stored in an instance of the B_tree_node<Type> class. By default, an empty B+-tree has a single empty B+-tree node, the address of which is stored in tree_root. Unlike the singly-linked list class, the B+-tree class, for the most part, simply makes the appropriate function call.

Member Variables

The one class variable is

Member Functions

Constructors

B_tree()

This constructor creates an empty B_tree_node<Type> and assigns this to the member variable tree_root.

Destructor

The destructor must delete all the nodes in the B+-tree in some manner.

Copy Constructor

There is no copy constructor in this class.

Assignment Operator =

There is no assignment operator in this class.

Accessors

This class has four accessors:

int size() const;
Returns the number of items in the tree.
bool empty() const;
Returns true if the tree is empty, false otherwise. (O(1))
B_tree_node<Type> *root() const;
Returns the root pointer. (O(1))
int count( Type const & ) const;
Returns 1 if the argument is stored by one of the nodes in the B+-tree and 0 otherwise.

Mutators

This class has one mutator:

void insert( Type const & );
Passes the argument to the root B+-tree node. If the insert member function of the B+-tree node returns a non-zero pointer, this indicates that the root must split, in which case a new root node is created with the root node as the first sub-tree and the returned pointer as the second sub-tree. You will note that there is a specific B+-tree node constructor to do this.
[an error occurred while processing this directive]