Skip to content

Btree implementation #6248

New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Merged
merged 10 commits into from
May 28, 2025
Merged

Btree implementation #6248

Show file tree
Hide file tree
Changes from all commits
Commits
Show all changes
10 commits
Select commit Hold shift + click to select a range
9b6c1a0
Btree implementation
skamble2 May 25, 2025
d1ff189
Fix Checkstyle violations in BTree and BTreeTest
skamble2 May 25, 2025
bad7a99
fix white space formatting errors
skamble2 May 25, 2025
43c1470
fix white space formatting errors
skamble2 May 25, 2025
0cd5d16
fixed whitespace errors
skamble2 May 25, 2025
9ad31af
import fix
skamble2 May 25, 2025
c3c3c0e
including description and edge test cases for inserting duplicate key…
skamble2 May 26, 2025
622d4a3
including description and edge test cases for inserting duplicate key…
skamble2 May 26, 2025
0988c61
updated code to handle duplicate keys
skamble2 May 26, 2025
84ff238
updated code to handle duplicate keys
skamble2 May 26, 2025
File filter

Filter by extension

Filter by extension
Conversations
Failed to load comments.
Loading
Jump to
Jump to file
Failed to load files.
Loading
Diff view
Diff view
323 changes: 323 additions & 0 deletions src/main/java/com/thealgorithms/datastructures/trees/BTree.java
View file
Open in desktop
Original file line number Diff line number Diff line change
@@ -0,0 +1,323 @@
package com.thealgorithms.datastructures.trees;

import java.util.ArrayList;

/**
* Implementation of a B-Tree, a self-balancing tree data structure that maintains sorted data
* and allows searches, sequential access, insertions, and deletions in logarithmic time.
*
* B-Trees are generalizations of binary search trees in that a node can have more than two children.
* They're widely used in databases and file systems.
*
* For more information: https://en.wikipedia.org/wiki/B-tree
*/

