Deletion In B-Tree C++

March 7, 2023

Deletion In B-Tree:

A B–Tree can be defined as a multi-way search tree of order m. All the values of a node that appear on the leftmost child of the node are smaller than the first value of that node. Similarly, all the values that appear on the rightmost child of a node are greater than the last value of that node.We will learn the deletion in B-Tree in C++.

Deletion In B-Tree In C++

Example:

Let us consider the given tree. From the given tree we are to delete the following elements:

A = 20 , 53 , 89 , 90 , 85.

Assuming we have order = 5; minimum keys = ⌈ m/2⌉ – 1 = 2; maximum keys = ⌈ m/2⌉ + 1 = 4; minimum children = ⌈ m/2⌉ = 3
maximum children = m = 5

1. If the target key is at the leaf node:

If the target key is at the leaf node, we further study the given data to check if any of the following cases exist:

Case 1: If the leaf node consists of the min number of keys according to the given degree/order, then the key is simply deleted from the node.
Case 2: If the leaf contains the minimum number of keys, then:
Case 2a: The node can borrow a key from the immediate left sibling node,if it has more than the minimum number of keys.The transfer of the keys take place through the parent node, i.e, the maximum key of the left sibling moves upwards and replaces the parent; while the parent key moves down to the target node from where the target key is simply deleted.
Case 2b: The node can borrow a key from the immediate right sibling node, if it has more than the minimum number of keys.The transfer of the keys take place through the parent node, i.e, the minimum key of the right sibling moves upwards and replaces the parent; while the parent key moves down to the target node from where the target key is simply deleted.
Case 2c: If neither of the siblings have keys more than the minimum number of keys required then, merge the target node with either the left or the right sibling along with the parent key of respective node.

2.If the target key is at the internal node:

If the target key is at an internal node, we further study the given data to check if any of the following cases exist:

Case 1: If the left child has more than the minimum number of keys, the target key in the internal node is replaced by its inorder predecessor ,i.e, the largest element of the left child node.
Case 2: If the right child has more than the minimum number of keys, the target key in the internal node is replaced by it’s inorder successor ,i.e, the smallest element of the right child node.

Step 1:

The first element to be deleted from the tree structure is 20.
We can see the key lies in the leaf node.

Step 2:

The key 20 exists in a leaf node.
The node has more than the minimum number of keys required.
Thus the key is simply deleted from the node.
The tree after deletion is shown as follows.

Step 3:

The next element to be deleted from the tree is 53.
We can see from the image that the key exists in the leaf node.

Step 4:

Since the node in which the target key 53 exists has just the minimum number of keys, we cannot delete it directly.
We check if the target node can borrow a key from it’s sibling nodes.
Since the target node doesn’t have any right sibling, it borrows from the left sibling node.
As we have studied above how the process of borrow and replace takes place, we apply it to the given structure.

Step 5:

The key 49 moves upwards to the parent node.
The key 50 moves down to the target node.

Step 6:

Now, since the target node has keys more than the minimum number of keys required, the key can be deleted directly.
The tree structure after deletion is shown as follows.

Step 7:

The next element to be deleted is 89.
The target key lies within a leaf node as seen from the image.

Step 8:

Again, the target node holds just the minimum number of keys required and hence the node cannot be deleted directly.
The target node now has to borrow a key from either of it’s siblings.
We check the left sibling; it also holds just the minimum number of keys required.
We check the right sibling node; it has one more than the minimum number of nodes so the target node can borrow a key from it.

B-Tree : Introduction

B-Tree: Insertion

AVL Trees : Introduction

AVL Tree Insertion

AVL Tree Deletion

Step 9:

The key 93 moves up to the parent node.
The parent key 90 moves down to the target node.

Step 10:

Now, as the target node has sufficient number of keys the target key can directly be deleted from the target node.
The tree structure after deletion is shown as follows.

Step 11:

The next key to be deleted is 90.
The key exists within a leaf node as shown in the image.

Step 12:

