×

Search anything:

# B-Tree Deletion

#### Data Structures tree data structure b tree deletion operation Get this book -> Problems on Array: For Interviews and Competitive Programming

Reading time: 15 minutes | Coding time: 10 minutes

A B-tree is a tree data structure that keeps data sorted and allows searches, insertions, and deletions in logarithmic amortized time.
Deletion in a B Tree is similar to insertion. At first the node from which a value is to be deleted is searched. If found out, then the value is deleted. After deletion the tree is checked if it still follows B Tree properties.

### Algorithm

• Basic operations associated with deletion of an element in a B-Tree:

• To delete any element from a B-tree, starting at a leaf node, there are 2 steps:

• Remove X from the current node. Being a leaf node there are no subtrees to worry about.
• Removing X might cause the node containing it to have too few values.
• Recall that we require the root to have at least 1 value in it and all other nodes to have at least (M-1)/2 values in them. If the node has too few values, we say it has underflowed.
• If underflow does not occur, then we are finished the deletion process. If it does occur, it must be fixed.
• The process for fixing a root is slightly different than the process for fixing the other nodes, and will be discussed afterwards. The figure illustrates the steps of deletion of an element from a B-Tree.

### Complexity

• Worst case deletion time complexity: `Θ(logn)`

• Average case Space complexity: `Θ(n)`

• Worst case Space complexity: `Θ(n)`

### Implementations

``````
#include <iostream.h>
#include <conio.h>

using namespace std;

#define MAX 4
#define MIN 2

struct btreeNode {
int val[MAX + 1], count;
};

btreeNode *root;

/* creating new node */
btreeNode * createNode(int val, btreeNode *child) {
btreeNode *newNode = new btreeNode;
newNode->val = val;
newNode->count = 1;
return newNode;
}

/* Places the value in appropriate position */
void addValToNode(int val, int pos, btreeNode *node, btreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
j--;
}
node->val[j + 1] = val;
node->count++;
}

/* split the node */
void splitNode(int val, int *pval, int pos, btreeNode *node,btreeNode *child, btreeNode **newNode) {
int median, j;

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

*newNode = new btreeNode;
j = median + 1;
while (j <= MAX) {
(*newNode)->val[j - median] = node->val[j];
j++;
}
node->count = median;
(*newNode)->count = MAX - median;

if (pos <= MIN) {
}
else {
addValToNode(val, pos - median, *newNode, child);
}
*pval = node->val[node->count];
node->count--;
}

/* sets the value val in the node */
int setValueInNode(int val, int *pval,btreeNode *node, btreeNode **child) {

int pos;
if (!node) {
*pval = val;
*child = NULL;
return 1;
}

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

/* insert val in B-Tree */
void insertion(int val) {
int flag, i;
btreeNode *child;

flag = setValueInNode(val, &i, root, &child);
if (flag)
root = createNode(i, child);
}

/* copy successor for the value to be deleted */
void copySuccessor(btreeNode *myNode, int pos) {
btreeNode *dummy;

myNode->val[pos] = dummy->val;

}

/* removes the value from the given node and rearrange values */
void removeVal(btreeNode *myNode, int pos) {
int i = pos + 1;
while (i <= myNode->count) {
myNode->val[i - 1] = myNode->val[i];
i++;
}
myNode->count--;
}

/* shifts value from parent to right child */
void doRightShift(btreeNode *myNode, int pos) {
int j = x->count;

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

myNode->val[pos] = x->val[x->count];
x->count--;
return;
}

/* shifts value from parent to left child */
void doLeftShift(btreeNode *myNode, int pos) {
int j = 1;
btreeNode *x = myNode->link[pos - 1];

x->count++;
x->val[x->count] = myNode->val[pos];

myNode->val[pos] = x->val;
x->count--;

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

/* merge nodes */
void mergeNodes(btreeNode *myNode, int pos) {
int j = 1;

x2->count++;
x2->val[x2->count] = myNode->val[pos];

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

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

/* adjusts the given node */
void adjustNode(btreeNode *myNode, int pos) {
if (!pos) {
doLeftShift(myNode, 1);
}
else {
mergeNodes(myNode, 1);
}
}
else {
if (myNode->count != pos) {
if (myNode->link[pos - 1]->count > MIN) {
doRightShift(myNode, pos);
}
else {
if (myNode->link[pos + 1]->count > MIN) {
doLeftShift(myNode, pos + 1);
}
else {
mergeNodes(myNode, pos);
}
}
}
else {
if (myNode->link[pos - 1]->count > MIN)
doRightShift(myNode, pos);
else
mergeNodes(myNode, pos);
}
}
}

/* delete val from the node */
int delValFromNode(int val,btreeNode *myNode) {
int pos, flag = 0;
if (myNode) {
if (val < myNode->val) {
pos = 0;
flag = 0;
}
else {
for (pos = myNode->count;
(val < myNode->val[pos] && pos > 1); pos--);
if (val == myNode->val[pos]) {
flag = 1;
}
else {
flag = 0;
}
}
if (flag) {
copySuccessor(myNode, pos);
if (flag == 0) {
cout<<"Given data is not present in B-Tree\n";
}
}
else {
removeVal(myNode, pos);
}
}
else {
}
}
}
return flag;
}

/* delete val from B-tree */
void deletion(int val,btreeNode *myNode) {
btreeNode *tmp;
if (!delValFromNode(val, myNode)) {
cout<<"Given value is not present in B-Tree\n";
return;
}
else {
if (myNode->count == 0) {
tmp = myNode;
free(tmp);
}
}
root = myNode;
return;
}

/* search val in B-Tree */
void searching(int val, int *pos,btreeNode *myNode) {
if (!myNode) {
return;
}

if (val < myNode->val) {
*pos = 0;
}
else {
for (*pos = myNode->count;
(val < myNode->val[*pos] && *pos > 1); (*pos)--);
if (val == myNode->val[*pos]) {
cout << "Given data is Found\n";
return;
}
}
return;
}

/* B-Tree Traversal */
void traversal(btreeNode *myNode) {
int i;
if (myNode) {
for (i = 0; i < myNode->count; i++) {
cout << myNode->val[i + 1] << ' ';
}
}
}

int main() {
int val, opt;
while (true) {
cout<<"1. Insertion\t2. Deletion\n";
cout<<"3. Searching\t4. Traversal\n";
cin >> opt;
cout << endl;
switch (opt) {
case 1:
cin >> val;
insertion(val);
break;
case 2:
cout<<"Enter the element to delete:";
cin >> val;
deletion(val, root);
break;
case 3:
cout<<"Enter the element to search:";
cin >> val;
searching(val, &opt, root);
break;
case 4:
traversal(root);
break;
case 5:
exit(0);
}
cout << endl;
}

// system("pause");
}
}
`````` 