#include <btree.h>

Collaboration diagram for BTree< K, V >:

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 BTree &	operator= (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...

V	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...

V	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...

BTreeNode *	copy (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

BTreeNode *	root

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

order The 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

other The 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

subroot A 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

subroot A 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

key	The 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

subroot	A reference of a pointer to the current BTreeNode.
key	The 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

key	The key to insert.
value	The 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

subroot	A reference of a pointer to the current BTreeNode.
pair	The DataPair to be inserted.
subroot	A reference of a pointer to the current BTreeNode.
pair	The 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

subroot A pointer to the current node being checked for validity.

Returns: true if the node's subtree is valid, false otherwise.

Parameters

subroot A 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

rhs	The 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

parent	The parent whose child we are trying to split.
child_idx	The index of the child in its parent's children vector.

Called if the child became too large.

Parameters

parent	The parent whose child we are trying to split.
child_idx	The index of the child in its parent's children vector.

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

Classes

Public Member Functions

Private Member Functions

Private Attributes

Detailed Description

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

Constructor & Destructor Documentation

◆ BTree() [1/3]

◆ BTree() [2/3]

◆ BTree() [3/3]

◆ ~BTree()

Member Function Documentation

◆ clear() [1/2]

◆ clear() [2/2]

◆ copy()

◆ find() [1/2]

◆ find() [2/2]

◆ insert() [1/2]

◆ insert() [2/2]

◆ is_valid() [1/2]

◆ is_valid() [2/2]

◆ operator=()

◆ split_child()

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