B Tree

In a multi-way search tree, many nodes have a left subtree but no right subtree. Similarly, they have a right subtree but no left subtree. The insertion of the keys into such a tree also increases the height of the tree. 

As we know access time is totally dependent on the level of the tree so we want to minimize the access time through a balanced tree only. 

So we have a need to take all the leaf nodes at the same level and non-leaf nodes should not contain the empty subtree. For balancing the tree each node should contain m/2 keys except the root, where m represents m-way search tree. 

So the B-Tree of order m can be defined as:

1. Each node has at least m/2 and a maximum of m non-empty children.
2. All leaf nodes will be at the same level.
3. All leaf nodes can contain a maximum of m-1 keys.
4. All non-leaf nodes can contain m-1 keys where m is the number of children for that node.
5. Keys in the non-leaf node will divide the left and right sub-tree where the value of the left subtree keys will be less and the value of the right subtree keys will be more than the particular key.

---

Insertion In B-Tree

---

The insertion of a key in a B-Tree requires the first traversal in B-Tree. Through traversal, it will find the key to be inserted is already existing or not. Suppose the key does not exist then through traversal it will reach the leaf node. Now we have two cases for inserting the key.

1. Node is not full.
2. Node is already full.

If the leaf node in which the key is to be inserted is not full, then the insertion is done in the node. A node is said to be full if it contains a maximum of m-1 keys, given the order of the B-Tree to be m. 

If the node were to be full then insert the key into the existing set of keys in the node, split the node at its median into two nodes at the same level, push the median element up by one level, and rearrange the elements in each level. The following diagrams show how insertion is done in B-Tree of order 5 (i.e. m = 5).

---

Deletion In B-Tree

---

Deletion also requires traversal in B-Tree. After reaching on particular node two cases may occur:

1. Node is a leaf node.
2. Node is non-leaf.

For the first case suppose the node has more than the minimum number of keys then it can be easily detected. But suppose it has only a minimum number of keys, then first we will see the number of keys in the adjacent node will go to the parent node and the key in the parent node which is partitioning will be combined together in one node. suppose now parent has also less than the minimum number of keys then the same thing will be repeated until it will get the node which has more than the minimum number of keys.

For the second case, the key will be deleted and its predecessor or successor key will come in its place. Suppose both nodes of the predecessor or successor key have a minimum number of keys then the nodes of the predecessor and the successor keys will be combined. Let's see how the deletion is done in B-Tree in the following figure.

We have clearly elaborated the deletion mechanism pictorially below.

The source code of insertion and deletion of B-tree is given below,

Insertion and Deletion operations in B-Tree

