Deletion in B-Tree in Java

Deletion in B-Tree 

Deletion from a B-tree is more complicated than insertion, because we can delete a key from any node-not just a leaf—and when we delete a key from an internal node, we will have to rearrange the node’s children. In this article, we will discuss about the deletion in B-Tree in Java.

 

Deletion in B-Tree in Java

B-Tree

B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of order m can have at most m-1 keys and m children. One of the main reason of using B tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.

A B tree of order m contains all the properties of an M way tree. In addition, it contains the following properties.

  1. Every node in a B-Tree contains at most m children.
  2. Every node in a B-Tree except the root node and the leaf node contain at least m/2 children.
  3. The root nodes must have at least 2 nodes.
  4. All leaf nodes must be at the same level.

It is not necessary that, all the nodes contain the same number of children but, each node must have m/2 number of nodes.

Deletion Operation

There are three main cases for deletion operation in a B-Tree:-

Case 1: The key to be deleted is the leaf node.

  • The deletion of the key does not violate the property of the minimum number of keys a node should hold.
    In the tree below, deleting 42 does not violate the above properties.
Deletion in B-Tree in Java
  • The deletion of the key violates the property of the minimum number of keys a node should hold. In this case, we borrow a key from its immediate neighboring sibling node in the order of left to right.
  • First, visit the immediate left sibling. If the left sibling node has more than a minimum number of keys, then borrow a key from this node.
  • Else, check to borrow from the immediate right sibling node.
  • In the tree below, deleting 41 results in the above condition. Let us borrow a key from the left sibling node.
Deletion in B-Tree in java
  • If both the immediate sibling nodes already have a minimum number of keys, then merge the node with either the left sibling node or the right sibling node. This merging is done through the parent node.

    Deleting 40 results in the above case.
     
Deletion in B-Tree in java

Case 2 : If the key to be deleted lies in the internal node, the following cases occur.

  • The internal node, which is deleted, is replaced by an inorder predecessor if the left child has more than the minimum number of keys.
Deletion in B-Tree in Java
  • The internal node, which is deleted, is replaced by an inorder successor if the right child has more than the minimum number of keys.
  • If either child has exactly a minimum number of keys then, merge the left and the right children.
Deletion in B-Tree in java

Case 3: 

  • In this case, the height of the tree shrinks. If the target key lies in an internal node, and the deletion of the key leads to a fewer number of keys in the node (i.e. less than the minimum required), then look for the inorder predecessor and the inorder successor. If both the children contain a minimum number of keys then, borrowing cannot take place. 
  • Again, look for the sibling to borrow a key. But, if the sibling also has only a minimum number of keys then, merge the node with the sibling along with the parent. Arrange the children accordingly (increasing order).
Deletion in B-Tree in Java

Code in Java

import java.util.Stack;
public class BTree
{
private int T;

public class Node
{
int n;
int key[] = new int[2 * T - 1];
Node child[] = new Node[2 * T];
boolean leaf = true;

public int Find (int k)
{
for (int i = 0; i < this.n; i++)
{
if (this.key[i] == k)
{
return i;
}
}
return -1;
};
}

public BTree (int t)
{
T = t;
root = new Node ();
root.n = 0;
root.leaf = true;
}

private Node root;

// Search the key
private Node Search (Node x, int key)
{
int i = 0;
if (x == null)
return x;
for (i = 0; i < x.n; i++)
{
if (key < x.key[i])
{
break;
}
if (key == x.key[i])
{
return x;
}
}
if (x.leaf)
{
return null;
}
else
{
return Search (x.child[i], key);
}
}
// Split function
private void Split (Node x, int pos, Node y)
{
Node z = new Node ();
z.leaf = y.leaf;
z.n = T - 1;

for (int j = 0; j < T - 1; j++)
{
z.key[j] = y.key[j + T];
}
if (!y.leaf)
{
for (int j = 0; j < T; j++)
{
z.child[j] = y.child[j + T];
}
}
y.n = T - 1;
for (int j = x.n; j >= pos + 1; j--)
{
x.child[j + 1] = x.child[j];
}
x.child[pos + 1] = z;

for (int j = x.n - 1; j >= pos; j--)
{
x.key[j + 1] = x.key[j];
}
x.key[pos] = y.key[T - 1];
x.n = x.n + 1;
}
// Insert the key
public void Insert (final int key)
{
Node r = root;

if (r.n == 2 * T - 1)
{
Node s = new Node ();
root = s;
s.leaf = false;
s.n = 0;
s.child[0] = r;
Split (s, 0, r);
_Insert (s, key);
}
else
{
_Insert (r, key);
}
}

// Insert the node
final private void _Insert (Node x, int k)
{
if (x.leaf)
{
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--)
{
x.key[i + 1] = x.key[i];
}
x.key[i + 1] = k;
x.n = x.n + 1;
}
else
{
int i = 0;
for (i = x.n - 1; i >= 0 && k < x.key[i]; i--)
{
};
i++;
Node tmp = x.child[i];

if (tmp.n == 2 * T - 1)
{
Split (x, i, tmp);
if (k > x.key[i])
{
i++;
}
}
_Insert (x.child[i], k);
}
}

public void Show ()
{
Show (root);
}