We can see that the target node has just the minimum number of keys.
The target node has to borrow a key from either of it’s siblings.
Since each of the siblings just have the number of the minimum keys, it cannot borrow the keys directly.

Step 13:

Since the target node cannot borrow from either of the siblings, we merge the target node, either of the sibling node and the corresponding parent to them.
The process of merging is shown as follows.

Step 14:

Since the target node now has sufficient number of keys, the target key 90 can be deleted directly.
The tree structure after the deletion of the element is shown as follows.

Step 15:

The next target node is 85.
Now here the node to be deleted is not a leaf node but an internal node.

Step 16:

In case, when an internal node is to be deleted, we replace the key with it’s inorder predecessor or inorder successor.
We can select either of the child nodes if they have sufficient number of keys.
But as we can see in this case the target internal node can only borrow from it’s right child, i.e, inorder predecessor.
The key 85 moves down to the child node; key 87 moves up to the parent node.

Step 17:

Now, as the target key is moved to the leaf node, it can be simply deleted from the leaf node.
The final tree structure after deletion of various nodes and preserving the b-tree properties is shown as follows.

C Code For Deletion In B-Tree

Run

// Deleting a key from a B-tree in C++

#include<iostream>
using namespace std;

class Tree
{
  int *keys;
  int t;
  Tree **C;
  int n;
  bool leaf_node;

public:
    Tree (int _t, bool _leaf_node);

  void traverse ();

  int findKey (int k);
  void insert_more (int k);
  void splitChild (int i, Tree * y);
  void Deletenode (int k);
  void remove_leaf_node (int idx);
  void remove_nonleaf_node (int idx);
  int get_pre (int idx);
  int get_suc (int idx);
  void fill (int idx);
  void borrow_prev (int idx);
  void borrow_next (int idx);
  void merge (int idx);
  friend class BTree;
};

class BTree
{
  Tree *root;
  int t;

public:
    BTree (int _t)
  {
    root = NULL;
    t = _t;
  }

  void traverse ()
  {
    if (root != NULL)
      root->traverse ();
  }

  void insertion (int k);

  void Deletenode (int k);
};

// B tree node
Tree::Tree (int t1, bool leaf_node1)
{
  t = t1;
  leaf_node = leaf_node1;
  int p = 2 * t - 1;
  keys = new int[p];
  C = new Tree *[2 * t];

  n = 0;
}

// Find the key
int Tree::findKey (int k)
{
  int idx = 0;
  while (idx < n && keys[idx] < k)
    ++idx;
  return idx;
}

// Deletenode operation
void Tree::Deletenode (int k)
{
  int idx = findKey (k);

  if (idx < n && keys[idx] == k)
    {
      if (leaf_node)
	remove_leaf_node (idx);
      else
	remove_nonleaf_node (idx);
    }
  else
    {
      if (leaf_node)
	{
	  cout << "The key " << k << " is does not exist in the tree\n"; return; } bool flag = ((idx == n) ? true : false); if (C[idx]->n < t) fill (idx); if (flag && idx > n)
	C[idx - 1]->Deletenode (k);
      else
	C[idx]->Deletenode (k);
    }
  return;
}

// Remove from the leaf_node
void Tree::remove_leaf_node (int idx)
{
  for (int i = idx + 1; i < n; ++i) keys[i - 1] = keys[i]; n--; return; } // Delete from non leaf_node node void Tree::remove_nonleaf_node (int idx) { int k = keys[idx]; if (C[idx]->n >= t)
    {
      int pred = get_pre (idx);
      keys[idx] = pred;
      C[idx]->Deletenode (pred);
    }

  else if (C[idx + 1]->n >= t)
    {
      int succ = get_suc (idx);
      keys[idx] = succ;
      C[idx + 1]->Deletenode (succ);
    }

  else
    {
      merge (idx);
      C[idx]->Deletenode (k);
    }
  return;
}

int Tree::get_pre (int idx)
{
  Tree *cur = C[idx];
  while (!cur->leaf_node)
    cur = cur->C[cur->n];

  return cur->keys[cur->n - 1];
}