public class BTree {
static class BTreeNode {
int[] keys;
int t; // Minimum degree (defines range for number of keys)
BTreeNode[] children;
int n; // Current number of keys
boolean leaf;

BTreeNode(int t, boolean leaf) {
this.t = t;
this.leaf = leaf;
this.keys = new int[2 * t - 1];
this.children = new BTreeNode[2 * t];
this.n = 0;
}

void traverse(ArrayList<Integer> result) {
for (int i = 0; i < n; i++) {
if (!leaf) {
children[i].traverse(result);
}
result.add(keys[i]);
}
if (!leaf) {
children[n].traverse(result);
}
}

BTreeNode search(int key) {
int i = 0;
while (i < n && key > keys[i]) {
i++;
}
if (i < n && keys[i] == key) {
return this;
}
if (leaf) {
return null;
}
return children[i].search(key);
}

void insertNonFull(int key) {
int i = n - 1;
if (leaf) {
while (i >= 0 && keys[i] > key) {
keys[i + 1] = keys[i];
i--;
}
keys[i + 1] = key;
n++;
} else {
while (i >= 0 && keys[i] > key) {
i--;
}
if (children[i + 1].n == 2 * t - 1) {
splitChild(i + 1, children[i + 1]);
if (keys[i + 1] < key) {
i++;
}
}
children[i + 1].insertNonFull(key);
}
}

void splitChild(int i, BTreeNode y) {
BTreeNode z = new BTreeNode(y.t, y.leaf);
z.n = t - 1;

System.arraycopy(y.keys, t, z.keys, 0, t - 1);
if (!y.leaf) {
System.arraycopy(y.children, t, z.children, 0, t);
}
y.n = t - 1;

for (int j = n; j >= i + 1; j--) {
children[j + 1] = children[j];
}
children[i + 1] = z;

for (int j = n - 1; j >= i; j--) {
keys[j + 1] = keys[j];
}
keys[i] = y.keys[t - 1];
n++;
}

void remove(int key) {
int idx = findKey(key);

if (idx < n && keys[idx] == key) {
if (leaf) {
removeFromLeaf(idx);
} else {
removeFromNonLeaf(idx);
}
} else {
if (leaf) {
return; // Key not found
}

boolean flag = idx == n;
if (children[idx].n < t) {
fill(idx);
}

if (flag && idx > n) {
children[idx - 1].remove(key);
} else {
children[idx].remove(key);
}
}
}

private int findKey(int key) {
int idx = 0;
while (idx < n && keys[idx] < key) {
++idx;
}
return idx;
}

private void removeFromLeaf(int idx) {
for (int i = idx + 1; i < n; ++i) {
keys[i - 1] = keys[i];
}
n--;
}

private void removeFromNonLeaf(int idx) {
int key = keys[idx];
if (children[idx].n >= t) {
int pred = getPredecessor(idx);
keys[idx] = pred;
children[idx].remove(pred);
} else if (children[idx + 1].n >= t) {
int succ = getSuccessor(idx);
keys[idx] = succ;
children[idx + 1].remove(succ);
} else {
merge(idx);
children[idx].remove(key);
}
}

private int getPredecessor(int idx) {
BTreeNode cur = children[idx];
while (!cur.leaf) {
cur = cur.children[cur.n];
}
return cur.keys[cur.n - 1];
}

private int getSuccessor(int idx) {
BTreeNode cur = children[idx + 1];
while (!cur.leaf) {
cur = cur.children[0];
}
return cur.keys[0];
}

private void fill(int idx) {
if (idx != 0 && children[idx - 1].n >= t) {
borrowFromPrev(idx);
} else if (idx != n && children[idx + 1].n >= t) {
borrowFromNext(idx);
} else {
if (idx != n) {
merge(idx);
} else {
merge(idx - 1);
}
}
}

private void borrowFromPrev(int idx) {
BTreeNode child = children[idx];
BTreeNode sibling = children[idx - 1];

for (int i = child.n - 1; i >= 0; --i) {
child.keys[i + 1] = child.keys[i];
}

if (!child.leaf) {
for (int i = child.n; i >= 0; --i) {
child.children[i + 1] = child.children[i];
}
}

child.keys[0] = keys[idx - 1];

if (!child.leaf) {
child.children[0] = sibling.children[sibling.n];
}

keys[idx - 1] = sibling.keys[sibling.n - 1];

child.n += 1;
sibling.n -= 1;
}

private void borrowFromNext(int idx) {
BTreeNode child = children[idx];
BTreeNode sibling = children[idx + 1];

child.keys[child.n] = keys[idx];

if (!child.leaf) {
child.children[child.n + 1] = sibling.children[0];
}

keys[idx] = sibling.keys[0];

for (int i = 1; i < sibling.n; ++i) {
sibling.keys[i - 1] = sibling.keys[i];
}

if (!sibling.leaf) {
for (int i = 1; i <= sibling.n; ++i) {
sibling.children[i - 1] = sibling.children[i];
}
}

child.n += 1;
sibling.n -= 1;
}

private void merge(int idx) {
BTreeNode child = children[idx];
BTreeNode sibling = children[idx + 1];

child.keys[t - 1] = keys[idx];

for (int i = 0; i < sibling.n; ++i) {
child.keys[i + t] = sibling.keys[i];
}

if (!child.leaf) {
for (int i = 0; i <= sibling.n; ++i) {
child.children[i + t] = sibling.children[i];
}
}

for (int i = idx + 1; i < n; ++i) {
keys[i - 1] = keys[i];
}

for (int i = idx + 2; i <= n; ++i) {
children[i - 1] = children[i];
}

child.n += sibling.n + 1;
n--;
}
}

private BTreeNode root;
private final int t;

public BTree(int t) {
this.root = null;
this.t = t;
}

public void traverse(ArrayList<Integer> result) {
if (root != null) {
root.traverse(result);
}
}

public boolean search(int key) {
return root != null && root.search(key) != null;
}

public void insert(int key) {
if (search(key)) {
return;
}
if (root == null) {
root = new BTreeNode(t, true);
root.keys[0] = key;
root.n = 1;
} else {
if (root.n == 2 * t - 1) {
BTreeNode s = new BTreeNode(t, false);
s.children[0] = root;
s.splitChild(0, root);
int i = 0;
if (s.keys[0] < key) {
i++;
}
s.children[i].insertNonFull(key);
root = s;
} else {
root.insertNonFull(key);
}
}
}

public void delete(int key) {
if (root == null) {
return;
}
root.remove(key);
if (root.n == 0) {
root = root.leaf ? null : root.children[0];
}
}
}
Loading