GitHub Viewer
#ifndef CPP_ALGORITHM_B_TREE_H
#define CPP_ALGORITHM_B_TREE_H
#include
namespace BTree
{
struct Node
{
std::vector keys;
std::vector children;
bool is_leaf;
};
class Tree
{
public:
Node* root;
std::vector nodes;
int degree;
/**
* \brief Split the node
* \param node internal node
* \param index index
*/
void SplitChild(Node* node, int index);
/**
* \brief Insert key
* \param node internal node
* \param key key
*/
void InsertNonFull(Node* node, char key);
/**
* \brief Insert the key to the tree
* \param node reference node for insert
* \param key key to insert
*/
void Insert(Node* node, char key);
/**
* \brief Search the key
* \param node reference node for tree search
* \param key key to search for
* \return node and key index pair
*/
std::pair Search(Node* node, char key);
};
}
// ----------------------------------------------------------------------------
inline void BTree::Tree::SplitChild(Node* node, int index)
{
Node* left_child = node->children[index];
// create a right child node,
// and split keys, children of the left child node
// create right child
Node* right_child = new Node{};
right_child->is_leaf = left_child->is_leaf;
// split keys of the left child
// copy keys from median+1 to the end
std::vector right_keys =
std::vector(left_child->keys.begin() + degree, left_child->keys.end());
right_child->keys = std::move(right_keys);
// get median key
const char median_key = left_child->keys[degree - 1];
// erase keys from median to the end
left_child->keys.erase(left_child->keys.begin() + degree - 1, left_child->keys.end());
// split children of the left child
if (left_child->is_leaf == false)
{
std::vector right_children =
std::vector(left_child->children.begin() + degree, left_child->children.end());
right_child->children = std::move(right_children);
left_child->children.erase(left_child->children.begin() + degree, left_child->children.end());
}
// insert a new right node,
// and move the median key to the parent node
// move the median key to parent node
node->keys.insert(node->keys.begin() + index, median_key);
// insert right node as a new child of node
node->children.insert(node->children.begin() + index + 1, right_child);
}
// ----------------------------------------------------------------------------
inline void BTree::Tree::InsertNonFull(Node* node, char key)
{
int key_count = static_cast(node->keys.size());
// insert key to leaf node
if (node->is_leaf == true)
{
while ((key_count >= 1) && (node->keys[key_count - 1] > key))
{
--key_count;
}
node->keys.insert(node->keys.begin() + key_count, key);
}
else
{
while ((key_count >= 1) && (node->keys[key_count - 1] > key))
{
--key_count;
}
++key_count;
if (static_cast(node->children[key_count - 1]->keys.size()) == 2 * degree - 1)
{
SplitChild(node, key_count - 1);
if (key > node->keys[key_count - 1])
{
++key_count;
}
}
InsertNonFull(node->children[key_count - 1], key);
}
}
// ----------------------------------------------------------------------------
inline void BTree::Tree::Insert(Node* node, char key)
{
Node* root_node = node;
if (static_cast(node->keys.size()) == 2 * degree - 1)
{
Node* new_node = new Node{};
root = new_node;
new_node->is_leaf = false;
new_node->children.push_back(root_node);
SplitChild(new_node, 0);
InsertNonFull(new_node, key);
}
else
{
InsertNonFull(root_node, key);
}
}
// ----------------------------------------------------------------------------
inline std::pair BTree::Tree::Search(Node* node, char key)
{
int index = 0;
int key_count = static_cast(node->keys.size());
// find the smallest index that key Keys[index]
while ((key_count > index) && (key > node->keys[index]))
{
++index;
}
// check to see whether key is found
if ((key_count > index) && (key == node->keys[index]))
{
return std::make_pair(node, index);
}
// key is not found and if node is a leaf
if (node->is_leaf == true)
{
return std::pair{};
}
// key is not found and recurse to search subtree of reference node
return Search(node->children[index], key);
}
#endif