-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathb_tree.cpp
More file actions
118 lines (100 loc) · 3.4 KB
/
b_tree.cpp
File metadata and controls
118 lines (100 loc) · 3.4 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include "b_tree.h"
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<char> right_keys = std::vector<char>(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<Node*> right_children = std::vector<Node*>(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);
}
void BTree::Tree::InsertNonFull(Node* node, char key)
{
int key_count = static_cast<int>(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<int>(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);
}
}
void BTree::Tree::Insert(Node* node, char key)
{
Node* root_node = node;
if (static_cast<int>(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);
}
}
auto BTree::Tree::Search(Node* node, char key) -> std::pair<Node*, const int>
{
int index = 0;
int key_count = static_cast<int>(node->keys.size());
// find the smallest index that key <= node->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<Node*, const int>{};
}
// key is not found and recurse to search subtree of reference node
return Search(node->children[index], key);
}