lab_btree
Belligerent BTrees
BTree< K, V > Class Template Reference

BTree class. More...

#include <btree.h>

Collaboration diagram for BTree< K, V >:
[legend]

Classes

struct  BTreeNode
 A class for the basic node structure of the BTree. More...
 
struct  DataPair
 A fancy key-value pair which acts as elements in the BTree. More...
 

Public Member Functions

 BTree ()
 Constructs a default, order 64 BTree. More...
 
 BTree (unsigned int order)
 Constructs a BTree with the specified order. More...
 
 BTree (const BTree &other)
 Constructs a BTree as a deep copy of another. More...
 
bool is_valid (unsigned int order=64) const
 Performs checks to make sure the BTree is valid. More...
 
 ~BTree ()
 Destroys a BTree. More...
 
const BTreeoperator= (const BTree &rhs)
 Assignment operator for a BTree. More...
 
void clear ()
 Clears the BTree of all data. More...
 
void insert (const K &key, const V &value)
 Inserts a key and value into the BTree. More...
 
find (const K &key) const
 Finds the value associated with a given key. More...
 

Private Member Functions

void insert (BTreeNode *subroot, const DataPair &pair)
 Private recursive version of the insert function. More...
 
find (const BTreeNode *subroot, const K &key) const
 Private recursive version of the find function. More...
 
void split_child (BTreeNode *parent, size_t child_idx)
 Splits a child node of a BTreeNode. More...
 
void clear (BTreeNode *subroot)
 Private recursive version of the clear function. More...
 
BTreeNodecopy (const BTreeNode *subroot)
 Private recursive version of the copy function. More...
 
bool is_valid (const BTreeNode *subroot, std::vector< DataPair > &data, unsigned int order) const
 Private recursive version of the is_valid function. More...
 

Private Attributes

unsigned int order
 
BTreeNoderoot
 

Detailed Description

template<class K, class V>
class BTree< K, V >

BTree class.

Provides interfaces for inserting and finding elements in B-tree.

Author
Matt Joras
Date
Winter 2013

Constructor & Destructor Documentation

◆ BTree() [1/3]

template<class K , class V >
BTree< K, V >::BTree ( )

Constructs a default, order 64 BTree.

◆ BTree() [2/3]

template<class K , class V >
BTree< K, V >::BTree ( unsigned int  order)

Constructs a BTree with the specified order.

The minimum order allowed is order 3.

Parameters
orderThe order of the constructed BTree.

◆ BTree() [3/3]

template<class K , class V >
BTree< K, V >::BTree ( const BTree< K, V > &  other)

Constructs a BTree as a deep copy of another.

Parameters
otherThe BTree to copy.

◆ ~BTree()

template<class K , class V >
BTree< K, V >::~BTree ( )

Destroys a BTree.

Member Function Documentation

◆ clear() [1/2]

template<class K , class V >
void BTree< K, V >::clear ( )

Clears the BTree of all data.

◆ clear() [2/2]

template<class K , class V >
void BTree< K, V >::clear ( BTreeNode subroot)
private

Private recursive version of the clear function.

Parameters
subrootA pointer to the current node being cleared.

◆ copy()

template<class K , class V >
BTree< K, V >::BTreeNode * BTree< K, V >::copy ( const BTreeNode subroot)
private

Private recursive version of the copy function.

Parameters
subrootA pointer to the current node being copied.

◆ find() [1/2]

template<class K , class V >
V BTree< K, V >::find ( const K &  key) const

Finds the value associated with a given key.

Parameters
keyThe key to look up.
Returns
The value (if found), the default V if not.

◆ find() [2/2]

template<class K , class V >
V BTree< K, V >::find ( const BTreeNode subroot,
const K &  key 
) const
private

Private recursive version of the find function.

Parameters
subrootA reference of a pointer to the current BTreeNode.
keyThe key we are looking up.
Returns
The value (if found), the default V if not.

◆ insert() [1/2]

template<class K , class V >
void BTree< K, V >::insert ( const K &  key,
const V &  value 
)

Inserts a key and value into the BTree.

If the key is already in the tree do nothing.

Parameters
keyThe key to insert.
valueThe value to insert.

◆ insert() [2/2]

template<class K , class V >
void BTree< K, V >::insert ( BTreeNode subroot,
const DataPair pair 
)
private

Private recursive version of the insert function.

Parameters
subrootA reference of a pointer to the current BTreeNode.
pairThe DataPair to be inserted.
subrootA reference of a pointer to the current BTreeNode.
pairThe DataPair to be inserted. Note: Original solution used std::lower_bound, but making the students write an equivalent seemed more instructive.

◆ is_valid() [1/2]

template<class K , class V >
bool BTree< K, V >::is_valid ( unsigned int  order = 64) const

Performs checks to make sure the BTree is valid.

Specifically it will check to make sure that an in-order traversal of the tree will result in a sorted sequence of keys. Also verifies that each BTree node doesn't have more nodes than its order.

Returns
true if it satisfies the conditions, false otherwise.

◆ is_valid() [2/2]

template<class K , class V >
bool BTree< K, V >::is_valid ( const BTreeNode subroot,
std::vector< DataPair > &  data,
unsigned int  order 
) const
private

Private recursive version of the is_valid function.

Parameters
subrootA pointer to the current node being checked for validity.
Returns
true if the node's subtree is valid, false otherwise.
Parameters
subrootA pointer to the current node being checked for validity.
Returns
true if the node is a valid BTreeNode, false otherwise.

◆ operator=()

template<class K , class V >
const BTree< K, V > & BTree< K, V >::operator= ( const BTree< K, V > &  rhs)

Assignment operator for a BTree.

Parameters
rhsThe BTree to assign into this one.
Returns
The copied BTree.

◆ split_child()

template<class K , class V >
void BTree< K, V >::split_child ( BTreeNode parent,
size_t  child_idx 
)
private

Splits a child node of a BTreeNode.

Called if the child became too large. Modifies the parent such that children[child_idx] contains half as many elements as before, and similarly for children[child_idx + 1] (which is a new BTreeNode*).

Parameters
parentThe parent whose child we are trying to split.
child_idxThe index of the child in its parent's children vector.

Called if the child became too large.

Parameters
parentThe parent whose child we are trying to split.
child_idxThe index of the child in its parent's children vector.

The documentation for this class was generated from the following files: