lab_btree
Belligerent BTrees
|
#include "btree.h"
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... | |
BTree class.
Provides interfaces for inserting and finding elements in B-tree.
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.
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.
key | The key to insert. |
value | The value to insert. |
V BTree< K, V >::find | ( | const K & | key | ) | const |
Finds the value associated with a given key.
key | The key to look up. |
|
private |
Private recursive version of the insert function.
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. |
|
private |
Private recursive version of the find function.
subroot | A reference of a pointer to the current BTreeNode. |
key | The key we are looking up. |
|
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*).
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.
parent | The parent whose child we are trying to split. |
child_idx | The index of the child in its parent's children vector. |
Private recursive version of the clear function.
subroot | A pointer to the current node being cleared. |
|
private |
Private recursive version of the copy function.
subroot | A pointer to the current node being copied. |
|
private |
Private recursive version of the is_valid function.
subroot | A pointer to the current node being checked for validity. |
subroot | A pointer to the current node being checked for validity. |