B-Tree: Insertion

Insertion In B-Tree

On this page we will discuss about insertion in B-Tree in C . B-tree is a self-balancing tree data structure that can store large amounts of data on disk or in memory. It is commonly used in database systems and file systems to organize and manage large volumes of data efficiently
Insertion in B-Tree In C

Insertion In B-Tree In C

In a B-Tree, the new element must be added to the leaf node only. The insertion operation can be performed as follows:
  • Initially we must check if the tree is empty or not.
  • If the tree is found to be empty, then a new node with new key value is created inserted as the root node.
  • If the tree is not empty, then using the BST logic the new node is inserted to it’s suitable location.
  • If there is some empty location at the leaf then, keeping in mind the increasing order of the key value, the node is inserted at the suitable position.
  • If the leaf node is filled completely, then split the node by moving the middle element upwards to the parent node.
  • If the node to be split is the root node, then the middle element that is moved becomes the new root node.
  • Let us understand this with the help of an example.

Assume we have a B-Tree as given in the image below.

  • As discussed in the properties above we , for instance, consider the B-tree of order = 5.
  • Hence to construct a B-tree by abiding by it’s properties we see,
  • The order of tree is 5. It means each node can have at most 4 keys.
Insertion in B-Tree In C
  • If we see the image, the node (5) violates the properties of the B-tree, since it contains 4 keys.
  • The node splits from the middle element ‘ U ‘ , which moves upwards to the parent node.
Insertion in B-Tree In C

Insert ‘ B ‘

  • Now, let us insert an element to the B-tree.
  • Let the element to be inserted is ‘ B ‘. 
  • Since ‘ B ‘ comes before ‘ G ‘ in alphabetical order, it is to be inserted in the node 2.
  • The node tree structure after insertion as follows.
Insertion in B-Tree In C
  • Now, since maximum keys a node can have = 4 ,the node 2 splits from the middle.
  • The middle element moves upward to the parent/root node.
  • The tree structure after alteration is shown as follows
Insertion in B-Tree In C
  • As discussed before, each node can have at most 4 keys, we can see here, the root node violates this property.
  • Hence, the root node is split from the middle.
  • The middle element ‘ M ‘ moves upward and becomes the new root to the tree structure.
  • The tree structure after alteration is shown as follows 
Insertion in B-Tree In C

Insert ‘ Q ‘

  • If we see the alphabetical order, the new node to be inserted Q lies after P.
  • Thus Q, will be inserted in the second last node before ‘ S ‘ and ‘ T ‘. 
  • The tree structure after new insertion is shown as follows.
Insertion in B-Tree In C
  • Since is inserted at the leaf node which could accommodate more nodes.
  • The final tree structure is shown as follows.
Insertion in B-Tree In C

C Code For Insertion in B-Tree

Run
// insertioning a key on a B-tree in C

#include <stdio.h>
#include <stdlib.h>

#define MAX 3
#define MIN 2

struct btreeNode
{
  int item[MAX + 1], count;
  struct btreeNode *link[MAX + 1];
};

struct btreeNode *root;

// Node creation
struct btreeNode *
createNode (int item, struct btreeNode *child)
{
  struct btreeNode *newNode;
  newNode = (struct btreeNode *) malloc (sizeof (struct btreeNode));
  newNode->item[1] = item;
  newNode->count = 1;
  newNode->link[0] = root;
  newNode->link[1] = child;
  return newNode;
}

// Insert
void insertValue (int item, int pos, struct btreeNode *node,
	     struct btreeNode *child)
{
  int j = node->count;
  while (j > pos)
    {
      node->item[j + 1] = node->item[j];
      node->link[j + 1] = node->link[j];
      j--;
    }
  node->item[j + 1] = item;
  node->link[j + 1] = child;
  node->count++;
}

// Split node
void splitNode (int item, int *pval, int pos, struct btreeNode *node,
	   struct btreeNode *child, struct btreeNode **newNode)
{
  int median, j;

  if (pos > MIN)
    median = MIN + 1;
  else
    median = MIN;

  *newNode = (struct btreeNode *) malloc (sizeof (struct btreeNode));
  j = median + 1;
  while (j <= MAX)
    {
      (*newNode)->item[j - median] = node->item[j];
      (*newNode)->link[j - median] = node->link[j];
      j++;
    }
  node->count = median;
  (*newNode)->count = MAX - median;

  if (pos <= MIN)
    {
      insertValue (item, pos, node, child);
    }
  else
    {
      insertValue (item, pos - median, *newNode, child);
    }
  *pval = node->item[node->count];
  (*newNode)->link[0] = node->link[node->count];
  node->count--;
}

// Set the value of node
int setNodeValue (int item, int *pval,
	      struct btreeNode *node, struct btreeNode **child)
{
  int pos;
  if (!node)
    {
      *pval = item;
      *child = NULL;
      return 1;
    }

