forked from TheAlgorithms/Rust
-
Notifications
You must be signed in to change notification settings - Fork 0
/
b_tree.rs
188 lines (168 loc) · 5.68 KB
/
b_tree.rs
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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
use std::convert::TryFrom;
use std::fmt::Debug;
use std::mem;
struct Node<T> {
keys: Vec<T>,
children: Vec<Node<T>>,
}
pub struct BTree<T> {
root: Node<T>,
props: BTreeProps,
}
// Why to need a different Struct for props...
// Check - http://smallcultfollowing.com/babysteps/blog/2018/11/01/after-nll-interprocedural-conflicts/#fnref:improvement
struct BTreeProps {
degree: usize,
max_keys: usize,
mid_key_index: usize,
}
impl<T> Node<T>
where
T: Ord,
{
fn new(degree: usize, _keys: Option<Vec<T>>, _children: Option<Vec<Node<T>>>) -> Self {
Node {
keys: match _keys {
Some(_keys) => _keys,
None => Vec::with_capacity(degree - 1),
},
children: match _children {
Some(_children) => _children,
None => Vec::with_capacity(degree),
},
}
}
fn is_leaf(&self) -> bool {
self.children.is_empty()
}
}
impl BTreeProps {
fn new(degree: usize) -> Self {
BTreeProps {
degree,
max_keys: degree - 1,
mid_key_index: (degree - 1) / 2,
}
}
fn is_maxed_out<T: Ord + Copy>(&self, node: &Node<T>) -> bool {
node.keys.len() == self.max_keys
}
// Split Child expects the Child Node to be full
/// Move the middle_key to parent node and split the child_node's
/// keys/chilren_nodes into half
fn split_child<T: Ord + Copy + Default>(&self, parent: &mut Node<T>, child_index: usize) {
let child = &mut parent.children[child_index];
let middle_key = child.keys[self.mid_key_index];
let right_keys = match child.keys.split_off(self.mid_key_index).split_first() {
Some((_first, _others)) => {
// We don't need _first, as it will move to parent node.
_others.to_vec()
}
None => Vec::with_capacity(self.max_keys),
};
let right_children = if !child.is_leaf() {
Some(child.children.split_off(self.mid_key_index + 1))
} else {
None
};
let new_child_node: Node<T> = Node::new(self.degree, Some(right_keys), right_children);
parent.keys.insert(child_index, middle_key);
parent.children.insert(child_index + 1, new_child_node);
}
fn insert_non_full<T: Ord + Copy + Default>(&mut self, node: &mut Node<T>, key: T) {
let mut index: isize = isize::try_from(node.keys.len()).ok().unwrap() - 1;
while index >= 0 && node.keys[index as usize] >= key {
index -= 1;
}
let mut u_index: usize = usize::try_from(index + 1).ok().unwrap();
if node.is_leaf() {
// Just insert it, as we know this method will be called only when node is not full
node.keys.insert(u_index, key);
} else {
if self.is_maxed_out(&node.children[u_index]) {
self.split_child(node, u_index);
if node.keys[u_index] < key {
u_index += 1;
}
}
self.insert_non_full(&mut node.children[u_index], key);
}
}
fn traverse_node<T: Ord + Debug>(&self, node: &Node<T>, depth: usize) {
if node.is_leaf() {
print!(" {0:{<1$}{2:?}{0:}<1$} ", "", depth, node.keys);
} else {
let _depth = depth + 1;
for (index, key) in node.keys.iter().enumerate() {
self.traverse_node(&node.children[index], _depth);
// Check https://doc.rust-lang.org/std/fmt/index.html
// And https://stackoverflow.com/a/35280799/2849127
print!("{0:{<1$}{2:?}{0:}<1$}", "", depth, key);
}
self.traverse_node(node.children.last().unwrap(), _depth);
}
}
}
impl<T> BTree<T>
where
T: Ord + Copy + Debug + Default,
{
pub fn new(branch_factor: usize) -> Self {
let degree = 2 * branch_factor;
BTree {
root: Node::new(degree, None, None),
props: BTreeProps::new(degree),
}
}
pub fn insert(&mut self, key: T) {
if self.props.is_maxed_out(&self.root) {
// Create an empty root and split the old root...
let mut new_root = Node::new(self.props.degree, None, None);
mem::swap(&mut new_root, &mut self.root);
self.root.children.insert(0, new_root);
self.props.split_child(&mut self.root, 0);
}
self.props.insert_non_full(&mut self.root, key);
}
pub fn traverse(&self) {
self.props.traverse_node(&self.root, 0);
println!();
}
pub fn search(&self, key: T) -> bool {
let mut current_node = &self.root;
let mut index: isize;
loop {
index = isize::try_from(current_node.keys.len()).ok().unwrap() - 1;
while index >= 0 && current_node.keys[index as usize] > key {
index -= 1;
}
let u_index: usize = usize::try_from(index + 1).ok().unwrap();
if index >= 0 && current_node.keys[u_index - 1] == key {
break true;
} else if current_node.is_leaf() {
break false;
} else {
current_node = ¤t_node.children[u_index];
}
}
}
}
#[cfg(test)]
mod test {
use super::BTree;
#[test]
fn test_search() {
let mut tree = BTree::new(2);
tree.insert(10);
tree.insert(20);
tree.insert(30);
tree.insert(5);
tree.insert(6);
tree.insert(7);
tree.insert(11);
tree.insert(12);
tree.insert(15);
assert!(tree.search(15));
assert_eq!(tree.search(16), false);
}
}