V tomto výučbe sa dozviete, ako odstrániť kľúč z b-stromu. Nájdete tiež pracovné príklady odstránenia kľúčov z B-stromu v jazykoch C, C ++, Java a Python.
Vymazanie prvku na B-strome pozostáva z troch hlavných udalostí: prehľadanie uzla, kde existuje kľúč, ktorý sa má vymazať , vymazanie kľúča a vyváženie stromu, ak je to potrebné.
Počas mazania stromu môže dôjsť k stavu nazývanému podtečenie . K podtečeniu dochádza, keď uzol obsahuje menej ako minimálny počet kľúčov, ktoré by mal obsahovať.
Pojmy, ktorým je potrebné porozumieť pred štúdiom operácie odstránenia, sú:
- Inorder Predchodca
Najväčší kľúč na ľavom potomku uzla sa nazýva jeho predchodca. - Nevyhnutného nástupca
Najmenší tlačidlo na pravej dieťa uzla sa nazýva jeho nevyhnutného nástupcu.
Operácia vymazania
Predtým, ako prejdete nasledujúcimi krokmi, musíte vedieť tieto fakty o strome B stupňa m .
- Uzol môže mať najviac m detí. (tj. 3)
- Uzol môže obsahovať najviac
m - 1kľúčov. (tj. 2) - Uzol by mal mať minimum
⌈m/2⌉detí. (tj. 2) - Uzol (okrem koreňového) by mal obsahovať minimum
⌈m/2⌉ - 1kľúčov. (tj. 1)
Existujú tri hlavné prípady operácie odstránenia v strome B.
Prípad I
Kľúč, ktorý sa má vymazať, leží v liste. Existujú dva prípady.
- Vymazanie kľúča neporušuje vlastnosť minimálneho počtu kľúčov, ktoré by uzol mal obsahovať.
Odstránenie 32 v strome nižšie neporuší vyššie uvedené vlastnosti.
Vymazanie listového kľúča (32) z B-stromu - Vymazanie kľúča porušuje vlastnosť minimálneho počtu kľúčov, ktoré by uzol mal obsahovať. V takom prípade si požičiame kľúč od jeho bezprostredne susedného súrodeneckého uzla v poradí zľava doprava.
Najskôr navštívte bezprostredného ľavého súrodenca. Ak má uzol ľavého súrodenca viac ako minimálny počet kľúčov, potom si kľúč z tohto uzla požičajte.
Inak začiarknite políčko, aby ste si požičali od pravého súrodeneckého uzla.
Odstránenie 31 v strome nižšie spôsobí vyššie uvedený stav. Požičajme si kľúč od ľavého súrodeneckého uzla.
Vymazanie listového kľúča (31) Ak obidva uzly bezprostredného súrodenca už majú minimálny počet kľúčov, zlúčte uzol buď s ľavým súrodeneckým uzlom, alebo s pravým uzlom súrodenca. Toto zlúčenie sa vykonáva prostredníctvom nadradeného uzla.
Vo vyššie uvedenom prípade bude odstránených 30 výsledkov.
Vymazať listový kľúč (30)
Prípad II
Ak kľúč, ktorý sa má vymazať, leží vo vnútornom uzle, nastanú nasledujúce prípady.
- Interný uzol, ktorý sa odstráni, sa nahradí predchodcom inorder, ak má ľavé dieťa viac ako minimálny počet kľúčov.
Vymazanie interného uzla (33) - Interný uzol, ktorý sa odstráni, sa nahradí následným radením, ak má správne dieťa viac ako minimálny počet kľúčov.
- Ak má ktorékoľvek dieťa presne minimálny počet kľúčov, zlúčte ľavé a pravé dieťa.
Vymazanie interného uzla (30) Ak má rodičovský uzol menej ako minimálny počet kľúčov, po zlúčení vyhľadajte súrodencov ako v prípade I.
Prípad III
V takom prípade sa výška stromu zmenší. Ak cieľový kľúč leží vo vnútornom uzle a vymazanie kľúča vedie k menšiemu počtu kľúčov v uzle (tj k menšiemu ako požadovanému minimu), vyhľadajte predchodcu poradia a následníka poradia. Ak obe deti obsahujú minimálny počet kľúčov, nemožno si požičať. To vedie k prípadu II (3), tj k zlúčeniu detí.
Opäť hľadajte súrodenca, ktorý si požičia kľúč. Ak má ale súrodenec tiež len minimálny počet kľúčov, zlúčte uzol so súrodencom spolu s rodičom. Podľa toho usporiadajte deti (narastajúce poradie).
Odstránenie interného uzla (10)
Príklady jazyka Python, Java a 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(); )
Zložitosť odstránenia
Najlepší prípad Časová zložitosť: Θ(log n)
Priemerná zložitosť priestoru: Θ(n)
Najhorší prípad Zložitosť priestoru: Θ(n)
