Poisto B-puusta

Tässä opetusohjelmassa opit avaimen poistamisen b-puusta. Löydät myös toimivia esimerkkejä avainten poistamisesta B-puusta C, C ++, Java ja Python.

Elementin poistaminen B-puusta koostuu kolmesta päätapahtumasta: haetaan solmusta, jossa poistettava avain on , avaimen poistamisesta ja puun tasapainottamisesta tarvittaessa.

Puuta poistettaessa voi esiintyä tila, jota kutsutaan alivirtaukseksi . Alivuoto tapahtuu, kun solmu sisältää vähemmän kuin tarvittava avainten vähimmäismäärä.

Ennen poistotoiminnan tutkimista ymmärrettävät termit ovat:

Tilauksen edeltäjä
Solmun vasemman lapsen suurinta avainta kutsutaan sen tilaukseksi.
Tilauksen seuraaja
Solmun oikean lapsen pienintä avainta kutsutaan sen sisäiseksi seuraajaksi.

Poistotoiminto

Ennen kuin käydään läpi alla olevat vaiheet, on tiedettävä nämä tosiasiat m- asteen B-puusta .

Solmussa voi olla enintään m lasta. (eli 3)
Solmu voi sisältää enintään m - 1avaimet. (eli 2)
Solmussa tulisi olla vähintään ⌈m/2⌉lapsia. (eli 2)
Solmun (paitsi juurisolmu) tulee sisältää vähintään ⌈m/2⌉ - 1avaimet. (eli 1)

B-puun poistotoimenpiteitä on kolme päätapausta.

Tapaus I

Poistettava avain on lehdessä. Sille on kaksi tapausta.

Avaimen poistaminen ei riko solmujen pitämän avainten vähimmäismäärän ominaisuutta.
Alla olevan puun 32 poistaminen ei riko yllä mainittuja ominaisuuksia. Lehtiavaimen (32) poistaminen B-puusta
Avaimen poistaminen rikkoo sen avaimen vähimmäismäärän ominaisuutta, jonka solmun tulisi pitää. Tällöin lainamme avaimen välittömältä naapurin sisarussolmulta vasemmalta oikealle -järjestyksessä.
Käy ensin välittömässä vasemmassa sisaruksessa. Jos vasemmassa sisarussolmussa on enemmän kuin vähimmäismäärä avaimia, lainaa avain tältä solmulta.
Muuten tarkista, jos haluat lainata oikealta sisarussolmulta.
Alla olevan puun 31 poistaminen johtaa yllä olevaan ehtoon. Lasketaanpa avain vasemmalta sisarussolmulta. Lehtiavaimen poistaminen (31) Jos molemmilla välittömillä sisarussolmuilla on jo vähimmäismäärä avaimia, yhdistä solmu joko vasempaan sisarussolmuun tai oikeaan sisarussolmuun. Tämä yhdistäminen tapahtuu pääsolmun kautta.
30 poistaminen johtaa edellä mainittuun tapaukseen.
Poista lehtiavain (30)

Tapaus II

Jos poistettava avain on sisäisessä solmussa, tapahtuu seuraavia tapauksia.

Sisäinen solmu, joka poistetaan, korvataan tilatulla edeltäjällä, jos vasemmalla lapsella on enemmän kuin vähimmäismäärä avaimia. Sisäisen solmun poistaminen (33)
Sisäinen solmu, joka poistetaan, korvataan sisäisellä seuraajalla, jos oikealla lapsella on enemmän kuin vähimmäismäärä avaimia.
Jos kummallakin lapsella on täsmälleen vähimmäismäärä avaimia, yhdistä vasen ja oikea lapsi.
Sisäisen solmun poistaminen (30) Yhdistämisen jälkeen, jos vanhemmalla solmulla on vähemmän kuin avainten vähimmäismäärä, etsi sisaruksia kuten tapauksessa I.

Tapaus III

Tällöin puun korkeus kutistuu. Jos kohdeavain on sisäisessä solmussa, ja avaimen poistaminen johtaa solmujen määrään vähemmän (ts. Vähemmän kuin vaadittu vähimmäismäärä), etsi sitten tilaaja edeltäjä ja tilaaja seuraaja. Jos molemmissa lapsissa on vähimmäismäärä avaimia, lainaa ei voida suorittaa. Tämä johtaa tapauksen II (3) eli lasten yhdistämiseen.

Jälleen kerran etsi sisar lainata avain. Mutta jos sisaruksella on myös vain vähimmäismäärä avaimia, yhdistä solmu sisaruksen kanssa vanhemman kanssa. Järjestä lapset vastaavasti (järjestys kasvaa).

Sisäisen solmun poistaminen (10)

Python-, Java- ja C / C ++ -esimerkkejä

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