int Tree::get_suc (int idx)
{
  Tree *cur = C[idx + 1];
  while (!cur->leaf_node)
    cur = cur->C[0];

  return cur->keys[0];
}

void Tree::fill (int idx)
{
  if (idx != 0 && C[idx - 1]->n >= t)
    borrow_prev (idx);

  else if (idx != n && C[idx + 1]->n >= t)
    borrow_next (idx);

  else
    {
      if (idx != n)
	merge (idx);
      else
	merge (idx - 1);
    }
  return;
}

// Borrow from previous
void Tree::borrow_prev (int idx)
{
  Tree *child = C[idx];
  Tree *sibling = C[idx - 1];

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

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

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

  if (!child->leaf_node)
    child->C[0] = sibling->C[sibling->n];

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

  child->n += 1;
  sibling->n -= 1;

  return;
}

// Borrow from the next
void Tree::borrow_next (int idx)
{
  Tree *child = C[idx];
  Tree *sibling = C[idx + 1];

  child->keys[(child->n)] = keys[idx];

  if (!(child->leaf_node))
    child->C[(child->n) + 1] = sibling->C[0];

  keys[idx] = sibling->keys[0];

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

  if (!sibling->leaf_node)
    {
      for (int i = 1; i <= sibling->n; ++i)
	sibling->C[i - 1] = sibling->C[i];
    }

  child->n += 1;
  sibling->n -= 1;

  return;
}

// Merge
void Tree::merge (int idx)
{
  Tree *child = C[idx];
  Tree *sibling = C[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_node)
    {
      for (int i = 0; i <= sibling->n; ++i)
	child->C[i + t] = sibling->C[i];
    }

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

  for (int i = idx + 2; i <= n; ++i) C[i - 1] = C[i]; child->n += sibling->n + 1;
  n--;

  delete (sibling);
  return;
}

// Insertion operation
void BTree::insertion (int k)
{
  if (root == NULL)
    {
      root = new Tree (t, true);
      root->keys[0] = k;
      root->n = 1;
    }
  else
    {
      if (root->n == 2 * t - 1)
	{
	  Tree *s = new Tree (t, false);

	  s->C[0] = root;

	  s->splitChild (0, root);

	  int i = 0;
	  if (s->keys[0] < k) i++; s->C[i]->insert_more (k);

	  root = s;
	}
      else
	root->insert_more (k);
    }
}

// Insertion non full
void Tree::insert_more (int k)
{
  int i = n - 1;

  if (leaf_node == true)
    {
      while (i >= 0 && keys[i] > k)
	{
	  keys[i + 1] = keys[i];
	  i--;
	}

      keys[i + 1] = k;
      n = n + 1;
    }
  else
    {
      while (i >= 0 && keys[i] > k)
	i--;

      if (C[i + 1]->n == 2 * t - 1)
	{
	  splitChild (i + 1, C[i + 1]);

	  if (keys[i + 1] < k) i++; } C[i + 1]->insert_more (k);
    }
}

// Split child
void Tree::splitChild (int i, Tree * y)
{
  Tree *z = new Tree (y->t, y->leaf_node);
  z->n = t - 1;

  for (int j = 0; j < t - 1; j++) z->keys[j] = y->keys[j + t];

  if (y->leaf_node == false)
    {
      for (int j = 0; j < t; j++) z->C[j] = y->C[j + t];
    }

  y->n = t - 1;

  for (int j = n; j >= i + 1; j--)
    C[j + 1] = C[j];

  C[i + 1] = z;

  for (int j = n - 1; j >= i; j--)
    keys[j + 1] = keys[j];

  keys[i] = y->keys[t - 1];

  n = n + 1;
}

// Traverse
void Tree::traverse ()
{
  int i;
  for (i = 0; i < n; i++) { if (leaf_node == false) C[i]->traverse ();
      cout << " " << keys[i]; } if (leaf_node == false) C[i]->traverse ();
}

