Изтриване от B-дърво

В този урок ще научите как да изтриете ключ от b-дърво. Също така ще намерите работещи примери за изтриване на ключове от B-дърво в C, C ++, Java и Python.

Изтриването на елемент от B-дърво се състои от три основни събития: търсене на възела, където съществува ключът за изтриване , изтриване на ключа и балансиране на дървото, ако е необходимо.

Докато изтривате дърво, може да възникне състояние, наречено underflow . Подточването възниква, когато възел съдържа по-малко от минималния брой ключове, които трябва да съдържа.

Термините, които трябва да се разберат преди изучаването на операцията по изтриване, са:

Inorder предшественик
Най-големият ключ от лявото дъщерно устройство на възел се нарича негов предшественик inorder.
Inorder наследник
Най-малкият ключ от дясното дете на възел се нарича негов наследник inorder.

Операция по изтриване

Преди да преминете през стъпките по-долу, трябва да знаете тези факти за B дърво на степен m .

Възел може да има максимум m деца. (т.е. 3)
Възелът може да съдържа максимум m - 1ключове. (т.е. 2)
Възелът трябва да има минимум ⌈m/2⌉деца. (т.е. 2)
Възел (с изключение на коренния възел) трябва да съдържа минимум ⌈m/2⌉ - 1ключове. (т.е. 1)

Има три основни случая на операция за изтриване в B дърво.

Дело I

Ключът, който трябва да бъде изтрит, се намира в листа. Има два случая за това.

Изтриването на ключа не нарушава свойството на минималния брой ключове, които един възел трябва да съдържа.
В дървото по-долу изтриването на 32 не нарушава горните свойства. Изтриване на листен ключ (32) от B-дърво
Изтриването на ключа нарушава свойството на минималния брой ключове, които един възел трябва да съдържа. В този случай ние взаимстваме ключ от непосредствения съседен братовъзлов възел в реда отляво надясно.
Първо посетете непосредствения ляв брат или сестра. Ако левият възел на сестра има повече от минимален брой ключове, вземете ключ от този възел.
В противен случай проверете дали да вземете назаем от непосредствения десен възел.
В дървото по-долу изтриването на 31 води до горното състояние. Нека заемем ключ от левия възел на сестра. Изтриване на листен ключ (31) Ако и двата непосредствени съседни възела вече имат минимален брой ключове, тогава обединете възела или с левия възел, или с десния възел. Това обединяване се извършва чрез родителския възел.
Изтриването на 30 резултата в горния случай.
Изтриване на листен ключ (30)

Дело II

Ако ключът, който трябва да бъде изтрит, се намира във вътрешния възел, възникват следните случаи.

Вътрешният възел, който се изтрива, се заменя с предшественик inorder, ако лявото дете има повече от минималния брой ключове. Изтриване на вътрешен възел (33)
Вътрешният възел, който се изтрива, се заменя с наследник по ред, ако правилното дете има повече от минималния брой ключове.
Ако някое дете има точно минимален брой ключове, обединете лявото и дясното деца.
Изтриване на вътрешен възел (30) След сливането, ако родителският възел има по-малко от минималния брой ключове, потърсете братята и сестрите, както в случай I.

Дело III

В този случай височината на дървото се свива. Ако целевият ключ се намира във вътрешен възел и изтриването на ключа води до по-малък брой ключове във възела (т.е. по-малко от минимално необходимия), тогава потърсете предшественика inorder и наследника на inorder. Ако и двете деца съдържат минимален брой ключове, заемането не може да стане. Това води до случай II (3), т.е. сливане на децата.

Отново потърсете брат или сестра, за да заемете ключ. Но ако братът и сестрят също имат само минимален брой ключове, обединете възела с брат или сестра заедно с родителя. Подредете децата по съответния начин (увеличаване на реда).

Изтриване на вътрешен възел (10)

Примери за Python, Java и C / C ++

Python Java C C ++

 # 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)  = 0 and 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 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 = t: self.delete(x.child(i), k) else: if i != 0 and i + 2 = 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 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("") B.print_tree(B.root)

 // 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 = 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  = 0 && 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 = 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 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 = 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 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 st) ( int i = 0; for (i = 0; i < x.n && 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(); ) )

 // Deleting a key from a B-tree in C #include #include #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 item(j - median) = node->item(j); (*newNode)->linker(j - median) = node->linker(j); j++; ) node->count = median; (*newNode)->count = MAX - median; if (pos 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 item(1)) ( pos = 0; ) else ( for (pos = node->count; (item item(pos) && pos> 1); pos--) ; if (item == node->item(pos)) ( printf("Duplicates not allowed"); return 0; ) ) if (setValueInNode(item, pval, node->linker(pos), child)) ( if (node->count 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 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 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 count) ( x2->count++; x2->item(x2->count) = x1->item(j); x2->linker(x2->count) = x1->linker(j); j++; ) j = pos; while (j 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 item(1)) ( pos = 0; flag = 0; ) else ( for (pos = myNode->count; (item 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"); ) ) else ( removeVal(myNode, pos); ) ) else ( flag = delValFromNode(item, myNode->linker(pos)); ) if (myNode->linker(pos)) ( if (myNode->linker(pos)->count 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 item(1)) ( *pos = 0; ) else ( for (*pos = myNode->count; (item 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 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(""); traversal(root); )

 // Deleting a key from a B-tree in C++ #include 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  deletion(k); else C(idx)->deletion(k); ) return; ) // Remove from the leaf void BTreeNode::removeFromLeaf(int idx) ( for (int i = idx + 1; i 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 n; ++i) sibling->keys(i - 1) = sibling->keys(i); if (!sibling->leaf) ( for (int i = 1; i 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 n; ++i) child->keys(i + t) = sibling->keys(i); if (!child->leaf) ( for (int i = 0; i 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 += 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) 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) 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 keys(j) = y->keys(j + t); if (y->leaf == false) ( for (int j = 0; j 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 traverse(); cout << " " 
 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 << "The B-tree is: "; t.traverse(); )