#include <stdlib.h> #include <stdio.h> #define M 5 //order of B tree struct node{ int n; /* n < M No. of keys in node will always less than order of B tree */ int keys[M-1]; /*array of keys*/ struct node *p[M]; /* (n+1 pointers will be in use) */ }*root=NULL; enum KeyStatus { Duplicate,SearchFailure,Success,InsertIt,LessKeys }; void insert(int key); void display(struct node *root,int); void DelNode(int x); void search(int x); enum KeyStatus ins(struct node *r, int x, int* y, struct node** u); int searchPos(int x,int *key_arr, int n); enum KeyStatus del(struct node *r, int x); int main() { int key; int choice; printf("Creation of B tree for order %d\n",M); while(1) { printf("1.Insert\n"); printf("2.Delete\n"); printf("3.Search\n"); printf("4.Display\n"); printf("5.Quit\n"); printf("Enter your choice : "); scanf("%d", &choice); switch(choice) { case 1: printf("Enter the key : "); scanf("%d", &key); insert(key); break; case 2: printf("Enter the key : "); scanf("%d", &key); DelNode(key); break; case 3: printf("Enter the key : "); scanf("%d", &key); search(key); break; case 4: printf("Btree is :\n"); display(root,0); break; case 5: exit(1); default: printf("Wrong choice\n"); break; } } return 0; } void insert(int key) { struct node *newnode; int upKey; enum KeyStatus value; value = ins(root, key, &upKey, &newnode); if (value == Duplicate) printf("Key already available\n"); if (value == InsertIt) { struct node *uproot = root; root=malloc(sizeof(struct node)); root->n = 1; root->keys[0] = upKey; root->p[0] = uproot; root->p[1] = newnode; } } enum KeyStatus ins(struct node *ptr, int key, int *upKey,struct node **newnode) { struct node *newPtr, *lastPtr; int pos, i, n,splitPos; int newKey, lastKey; enum KeyStatus value; if (ptr == NULL) { *newnode = NULL; *upKey = key; return InsertIt; } n = ptr->n; pos = searchPos(key, ptr->keys, n); if (pos < n && key == ptr->keys[pos]) return Duplicate; value = ins(ptr->p[pos], key, &newKey, &newPtr); if (value != InsertIt) return value; /*If keys in node is less than M-1 where M is order of B tree*/ if (n < M - 1) { pos = searchPos(newKey, ptr->keys, n); /*Shifting the key and pointer right for inserting the new key*/ for (i=n; i>pos; i--) { ptr->keys[i] = ptr->keys[i-1]; ptr->p[i+1] = ptr->p[i]; } /*Key is inserted at exact location*/ ptr->keys[pos] = newKey; ptr->p[pos+1] = newPtr; ++ptr->n; /*incrementing the number of keys in node*/ return Success; } /*If keys in nodes are maximum and position of node to be inserted is last*/ if (pos == M - 1) { lastKey = newKey; lastPtr = newPtr; } else /*If keys in node are maximum and position of node to be inserted is not last*/ { lastKey = ptr->keys[M-2]; lastPtr = ptr->p[M-1]; for (i=M-2; i>pos; i--) { ptr->keys[i] = ptr->keys[i-1]; ptr->p[i+1] = ptr->p[i]; } ptr->keys[pos] = newKey; ptr->p[pos+1] = newPtr; } splitPos = (M - 1)/2; (*upKey) = ptr->keys[splitPos]; (*newnode)=malloc(sizeof(struct node));/*Right node after split*/ ptr->n = splitPos; /*No. of keys for left splitted node*/ (*newnode)->n = M-1-splitPos;/*No. of keys for right splitted node*/ for (i=0; i < (*newnode)->n; i++) { (*newnode)->p[i] = ptr->p[i + splitPos + 1]; if(i < (*newnode)->n - 1) (*newnode)->keys[i] = ptr->keys[i + splitPos + 1]; else (*newnode)->keys[i] = lastKey; } (*newnode)->p[(*newnode)->n] = lastPtr; return InsertIt; } void display(struct node *ptr, int blanks) { if (ptr) { int i, level = 0; printf("\nlevel=%d\n", (blanks+10)/10); for(i = 1; i <= blanks; i++) printf(" "); for (i=0; i < ptr->n; i++) printf("%d ",ptr->keys[i]); printf("\n"); for (i=0; i <= ptr->n; i++) display(ptr->p[i], blanks+10); } } void search(int key) { int pos, i, n; struct node *ptr = root; printf("Search path:\n"); while (ptr) { n = ptr->n; for (i = 0; i < ptr->n; i++) printf(" %d", ptr->keys[i]); printf("\n"); pos = searchPos(key, ptr->keys, n); if (pos < n && key == ptr->keys[pos]) { printf("Key %d found in position %d of last dispalyed node\n",key,i); return; } ptr = ptr->p[pos]; } printf("Key %d is not available\n",key); } int searchPos(int key, int *key_arr, int n) { int pos=0; while (pos < n && key > key_arr[pos]) pos++; return pos; } void DelNode(int key) { struct node *uproot; enum KeyStatus value; value = del(root,key); switch (value) { case SearchFailure: printf("Key %d is not available\n",key); break; case LessKeys: uproot = root; root = root->p[0]; free(uproot); break; } } enum KeyStatus del(struct node *ptr, int key) { int pos, i, pivot, n ,min; int *key_arr; enum KeyStatus value; struct node **p,*lptr,*rptr; if (ptr == NULL) return SearchFailure; /*Assigns values of node*/ n=ptr->n; key_arr = ptr->keys; p = ptr->p; min = (M - 1)/2;/*Minimum number of keys*/ pos = searchPos(key, key_arr, n); if (p[0] == NULL) { if (pos == n || key < key_arr[pos]) return SearchFailure; /*Shift keys and pointers left*/ for (i=pos+1; i < n; i++) { key_arr[i-1] = key_arr[i]; p[i] = p[i+1]; } return --ptr->n >= (ptr==root ? 1 : min) ? Success : LessKeys; } if (pos < n && key == key_arr[pos]) { struct node *qp = p[pos], *qp1; int nkey; while(1) { nkey = qp->n; qp1 = qp->p[nkey]; if (qp1 == NULL) break; qp = qp1; } key_arr[pos] = qp->keys[nkey-1]; qp->keys[nkey - 1] = key; } value = del(p[pos], key); if (value != LessKeys) return value; if (pos > 0 && p[pos-1]->n > min) { pivot = pos - 1; /*pivot for left and right node*/ lptr = p[pivot]; rptr = p[pos]; /*Assigns values for right node*/ rptr->p[rptr->n + 1] = rptr->p[rptr->n]; for (i=rptr->n; i>0; i--) { rptr->keys[i] = rptr->keys[i-1]; rptr->p[i] = rptr->p[i-1]; } rptr->n++; rptr->keys[0] = key_arr[pivot]; rptr->p[0] = lptr->p[lptr->n]; key_arr[pivot] = lptr->keys[--lptr->n]; return Success; } if (pos < n && p[pos+1]->n > min) { pivot = pos; /*pivot for left and right node*/ lptr = p[pivot]; rptr = p[pivot+1]; /*Assigns values for left node*/ lptr->keys[lptr->n] = key_arr[pivot]; lptr->p[lptr->n + 1] = rptr->p[0]; key_arr[pivot] = rptr->keys[0]; lptr->n++; rptr->n--; for (i=0; i < rptr->n; i++) { rptr->keys[i] = rptr->keys[i+1]; rptr->p[i] = rptr->p[i+1]; } rptr->p[rptr->n] = rptr->p[rptr->n + 1]; return Success; } if(pos == n) pivot = pos-1; else pivot = pos; lptr = p[pivot]; rptr = p[pivot+1]; /*merge right node with left node*/ lptr->keys[lptr->n] = key_arr[pivot]; lptr->p[lptr->n + 1] = rptr->p[0]; for (i=0; i < rptr->n; i++) { lptr->keys[lptr->n + 1 + i] = rptr->keys[i]; lptr->p[lptr->n + 2 + i] = rptr->p[i+1]; } lptr->n = lptr->n + rptr->n +1; free(rptr); /*Remove right node*/ for (i=pos+1; i < n; i++) { key_arr[i-1] = key_arr[i]; p[i] = p[i+1]; } return --ptr->n >= (ptr == root ? 1 : min) ? Success : LessKeys; }

Happy Exploring!