Table of Contents
In this tutorial, you will learn how to delete a key from a b-tree. Also, you will find working examples of deleting keys from a B-tree in C, C++, Java and Python.
Deleting an element on a B-tree consists of three main events: searching the node where the key to be deleted exists, deleting the key and balancing the tree if required.
While deleting a tree, a condition called underflow may occur. Underflow occurs when a node contains less than the minimum number of keys it should hold.
The terms to be understood before studying deletion operation are:
- Inorder Predecessor
The largest key on the left child of a node is called its inorder predecessor. - Inorder Successor
The smallest key on the right child of a node is called its inorder successor.
1. Deletion Operation
Before going through the steps below, one must know these facts about a B tree of degree m.
- A node can have a maximum of m children. (i.e. 3)
- A node can contain a maximum of
m - 1
keys. (i.e. 2) - A node should have a minimum of
⌈m/2⌉
children. (i.e. 2) - A node (except root node) should contain a minimum of
⌈m/2⌉ - 1
keys. (i.e. 1)
There are three main cases for deletion operation in a B tree.
1.1. Case I
The key to be deleted lies in the leaf. There are two cases for it.
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 32 does not violate the above properties.
Deleting a leaf key (32) from B-tree
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 31 results in the above condition. Let us borrow a key from the left sibling node.
Deleting a leaf key (31)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 30 results in the above case.
Delete a leaf key (30)
1.2. Case II
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.Deleting an internal node (33)
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.
Deleting an internal node (30)After merging if the parent node has less than the minimum number of keys then, look for the siblings as in Case I.
1.3. Case III
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. This leads to Case II(3) i.e. merging the children.
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).
2. Python, Java and C/C++ Examples
Source code by Python Language:
# Deleting a key on a B-tree in Python # Btree node class BTreeNode: def __init__(self, leaf=False): self.leaf = leaf self.keys = [] self.child = [] class BTree: def __init__(self, t): self.root = BTreeNode(True) self.t = t # Insert a key def insert(self, k): root = self.root if len(root.keys) == (2 * self.t) - 1: temp = BTreeNode() self.root = temp temp.child.insert(0, root) self.split_child(temp, 0) self.insert_non_full(temp, k) else: self.insert_non_full(root, k) # Insert non full def insert_non_full(self, x, k): i = len(x.keys) - 1 if x.leaf: x.keys.append((None, None)) while i >= 0 and k[0] < x.keys[i][0]: x.keys[i + 1] = x.keys[i] i -= 1 x.keys[i + 1] = k else: while i >= 0 and k[0] < x.keys[i][0]: i -= 1 i += 1 if len(x.child[i].keys) == (2 * self.t) - 1: self.split_child(x, i) if k[0] > x.keys[i][0]: i += 1 self.insert_non_full(x.child[i], k) # Split the child def split_child(self, x, i): t = self.t y = x.child[i] z = BTreeNode(y.leaf) x.child.insert(i + 1, z) x.keys.insert(i, y.keys[t - 1]) z.keys = y.keys[t: (2 * t) - 1] y.keys = y.keys[0: t - 1] if not y.leaf: z.child = y.child[t: 2 * t] y.child = y.child[0: t - 1] # Delete a node def delete(self, x, k): t = self.t i = 0 while i < len(x.keys) and k[0] > x.keys[i][0]: i += 1 if x.leaf: if i < len(x.keys) and x.keys[i][0] == k[0]: x.keys.pop(i) return return if i < len(x.keys) and x.keys[i][0] == k[0]: return self.delete_internal_node(x, k, i) elif len(x.child[i].keys) >= t: self.delete(x.child[i], k) else: if i != 0 and i + 2 < len(x.child): if len(x.child[i - 1].keys) >= t: self.delete_sibling(x, i, i - 1) elif len(x.child[i + 1].keys) >= t: self.delete_sibling(x, i, i + 1) else: self.delete_merge(x, i, i + 1) elif i == 0: if len(x.child[i + 1].keys) >= t: self.delete_sibling(x, i, i + 1) else: self.delete_merge(x, i, i + 1) elif i + 1 == len(x.child): if len(x.child[i - 1].keys) >= t: self.delete_sibling(x, i, i - 1) else: self.delete_merge(x, i, i - 1) self.delete(x.child[i], k) # Delete internal node def delete_internal_node(self, x, k, i): t = self.t if x.leaf: if x.keys[i][0] == k[0]: x.keys.pop(i) return return if len(x.child[i].keys) >= t: x.keys[i] = self.delete_predecessor(x.child[i]) return elif len(x.child[i + 1].keys) >= t: x.keys[i] = self.delete_successor(x.child[i + 1]) return else: self.delete_merge(x, i, i + 1) self.delete_internal_node(x.child[i], k, self.t - 1) # Delete the predecessor def delete_predecessor(self, x): if x.leaf: return x.pop() n = len(x.keys) - 1 if len(x.child[n].keys) >= self.t: self.delete_sibling(x, n + 1, n) else: self.delete_merge(x, n, n + 1) self.delete_predecessor(x.child[n]) # Delete the successor def delete_successor(self, x): if x.leaf: return x.keys.pop(0) if len(x.child[1].keys) >= self.t: self.delete_sibling(x, 0, 1) else: self.delete_merge(x, 0, 1) self.delete_successor(x.child[0]) # Delete resolution def delete_merge(self, x, i, j): cnode = x.child[i] if j > i: rsnode = x.child[j] cnode.keys.append(x.keys[i]) for k in range(len(rsnode.keys)): cnode.keys.append(rsnode.keys[k]) if len(rsnode.child) > 0: cnode.child.append(rsnode.child[k]) if len(rsnode.child) > 0: cnode.child.append(rsnode.child.pop()) new = cnode x.keys.pop(i) x.child.pop(j) else: lsnode = x.child[j] lsnode.keys.append(x.keys[j]) for i in range(len(cnode.keys)): lsnode.keys.append(cnode.keys[i]) if len(lsnode.child) > 0: lsnode.child.append(cnode.child[i]) if len(lsnode.child) > 0: lsnode.child.append(cnode.child.pop()) new = lsnode x.keys.pop(j) x.child.pop(i) if x == self.root and len(x.keys) == 0: self.root = new # Delete the sibling def delete_sibling(self, x, i, j): cnode = x.child[i] if i < j: rsnode = x.child[j] cnode.keys.append(x.keys[i]) x.keys[i] = rsnode.keys[0] if len(rsnode.child) > 0: cnode.child.append(rsnode.child[0]) rsnode.child.pop(0) rsnode.keys.pop(0) else: lsnode = x.child[j] cnode.keys.insert(0, x.keys[i - 1]) x.keys[i - 1] = lsnode.keys.pop() if len(lsnode.child) > 0: cnode.child.insert(0, lsnode.child.pop()) # Print the tree def print_tree(self, x, l=0): print("Level ", l, " ", len(x.keys), end=":") for i in x.keys: print(i, end=" ") print() l += 1 if len(x.child) > 0: for i in x.child: self.print_tree(i, l) B = BTree(3) for i in range(10): B.insert((i, 2 * i)) B.print_tree(B.root) B.delete(B.root, (8,)) print("\n") B.print_tree(B.root)
Source code by Java Language:
// Inserting a key on a B-tree 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(); } }
Source code by C Language:
// Deleting a key from 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 *linker[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->linker[0] = root; newNode->linker[1] = child; return newNode; } // Add value to the node void addValToNode(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->linker[j + 1] = node->linker[j]; j--; } node->item[j + 1] = item; node->linker[j + 1] = child; node->count++; } // Split the 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)->linker[j - median] = node->linker[j]; j++; } node->count = median; (*newNode)->count = MAX - median; if (pos <= MIN) { addValToNode(item, pos, node, child); } else { addValToNode(item, pos - median, *newNode, child); } *pval = node->item[node->count]; (*newNode)->linker[0] = node->linker[node->count]; node->count--; } // Set the value in the node int setValueInNode(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 (setValueInNode(item, pval, node->linker[pos], child)) { if (node->count < MAX) { addValToNode(*pval, pos, node, *child); } else { splitNode(*pval, pval, pos, node, *child, child); return 1; } } return 0; } // Insertion operation void insertion(int item) { int flag, i; struct BTreeNode *child; flag = setValueInNode(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->linker[pos]; for (; dummy->linker[0] != NULL;) dummy = dummy->linker[0]; myNode->item[pos] = dummy->item[1]; } // Remove the value void removeVal(struct BTreeNode *myNode, int pos) { int i = pos + 1; while (i <= myNode->count) { myNode->item[i - 1] = myNode->item[i]; myNode->linker[i - 1] = myNode->linker[i]; i++; } myNode->count--; } // Do right shift void rightShift(struct BTreeNode *myNode, int pos) { struct BTreeNode *x = myNode->linker[pos]; int j = x->count; while (j > 0) { x->item[j + 1] = x->item[j]; x->linker[j + 1] = x->linker[j]; } x->item[1] = myNode->item[pos]; x->linker[1] = x->linker[0]; x->count++; x = myNode->linker[pos - 1]; myNode->item[pos] = x->item[x->count]; myNode->linker[pos] = x->linker[x->count]; x->count--; return; } // Do left shift void leftShift(struct BTreeNode *myNode, int pos) { int j = 1; struct BTreeNode *x = myNode->linker[pos - 1]; x->count++; x->item[x->count] = myNode->item[pos]; x->linker[x->count] = myNode->linker[pos]->linker[0]; x = myNode->linker[pos]; myNode->item[pos] = x->item[1]; x->linker[0] = x->linker[1]; x->count--; while (j <= x->count) { x->item[j] = x->item[j + 1]; x->linker[j] = x->linker[j + 1]; j++; } return; } // Merge the nodes void mergeNodes(struct BTreeNode *myNode, int pos) { int j = 1; struct BTreeNode *x1 = myNode->linker[pos], *x2 = myNode->linker[pos - 1]; x2->count++; x2->item[x2->count] = myNode->item[pos]; x2->linker[x2->count] = myNode->linker[0]; while (j <= x1->count) { x2->count++; x2->item[x2->count] = x1->item[j]; x2->linker[x2->count] = x1->linker[j]; j++; } j = pos; while (j < myNode->count) { myNode->item[j] = myNode->item[j + 1]; myNode->linker[j] = myNode->linker[j + 1]; j++; } myNode->count--; free(x1); } // Adjust the node void adjustNode(struct BTreeNode *myNode, int pos) { if (!pos) { if (myNode->linker[1]->count > MIN) { leftShift(myNode, 1); } else { mergeNodes(myNode, 1); } } else { if (myNode->count != pos) { if (myNode->linker[pos - 1]->count > MIN) { rightShift(myNode, pos); } else { if (myNode->linker[pos + 1]->count > MIN) { leftShift(myNode, pos + 1); } else { mergeNodes(myNode, pos); } } } else { if (myNode->linker[pos - 1]->count > MIN) rightShift(myNode, pos); else mergeNodes(myNode, pos); } } } // Delete a value from the node int delValFromNode(int item, struct BTreeNode *myNode) { int pos, flag = 0; if (myNode) { if (item < myNode->item[1]) { pos = 0; flag = 0; } else { for (pos = myNode->count; (item < myNode->item[pos] && pos > 1); pos--) ; if (item == myNode->item[pos]) { flag = 1; } else { flag = 0; } } if (flag) { if (myNode->linker[pos - 1]) { copySuccessor(myNode, pos); flag = delValFromNode(myNode->item[pos], myNode->linker[pos]); if (flag == 0) { printf("Given data is not present in B-Tree\n"); } } else { removeVal(myNode, pos); } } else { flag = delValFromNode(item, myNode->linker[pos]); } if (myNode->linker[pos]) { if (myNode->linker[pos]->count < MIN) adjustNode(myNode, pos); } } return flag; } // Delete operaiton void delete (int item, struct BTreeNode *myNode) { struct BTreeNode *tmp; if (!delValFromNode(item, myNode)) { printf("Not present\n"); return; } else { if (myNode->count == 0) { tmp = myNode; myNode = myNode->linker[0]; free(tmp); } } root = myNode; return; } void searching(int item, int *pos, struct BTreeNode *myNode) { if (!myNode) { return; } if (item < myNode->item[1]) { *pos = 0; } else { for (*pos = myNode->count; (item < myNode->item[*pos] && *pos > 1); (*pos)--) ; if (item == myNode->item[*pos]) { printf("%d present in B-tree", item); return; } } searching(item, pos, myNode->linker[*pos]); return; } void traversal(struct BTreeNode *myNode) { int i; if (myNode) { for (i = 0; i < myNode->count; i++) { traversal(myNode->linker[i]); printf("%d ", myNode->item[i + 1]); } traversal(myNode->linker[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); delete (20, root); printf("\n"); traversal(root); }
Source code by C++ Language:
// Deleting a key from a B-tree in C++ #include <iostream> using namespace std; class BTreeNode { int *keys; int t; BTreeNode **C; int n; bool leaf; public: BTreeNode(int _t, bool _leaf); void traverse(); int findKey(int k); void insertNonFull(int k); void splitChild(int i, BTreeNode *y); void deletion(int k); void removeFromLeaf(int idx); void removeFromNonLeaf(int idx); int getPredecessor(int idx); int getSuccessor(int idx); void fill(int idx); void borrowFromPrev(int idx); void borrowFromNext(int idx); void merge(int idx); friend class BTree; }; class BTree { BTreeNode *root; int t; public: BTree(int _t) { root = NULL; t = _t; } void traverse() { if (root != NULL) root->traverse(); } void insertion(int k); void deletion(int k); }; // B tree node BTreeNode::BTreeNode(int t1, bool leaf1) { t = t1; leaf = leaf1; keys = new int[2 * t - 1]; C = new BTreeNode *[2 * t]; n = 0; } // Find the key int BTreeNode::findKey(int k) { int idx = 0; while (idx < n && keys[idx] < k) ++idx; return idx; } // Deletion operation void BTreeNode::deletion(int k) { int idx = findKey(k); if (idx < n && keys[idx] == k) { if (leaf) removeFromLeaf(idx); else removeFromNonLeaf(idx); } else { if (leaf) { 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]->deletion(k); else C[idx]->deletion(k); } return; } // Remove from the leaf void BTreeNode::removeFromLeaf(int idx) { for (int i = idx + 1; i < n; ++i) keys[i - 1] = keys[i]; n--; return; } // Delete from non leaf node void BTreeNode::removeFromNonLeaf(int idx) { int k = keys[idx]; if (C[idx]->n >= t) { int pred = getPredecessor(idx); keys[idx] = pred; C[idx]->deletion(pred); } else if (C[idx + 1]->n >= t) { int succ = getSuccessor(idx); keys[idx] = succ; C[idx + 1]->deletion(succ); } else { merge(idx); C[idx]->deletion(k); } return; } int BTreeNode::getPredecessor(int idx) { BTreeNode *cur = C[idx]; while (!cur->leaf) cur = cur->C[cur->n]; return cur->keys[cur->n - 1]; } int BTreeNode::getSuccessor(int idx) { BTreeNode *cur = C[idx + 1]; while (!cur->leaf) cur = cur->C[0]; return cur->keys[0]; } void BTreeNode::fill(int idx) { if (idx != 0 && C[idx - 1]->n >= t) borrowFromPrev(idx); else if (idx != n && C[idx + 1]->n >= t) borrowFromNext(idx); else { if (idx != n) merge(idx); else merge(idx - 1); } return; } // Borrow from previous void BTreeNode::borrowFromPrev(int idx) { BTreeNode *child = C[idx]; BTreeNode *sibling = C[idx - 1]; for (int i = child->n - 1; i >= 0; --i) child->keys[i + 1] = child->keys[i]; if (!child->leaf) { for (int i = child->n; i >= 0; --i) child->C[i + 1] = child->C[i]; } child->keys[0] = keys[idx - 1]; if (!child->leaf) 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 BTreeNode::borrowFromNext(int idx) { BTreeNode *child = C[idx]; BTreeNode *sibling = C[idx + 1]; child->keys[(child->n)] = keys[idx]; if (!(child->leaf)) 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) { for (int i = 1; i <= sibling->n; ++i) sibling->C[i - 1] = sibling->C[i]; } child->n += 1; sibling->n -= 1; return; } // Merge void BTreeNode::merge(int idx) { BTreeNode *child = C[idx]; BTreeNode *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) { 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 BTreeNode(t, true); root->keys[0] = k; root->n = 1; } else { if (root->n == 2 * t - 1) { BTreeNode *s = new BTreeNode(t, false); s->C[0] = root; s->splitChild(0, root); int i = 0; if (s->keys[0] < k) i++; s->C[i]->insertNonFull(k); root = s; } else root->insertNonFull(k); } } // Insertion non full void BTreeNode::insertNonFull(int k) { int i = n - 1; if (leaf == 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]->insertNonFull(k); } } // Split child void BTreeNode::splitChild(int i, BTreeNode *y) { BTreeNode *z = new BTreeNode(y->t, y->leaf); z->n = t - 1; for (int j = 0; j < t - 1; j++) z->keys[j] = y->keys[j + t]; if (y->leaf == 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 BTreeNode::traverse() { int i; for (i = 0; i < n; i++) { if (leaf == false) C[i]->traverse(); cout << " " << keys[i]; } if (leaf == false) C[i]->traverse(); } // Delete Operation void BTree::deletion(int k) { if (!root) { cout << "The tree is empty\n"; return; } root->deletion(k); if (root->n == 0) { BTreeNode *tmp = root; if (root->leaf) 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(15); t.insertion(16); t.insertion(17); t.insertion(18); t.insertion(20); t.insertion(23); cout << "The B-tree is: "; t.traverse(); t.deletion(20); cout << "\nThe B-tree is: "; t.traverse(); }
3. Deletion Complexity
Best case Time complexity: Θ(log n)
Average case Space complexity: Θ(n)
Worst case Space complexity: Θ(n)