  if (item < node->item[1])
    {
      pos = 0;
    }
  else
    {
      for (pos = node->count; (item < node->item[pos] && pos > 1); pos--)
	;
      if (item == node->item[pos])
	{
	  printf ("Duplicates not allowed\n");
	  return 0;
	}
    }
  if (setNodeValue (item, pval, node->link[pos], child))
    {
      if (node->count < MAX)
	{
	  insertValue (*pval, pos, node, *child);
	}
      else
	{
	  splitNode (*pval, pval, pos, node, *child, child);
	  return 1;
	}
    }
  return 0;
}

// Insert the value
void insertion (int item)
{
  int flag, i;
  struct btreeNode *child;

  flag = setNodeValue (item, &i, root, &child);
  if (flag)
    root = createNode (i, child);
}

// Copy the successor
void copySuccessor (struct btreeNode *myNode, int pos)
{
  struct btreeNode *dummy;
  dummy = myNode->link[pos];

  for (; dummy->link[0] != NULL;)
    dummy = dummy->link[0];
  myNode->item[pos] = dummy->item[1];
}

// Do rightshift
void
rightShift (struct btreeNode *myNode, int pos)
{
  struct btreeNode *x = myNode->link[pos];
  int j = x->count;

  while (j > 0)
    {
      x->item[j + 1] = x->item[j];
      x->link[j + 1] = x->link[j];
    }
  x->item[1] = myNode->item[pos];
  x->link[1] = x->link[0];
  x->count++;

  x = myNode->link[pos - 1];
  myNode->item[pos] = x->item[x->count];
  myNode->link[pos] = x->link[x->count];
  x->count--;
  return;
}

// Do leftshift
void leftShift (struct btreeNode *myNode, int pos)
{
  int j = 1;
  struct btreeNode *x = myNode->link[pos - 1];

  x->count++;
  x->item[x->count] = myNode->item[pos];
  x->link[x->count] = myNode->link[pos]->link[0];

  x = myNode->link[pos];
  myNode->item[pos] = x->item[1];
  x->link[0] = x->link[1];
  x->count--;

  while (j <= x->count)
    {
      x->item[j] = x->item[j + 1];
      x->link[j] = x->link[j + 1];
      j++;
    }
  return;
}

// Merge the nodes
void mergeNodes (struct btreeNode *myNode, int pos)
{
  int j = 1;
  struct btreeNode *x1 = myNode->link[pos], *x2 = myNode->link[pos - 1];

  x2->count++;
  x2->item[x2->count] = myNode->item[pos];
  x2->link[x2->count] = myNode->link[0];

  while (j <= x1->count)
    {
      x2->count++;
      x2->item[x2->count] = x1->item[j];
      x2->link[x2->count] = x1->link[j];
      j++;
    }

  j = pos;
  while (j < myNode->count)
    {
      myNode->item[j] = myNode->item[j + 1];
      myNode->link[j] = myNode->link[j + 1];
      j++;
    }
  myNode->count--;
  free (x1);
}

// Adjust the node
void adjustNode (struct btreeNode *myNode, int pos)
{
  if (!pos)
    {
      if (myNode->link[1]->count > MIN)
	{
	  leftShift (myNode, 1);
	}
      else
	{
	  mergeNodes (myNode, 1);
	}
    }
  else
    {
      if (myNode->count != pos)
	{
	  if (myNode->link[pos - 1]->count > MIN)
	    {
	      rightShift (myNode, pos);
	    }
	  else
	    {
	      if (myNode->link[pos + 1]->count > MIN)
		{
		  leftShift (myNode, pos + 1);
		}
	      else
		{
		  mergeNodes (myNode, pos);
		}
	    }
	}
      else
	{
	  if (myNode->link[pos - 1]->count > MIN)
	    rightShift (myNode, pos);
	  else
	    mergeNodes (myNode, pos);
	}
    }
}

// Traverse the tree
void traversal (struct btreeNode *myNode)
{
  int i;
  if (myNode)
    {
      for (i = 0; i < myNode->count; i++)
	{
	  traversal (myNode->link[i]);
	  printf ("%d ", myNode->item[i + 1]);
	}
      traversal (myNode->link[i]);
    }
}

int main ()
{
  int item, ch;

  insertion (8);
  insertion (9);
  insertion (10);
  insertion (11);
  insertion (15);
  insertion (16);
  insertion (17);
  insertion (18);
  insertion (20);
  insertion (23);

  traversal (root);
}

Output:

8 9 10 11 15 16 17 18 20 23 

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

Checkout list of all the video courses in PrepInsta Prime Subscription

Introduction to Trees

Binary Trees

Binary Search Trees

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

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- CC++Java
  • Spiral Order traversal of Tree- CC++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.- CC++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- CC++ | Java
  • Lowest Common Ancestor in Binary Tree- CC++ | Java

Introduction to Trees

Binary Trees

Binary Search Trees

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

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- CC++Java
  • Spiral Order traversal of Tree- CC++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.- CC++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- CC++ | Java
  • Lowest Common Ancestor in Binary Tree. CC++ | Java