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

• One pointer to a B_tree_node<Type> object, referred to as the root.

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.