// Delete Operation
void BTree::Deletenode (int k)
{
  if (!root)
    {
      cout << "The tree is empty\n"; return; } root->Deletenode (k);

  if (root->n == 0)
    {
      Tree *tmp = root;
      if (root->leaf_node)
	root = NULL;
      else
	root = root->C[0];

      delete tmp;
    }
  return;
}

int main ()
{
  BTree t (3);
  t.insertion (8);
  t.insertion (9);
  t.insertion (10);
  t.insertion (11);
  t.insertion (12);
  t.insertion (13);
  t.insertion (14);
  t.insertion (15);
  t.insertion (16);
  t.insertion (17);

  cout << "The B-tree is: ";
  t.traverse ();

  t.Deletenode (10);

  cout << "\nThe B-tree is: ";
  t.traverse ();
}

Output:

The B-tree is:  8 9 10 11 12 13 14 15 16 17
The B-tree is:  8 9 11 12 13 14 15 16 17

Prime Course Trailer

Related Banners

Get PrepInsta Prime & get Access to all 200+ courses offered by PrepInsta in One Subscription

Get over 200+ course One Subscription

Courses like AI/ML, Cloud Computing, Ethical Hacking, C, C++, Java, Python, DSA (All Languages), Competitive Coding (All Languages), TCS, Infosys, Wipro, Amazon, DBMS, SQL and others

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Tree in Data Structures (Introduction)
Tree Traversals: Inorder Postorder Preorder : C | C++ | Java
Inorder Postorder PreOrder Traversals Examples
- Inorder Tree Traversal in Binary Tree: C | C++ | Java
- Preorder Tree Traversal in Binary Tree : C | C++ | Java
- Postorder Tree Traversal in Binary Tree : C | C++ | Java
Tree Traversal without Recursion
- Postorder Preorder Inorder Traversal without recursion
- Inorder Tree Traversal without Recursion – C | C++ | Java
- Preorder Tree Traversal without Recursion – C | C++ | Java
- Postorder Tree Traversal without Recursion – C | C++ | Java

Binary Search Trees

Binary search tree in Data Structures (Introduction)
- BST: Introduction to Binary Search Tree
- BST: Binary Search Tree Program : C | C++ | Java
- BST: Search a node in Binary Search Tree : C | C++ | Java
- BST: Insertion in a Binary Search Tree : C | C++ | Java
- BST: Deletion in a Binary Search Tree : C | C++ | Java

Traversals

Traversal in Trees
Tree Traversals: Breadth-First Search (BFS) : C | C++ | Java
Tree Traversals: Depth First Search (DFS) : C | C++ | Java
Construct a Binary Tree from Postorder and Inorder

B – Trees

B-Tree
- B-Tree: Introduction
- B-Tree: Insertion : C | C++ | Java
- B-Tree: Deletion : C | C++ | Java

AVL Trees

AVL Trees
- AVL Trees: Introduction
- AVL Tree Insertion : C | C++ | Java
- AVL Tree Deletion : C | C++ | Java
- Insertion in a Binary Tree (Level Order) – C | C++ | Java
- Searching in Binary Tree – C | C++ | Java
- Searching in a Binary Search Tree – C | C++ | Java

Complete Programs for Trees

Depth First Traversals – C | C++ | Java
Level Order Traversal – C | C++ | Java
Construct Tree from given Inorder and Preorder traversals – C | C++ | Java
Construct Tree from given Postorder and Inorder traversals – C | C++ | Java
Construct Tree from given Postorder and Preorder traversal – C | C++ | Java
Find size of the Binary tree – C | C++ | Java
Find the height of binary tree – C | C++ | Java
Find maximum in binary tree – C | C++ | Java
Check whether two tree are identical- C| C++| Java
Spiral Order traversal of Tree- C | C++| Java
Level Order Traversal Line by Line – C | C++| Java
Hand shaking lemma and some Impotant Tree Properties.
Check If binary tree if Foldable or not.- C| C++| Java
check whether tree is Symmetric – C| C++| Java.
Check for Children-Sum in Binary Tree- C|C++| Java
Sum of all nodes in Binary Tree- C | C++ | Java
Lowest Common Ancestor in Binary Tree- C | C++ | Java