private void Remove (Node x, int key)
{
int pos = x.Find (key);
if (pos != -1)
{
if (x.leaf)
{
int i = 0;
for (i = 0; i < x.n && x.key[i] != key; i++)
{
};
for (; i < x.n; i++)
{
if (i != 2 * T - 2)
{
x.key[i] = x.key[i + 1];
}
}
x.n--;
return;
}
if (!x.leaf)
{
Node pred = x.child[pos];
int predKey = 0;
if (pred.n >= T)
{
for (;;)
{
if (pred.leaf)
{
System.out.println (pred.n);
predKey = pred.key[pred.n - 1];
break;
}
else
{
pred = pred.child[pred.n];
}
}
Remove (pred, predKey);
x.key[pos] = predKey;
return;
}

Node nextNode = x.child[pos + 1];
if (nextNode.n >= T)
{
int nextKey = nextNode.key[0];
if (!nextNode.leaf)
{
nextNode = nextNode.child[0];
for (;;)
{
if (nextNode.leaf)
{
nextKey = nextNode.key[nextNode.n - 1];
break;
}
else
{
nextNode = nextNode.child[nextNode.n];
}
}
}
Remove (nextNode, nextKey);
x.key[pos] = nextKey;
return;
}
int temp = pred.n + 1;
pred.key[pred.n++] = x.key[pos];
for (int i = 0, j = pred.n; i < nextNode.n; i++)
{
pred.key[j++] = nextNode.key[i];
pred.n++;
}
for (int i = 0; i < nextNode.n + 1; i++)
{
pred.child[temp++] = nextNode.child[i];
}
x.child[pos] = pred;
for (int i = pos; i < x.n; i++)
{
if (i != 2 * T - 2)
{
x.key[i] = x.key[i + 1];
}
}
for (int i = pos + 1; i < x.n + 1; i++)
{
if (i != 2 * T - 1)
{
x.child[i] = x.child[i + 1];
}
}
x.n--;
if (x.n == 0)
{
if (x == root)
{
root = x.child[0];
}
x = x.child[0];
}
Remove (pred, key);
return;
}
}
else
{
for (pos = 0; pos < x.n; pos++)
{
if (x.key[pos] > key)
{
break;
}
}
Node tmp = x.child[pos];

if (tmp.n >= T)
{
Remove (tmp, key);
return;
}
if (true)
{
Node nb = null;
int devider = -1;
if (pos != x.n && x.child[pos + 1].n >= T)
{
devider = x.key[pos];
nb = x.child[pos + 1];
x.key[pos] = nb.key[0];
tmp.key[tmp.n++] = devider;
tmp.child[tmp.n] = nb.child[0];

for (int i = 1; i < nb.n; i++)
{
nb.key[i - 1] = nb.key[i];
}
for (int i = 1; i <= nb.n; i++)
{
nb.child[i - 1] = nb.child[i];
}
nb.n--;
Remove (tmp, key);
return;
}
else if (pos != 0 && x.child[pos - 1].n >= T)
{
devider = x.key[pos - 1];
nb = x.child[pos - 1];
x.key[pos - 1] = nb.key[nb.n - 1];
Node child = nb.child[nb.n];
nb.n--;

for (int i = tmp.n; i > 0; i--)
{
tmp.key[i] = tmp.key[i - 1];
}
tmp.key[0] = devider;

for (int i = tmp.n + 1; i > 0; i--)
{
tmp.child[i] = tmp.child[i - 1];
}
tmp.child[0] = child;
tmp.n++;
Remove (tmp, key);
return;
}
else
{
Node lt = null;
Node rt = null;
boolean last = false;
if (pos != x.n)
{
devider = x.key[pos];
lt = x.child[pos];
rt = x.child[pos + 1];
}
else
{
devider = x.key[pos - 1];
rt = x.child[pos];
lt = x.child[pos - 1];
last = true;
pos--;
}
for (int i = pos; i < x.n - 1; i++)
{
x.key[i] = x.key[i + 1];
}
for (int i = pos + 1; i < x.n; i++)
{
x.child[i] = x.child[i + 1];
}
x.n--;
lt.key[lt.n++] = devider;

for (int i = 0, j = lt.n; i < rt.n + 1; i++, j++)
{
if (i < rt.n)
{
lt.key[j] = rt.key[i];
}
lt.child[j] = rt.child[i];
}
lt.n += rt.n;
if (x.n == 0)
{
if (x == root)
{
root = x.child[0];
}
x = x.child[0];
}
Remove (lt, key);
return;
}
}
}
}

public void Remove (int key)
{
Node x = Search (root, key);
if (x == null)
{
return;
}
Remove (root, key);
}

public void Task (int a, int b)
{
Stack < Integer > st = new Stack <> ();
FindKeys (a, b, root, st);
while (st.isEmpty () == false)
{
this.Remove (root, st.pop ());
}
}

private void FindKeys (int a, int b, Node x, Stack < Integer > st)
{
int i = 0;
for (i = 0; i < x.n && x.key[i] < b; i++)
{
if (x.key[i] > a)
{
st.push (x.key[i]);

}
}
if (!x.leaf)
{
for (int j = 0; j < i + 1; j++)
{
FindKeys (a, b, x.child[j], st);
}
}
}

public boolean Contain (int k)
{
if (this.Search (root, k) != null)
{
return true;
}
else
{
return false;
}
}

// Show the node
private void Show (Node x)
{
assert (x == null);
for (int i = 0; i < x.n; i++)
{
System.out.print (x.key[i] + " ");
}
if (!x.leaf)
{
for (int i = 0; i < x.n + 1; i++)
{
Show (x.child[i]);
}
}
}

public static void main (String[]args)
{
BTree b = new BTree (3);
b.Insert (8);
b.Insert (9);
b.Insert (10);
b.Insert (11);
b.Insert (15);
b.Insert (20);
b.Insert (17);

b.Show ();
b.Remove (10);

System.out.println ();
b.Show ();
}
}

Output :

10 8 9 11 15 17 20
11 8 9 15 17 20