Skip to content

Commit 2320b46

Browse files
skamble2skamble2
authored
Add BTree implementation (#6248)
1 parent d23a0ec commit 2320b46

File tree

2 files changed

+417
-0
lines changed
  • src
    • main/java/com/thealgorithms/datastructures/trees
    • test/java/com/thealgorithms/datastructures/trees

2 files changed

+417
-0
lines changed

‎src/main/java/com/thealgorithms/datastructures/trees/BTree.java

Lines changed: 323 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,323 @@
1+
package com.thealgorithms.datastructures.trees;
2+
3+
import java.util.ArrayList;
4+
5+
/**
6+
* Implementation of a B-Tree, a self-balancing tree data structure that maintains sorted data
7+
* and allows searches, sequential access, insertions, and deletions in logarithmic time.
8+
*
9+
* B-Trees are generalizations of binary search trees in that a node can have more than two children.
10+
* They're widely used in databases and file systems.
11+
*
12+
* For more information: https://en.wikipedia.org/wiki/B-tree
13+
*/
14+
15+
public class BTree {
16+
static class BTreeNode {
17+
int[] keys;
18+
int t; // Minimum degree (defines range for number of keys)
19+
BTreeNode[] children;
20+
int n; // Current number of keys
21+
boolean leaf;
22+
23+
BTreeNode(int t, boolean leaf) {
24+
this.t = t;
25+
this.leaf = leaf;
26+
this.keys = new int[2 * t - 1];
27+
this.children = new BTreeNode[2 * t];
28+
this.n = 0;
29+
}
30+
31+
void traverse(ArrayList<Integer> result) {
32+
for (int i = 0; i < n; i++) {
33+
if (!leaf) {
34+
children[i].traverse(result);
35+
}
36+
result.add(keys[i]);
37+
}
38+
if (!leaf) {
39+
children[n].traverse(result);
40+
}
41+
}
42+
43+
BTreeNode search(int key) {
44+
int i = 0;
45+
while (i < n && key > keys[i]) {
46+
i++;
47+
}
48+
if (i < n && keys[i] == key) {
49+
return this;
50+
}
51+
if (leaf) {
52+
return null;
53+
}
54+
return children[i].search(key);
55+
}
56+
57+
void insertNonFull(int key) {
58+
int i = n - 1;
59+
if (leaf) {
60+
while (i >= 0 && keys[i] > key) {
61+
keys[i + 1] = keys[i];
62+
i--;
63+
}
64+
keys[i + 1] = key;
65+
n++;
66+
} else {
67+
while (i >= 0 && keys[i] > key) {
68+
i--;
69+
}
70+
if (children[i + 1].n == 2 * t - 1) {
71+
splitChild(i + 1, children[i + 1]);
72+
if (keys[i + 1] < key) {
73+
i++;
74+
}
75+
}
76+
children[i + 1].insertNonFull(key);
77+
}
78+
}
79+
80+
void splitChild(int i, BTreeNode y) {
81+
BTreeNode z = new BTreeNode(y.t, y.leaf);
82+
z.n = t - 1;
83+
84+
System.arraycopy(y.keys, t, z.keys, 0, t - 1);
85+
if (!y.leaf) {
86+
System.arraycopy(y.children, t, z.children, 0, t);
87+
}
88+
y.n = t - 1;
89+
90+
for (int j = n; j >= i + 1; j--) {
91+
children[j + 1] = children[j];
92+
}
93+
children[i + 1] = z;
94+
95+
for (int j = n - 1; j >= i; j--) {
96+
keys[j + 1] = keys[j];
97+
}
98+
keys[i] = y.keys[t - 1];
99+
n++;
100+
}
101+
102+
void remove(int key) {
103+
int idx = findKey(key);
104+
105+
if (idx < n && keys[idx] == key) {
106+
if (leaf) {
107+
removeFromLeaf(idx);
108+
} else {
109+
removeFromNonLeaf(idx);
110+
}
111+
} else {
112+
if (leaf) {
113+
return; // Key not found
114+
}
115+
116+
boolean flag = idx == n;
117+
if (children[idx].n < t) {
118+
fill(idx);
119+
}
120+
121+
if (flag && idx > n) {
122+
children[idx - 1].remove(key);
123+
} else {
124+
children[idx].remove(key);
125+
}
126+
}
127+
}
128+
129+
private int findKey(int key) {
130+
int idx = 0;
131+
while (idx < n && keys[idx] < key) {
132+
++idx;
133+
}
134+
return idx;
135+
}
136+
137+
private void removeFromLeaf(int idx) {
138+
for (int i = idx + 1; i < n; ++i) {
139+
keys[i - 1] = keys[i];
140+
}
141+
n--;
142+
}
143+
144+
private void removeFromNonLeaf(int idx) {
145+
int key = keys[idx];
146+
if (children[idx].n >= t) {
147+
int pred = getPredecessor(idx);
148+
keys[idx] = pred;
149+
children[idx].remove(pred);
150+
} else if (children[idx + 1].n >= t) {
151+
int succ = getSuccessor(idx);
152+
keys[idx] = succ;
153+
children[idx + 1].remove(succ);
154+
} else {
155+
merge(idx);
156+
children[idx].remove(key);
157+
}
158+
}
159+
160+
private int getPredecessor(int idx) {
161+
BTreeNode cur = children[idx];
162+
while (!cur.leaf) {
163+
cur = cur.children[cur.n];
164+
}
165+
return cur.keys[cur.n - 1];
166+
}
167+
168+
private int getSuccessor(int idx) {
169+
BTreeNode cur = children[idx + 1];
170+
while (!cur.leaf) {
171+
cur = cur.children[0];
172+
}
173+
return cur.keys[0];
174+
}
175+
176+
private void fill(int idx) {
177+
if (idx != 0 && children[idx - 1].n >= t) {
178+
borrowFromPrev(idx);
179+
} else if (idx != n && children[idx + 1].n >= t) {
180+
borrowFromNext(idx);
181+
} else {
182+
if (idx != n) {
183+
merge(idx);
184+
} else {
185+
merge(idx - 1);
186+
}
187+
}
188+
}
189+
190+
private void borrowFromPrev(int idx) {
191+
BTreeNode child = children[idx];
192+
BTreeNode sibling = children[idx - 1];
193+
194+
for (int i = child.n - 1; i >= 0; --i) {
195+
child.keys[i + 1] = child.keys[i];
196+
}
197+
198+
if (!child.leaf) {
199+
for (int i = child.n; i >= 0; --i) {
200+
child.children[i + 1] = child.children[i];
201+
}
202+
}
203+
204+
child.keys[0] = keys[idx - 1];
205+
206+
if (!child.leaf) {
207+
child.children[0] = sibling.children[sibling.n];
208+
}
209+
210+
keys[idx - 1] = sibling.keys[sibling.n - 1];
211+
212+
child.n += 1;
213+
sibling.n -= 1;
214+
}
215+
216+
private void borrowFromNext(int idx) {
217+
BTreeNode child = children[idx];
218+
BTreeNode sibling = children[idx + 1];
219+
220+
child.keys[child.n] = keys[idx];
221+
222+
if (!child.leaf) {
223+
child.children[child.n + 1] = sibling.children[0];
224+
}
225+
226+
keys[idx] = sibling.keys[0];
227+
228+
for (int i = 1; i < sibling.n; ++i) {
229+
sibling.keys[i - 1] = sibling.keys[i];
230+
}
231+
232+
if (!sibling.leaf) {
233+
for (int i = 1; i <= sibling.n; ++i) {
234+
sibling.children[i - 1] = sibling.children[i];
235+
}
236+
}
237+
238+
child.n += 1;
239+
sibling.n -= 1;
240+
}
241+
242+
private void merge(int idx) {
243+
BTreeNode child = children[idx];
244+
BTreeNode sibling = children[idx + 1];
245+
246+
child.keys[t - 1] = keys[idx];
247+
248+
for (int i = 0; i < sibling.n; ++i) {
249+
child.keys[i + t] = sibling.keys[i];
250+
}
251+
252+
if (!child.leaf) {
253+
for (int i = 0; i <= sibling.n; ++i) {
254+
child.children[i + t] = sibling.children[i];
255+
}
256+
}
257+
258+
for (int i = idx + 1; i < n; ++i) {
259+
keys[i - 1] = keys[i];
260+
}
261+
262+
for (int i = idx + 2; i <= n; ++i) {
263+
children[i - 1] = children[i];
264+
}
265+
266+
child.n += sibling.n + 1;
267+
n--;
268+
}
269+
}
270+
271+
private BTreeNode root;
272+
private final int t;
273+
274+
public BTree(int t) {
275+
this.root = null;
276+
this.t = t;
277+
}
278+
279+
public void traverse(ArrayList<Integer> result) {
280+
if (root != null) {
281+
root.traverse(result);
282+
}
283+
}
284+
285+
public boolean search(int key) {
286+
return root != null && root.search(key) != null;
287+
}
288+
289+
public void insert(int key) {
290+
if (search(key)) {
291+
return;
292+
}
293+
if (root == null) {
294+
root = new BTreeNode(t, true);
295+
root.keys[0] = key;
296+
root.n = 1;
297+
} else {
298+
if (root.n == 2 * t - 1) {
299+
BTreeNode s = new BTreeNode(t, false);
300+
s.children[0] = root;
301+
s.splitChild(0, root);
302+
int i = 0;
303+
if (s.keys[0] < key) {
304+
i++;
305+
}
306+
s.children[i].insertNonFull(key);
307+
root = s;
308+
} else {
309+
root.insertNonFull(key);
310+
}
311+
}
312+
}
313+
314+
public void delete(int key) {
315+
if (root == null) {
316+
return;
317+
}
318+
root.remove(key);
319+
if (root.n == 0) {
320+
root = root.leaf ? null : root.children[0];
321+
}
322+
}
323+
}

0 commit comments

Comments
 (0)