Penghapusan dari B-tree

Dalam tutorial ini, Anda akan belajar cara menghapus kunci dari b-tree. Selain itu, Anda akan menemukan contoh kerja menghapus kunci dari pohon-B di C, C ++, Java dan Python.

Menghapus elemen pada pohon-B terdiri dari tiga kejadian utama: mencari node di mana kunci yang akan dihapus berada , menghapus kunci dan menyeimbangkan pohon jika diperlukan.

Saat menghapus pohon, kondisi yang disebut underflow mungkin terjadi. Underflow terjadi ketika sebuah node berisi kurang dari jumlah minimum kunci yang harus dipegangnya.

Istilah yang harus dipahami sebelum mempelajari operasi penghapusan adalah:

Inorder Precessor
Kunci terbesar di sebelah kiri node disebut inorder precessor.
Penerus Inorder
Kunci terkecil di anak kanan node disebut penerus inordernya.

Operasi Penghapusan

Sebelum melalui langkah-langkah di bawah ini, kita harus mengetahui fakta-fakta ini tentang pohon B derajat m .

Sebuah node dapat memiliki maksimal m anak. (yaitu 3)
Sebuah node dapat berisi maksimal m - 1kunci. (yaitu 2)
Sebuah node harus memiliki minimal ⌈m/2⌉anak. (yaitu 2)
Sebuah node (kecuali node root) harus berisi minimal ⌈m/2⌉ - 1kunci. (yaitu 1)

Ada tiga kasus utama untuk operasi penghapusan di pohon B.

Kasus I

Kunci yang akan dihapus terletak di daunnya. Ada dua kasus untuk itu.

Penghapusan kunci tidak melanggar properti jumlah minimum kunci yang harus dimiliki sebuah node.
Pada pohon di bawah, menghapus 32 tidak melanggar properti di atas. Menghapus kunci daun (32) dari B-tree
Penghapusan kunci melanggar properti jumlah minimum kunci yang harus dimiliki sebuah node. Dalam kasus ini, kami meminjam kunci dari simpul saudara tetangga terdekatnya dalam urutan kiri ke kanan.
Pertama, kunjungi saudara kiri langsung. Jika node saudara kiri memiliki lebih dari jumlah kunci minimum, maka pinjam kunci dari node ini.
Jika tidak, centang untuk meminjam dari simpul saudara kanan langsung.
Pada pohon di bawah ini, menghapus 31 hasil dalam kondisi di atas. Mari kita meminjam kunci dari simpul saudara kiri. Menghapus kunci daun (31) Jika kedua simpul saudara langsung sudah memiliki jumlah kunci minimum, gabungkan simpul dengan simpul saudara kiri atau simpul saudara kanan. Penggabungan ini dilakukan melalui node induk.
Menghapus 30 hasil dalam kasus di atas.
Hapus kunci daun (30)

Kasus II

Jika kunci yang akan dihapus terletak di simpul internal, kasus berikut terjadi.

Node internal, yang dihapus, diganti dengan inorder pendahulu jika anak kiri memiliki lebih dari jumlah minimum kunci. Menghapus node internal (33)
Node internal, yang dihapus, diganti dengan penerus inorder jika anak kanan memiliki lebih dari jumlah minimum kunci.
Jika salah satu anak memiliki jumlah kunci yang persis sama, gabungkan anak kiri dan kanan.
Menghapus simpul internal (30) Setelah menggabungkan jika simpul induk memiliki kurang dari jumlah kunci minimum, cari saudara kandung seperti pada Kasus I.

Kasus III

Dalam hal ini, ketinggian pohon menyusut. Jika kunci target terletak di node internal, dan penghapusan kunci menyebabkan jumlah kunci yang lebih sedikit di node tersebut (yaitu kurang dari jumlah minimum yang dibutuhkan), maka cari inorder precessor dan inorder successor. Jika kedua anak memiliki jumlah kunci minimum, maka peminjaman tidak dapat dilakukan. Hal ini mengarah pada Kasus II (3) yaitu penggabungan anak-anak.

Sekali lagi, cari saudara kandung untuk meminjam kunci. Namun, jika saudara kandung juga hanya memiliki jumlah kunci minimum, gabungkan node dengan saudara tersebut bersama dengan induknya. Aturlah anak-anak sesuai (meningkatkan urutan).

Menghapus node internal (10)

Contoh Python, Java dan C / C ++

Python Java 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(); )