Löschen aus einem B-Baum

In diesem Tutorial erfahren Sie, wie Sie einen Schlüssel aus einem B-Baum löschen. Außerdem finden Sie Arbeitsbeispiele zum Löschen von Schlüsseln aus einem B-Baum in C, C ++, Java und Python.

Das Löschen eines Elements in einem B-Baum besteht aus drei Hauptereignissen: Durchsuchen des Knotens, auf dem der zu löschende Schlüssel vorhanden ist , Löschen des Schlüssels und Ausgleichen des Baums, falls erforderlich.

Beim Löschen eines Baums kann eine Bedingung namens Unterlauf auftreten. Ein Unterlauf tritt auf, wenn ein Knoten weniger als die Mindestanzahl von Schlüsseln enthält, die er halten sollte.

Die Begriffe, die vor dem Studium des Löschvorgangs zu verstehen sind, sind:

  1. Inorder-Vorgänger
    Der größte Schlüssel auf dem linken untergeordneten Knoten eines Knotens wird als Inorder-Vorgänger bezeichnet.
  2. Inorder-Nachfolger
    Der kleinste Schlüssel auf dem rechten Kind eines Knotens wird als Inorder-Nachfolger bezeichnet.

Löschvorgang

Bevor Sie die folgenden Schritte ausführen, müssen Sie diese Fakten über einen B-Baum vom Grad m kennen .

  1. Ein Knoten kann maximal m Kinder haben. (dh 3)
  2. Ein Knoten kann maximal m - 1Schlüssel enthalten. (dh 2)
  3. Ein Knoten sollte mindestens untergeordnete Knoten haben ⌈m/2⌉. (dh 2)
  4. Ein Knoten (außer Wurzelknoten) sollte ein Minimum an ⌈m/2⌉ - 1Schlüsseln enthalten. (dh 1)

Es gibt drei Hauptfälle für Löschvorgänge in einem B-Baum.

Fall I.

Der zu löschende Schlüssel liegt im Blatt. Es gibt zwei Fälle dafür.

  1. Das Löschen des Schlüssels verletzt nicht die Eigenschaft der Mindestanzahl von Schlüsseln, die ein Knoten enthalten sollte.
    In der folgenden Baumstruktur verletzt das Löschen von 32 die oben genannten Eigenschaften nicht. Löschen eines Blattschlüssels (32) aus dem B-Baum
  2. Das Löschen des Schlüssels verletzt die Eigenschaft der Mindestanzahl von Schlüsseln, die ein Knoten enthalten sollte. In diesem Fall leihen wir einen Schlüssel von seinem unmittelbar benachbarten Geschwisterknoten in der Reihenfolge von links nach rechts aus.
    Besuchen Sie zuerst das unmittelbare linke Geschwister. Wenn der linke Geschwisterknoten mehr als eine Mindestanzahl von Schlüsseln hat, leihen Sie sich einen Schlüssel von diesem Knoten aus.
    Überprüfen Sie andernfalls, ob Sie vom unmittelbaren rechten Geschwisterknoten etwas ausleihen möchten.
    Im folgenden Baum führt das Löschen von 31 zu der obigen Bedingung. Lassen Sie uns einen Schlüssel vom linken Geschwisterknoten ausleihen. Löschen eines Blattschlüssels (31) Wenn beide unmittelbaren Geschwisterknoten bereits eine Mindestanzahl von Schlüsseln haben, führen Sie den Knoten entweder mit dem linken Geschwisterknoten oder dem rechten Geschwisterknoten zusammen. Diese Zusammenführung erfolgt über den übergeordneten Knoten.
    Das Löschen von 30 Ergebnissen im obigen Fall.
    Lösche einen Blattschlüssel (30)

Fall II

Wenn der zu löschende Schlüssel im internen Knoten liegt, treten die folgenden Fälle auf.

  1. Der interne Knoten, der gelöscht wird, wird durch einen ungeordneten Vorgänger ersetzt, wenn das linke Kind mehr als die Mindestanzahl von Schlüsseln hat. Löschen eines internen Knotens (33)
  2. Der interne Knoten, der gelöscht wird, wird durch einen Inorder-Nachfolger ersetzt, wenn das richtige Kind mehr als die Mindestanzahl von Schlüsseln hat.
  3. Wenn eines der Kinder genau eine Mindestanzahl von Schlüsseln hat, führen Sie das linke und das rechte Kind zusammen.
    Löschen eines internen Knotens (30) Suchen Sie nach dem Zusammenführen nach den Geschwistern wie in Fall I, wenn der übergeordnete Knoten weniger als die Mindestanzahl von Schlüsseln aufweist.

Fall III

In diesem Fall schrumpft die Höhe des Baumes. Wenn der Zielschlüssel in einem internen Knoten liegt und das Löschen des Schlüssels zu einer geringeren Anzahl von Schlüsseln im Knoten führt (dh weniger als das erforderliche Minimum), suchen Sie nach dem Inorder-Vorgänger und dem Inorder-Nachfolger. Wenn beide Kinder eine Mindestanzahl von Schlüsseln enthalten, kann keine Ausleihe erfolgen. Dies führt zu Fall II (3), dh zur Verschmelzung der Kinder.

Suchen Sie erneut nach dem Geschwister, um einen Schlüssel auszuleihen. Wenn das Geschwister jedoch auch nur eine Mindestanzahl von Schlüsseln hat, führen Sie den Knoten mit dem Geschwister zusammen mit dem übergeordneten Knoten zusammen. Ordnen Sie die Kinder entsprechend an (aufsteigende Reihenfolge).

Löschen eines internen Knotens (10)

Beispiele für Python, Java und 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(); )

Löschkomplexität

Bester Fall Zeitkomplexität: Θ(log n)

Durchschnittlicher Fall Raumkomplexität: Θ(n)

Worst case Raumkomplexität: Θ(n)

Interessante Beiträge...