資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚學
法學資料結構中的 B 樹刪除
接下來，我們將瞭解如何從 B 樹中刪除一個節點。假設我們擁有一個類似於以下內容的 B 樹 −
B 樹示例 −
刪除分為兩部分。首先，我們必須找到該元素。此策略類似於查詢。現在，對於刪除，我們必須注意一些規則。一個節點至少必須有 m/2 個元素。因此，如果我們刪除一個元素，而它的剩餘元素少於 m-1 個，那麼它將自行調整。如果整個節點被刪除，那麼它的子節點將被合併，如果它們的大小與 m 相同，那麼將它們分成兩部分，然後中間值將再次上升。
假設我們要刪除 46。現在有兩個子節點。 [45] 和 [47, 49]，那麼它們將被合併，結果為 [45, 47, 49]，現在 47 出現了。
演算法
BTreeDelete(x, key) −
輸入 - 樹的根，和要刪除的鍵
我們假設鍵存在於列表中
if x is leaf, then delete object with key ‘key’ from x else if x does not contain the object with key ‘key’, then locate the child x->child[i] whose key range is holding ‘key’ y := x->child[i] if y has m/2 elements, then If the sibling node z immediate to the left or right of y, has at least one more object than m/2, add one more object by moving x->key[i] from x to y, and move that last or first object from z to x. If y is non-leaf node, then last or first child pointer in z is also moved to y else any immediate sibling of y has m/2 elements, merge y with immediate sibling end if BTreeDelete(y, key) else if y that precedes ‘key’ in x, has at-least m/2 + 1 objects, then find predecessor k of ‘key’, in the sub-tree rooted by y. then recursively delete k from the sub-tree and replace key with k in x else if ys has m/2 elements, then check the child z, which is immediately follows ‘key’ in x if z has at least m/2+1 elements, then find successor k of ‘key’, in the sub-tree rooted by z. recursively delete k from sub-tree, and replace key with k in x else both y and z has m/2 elements, then merge then into one node, and push ‘key’ down to the new node as well. Recursively delete ‘key’ from this new node end if end if
更新於：2020-08-11
1 千+ 瀏覽
廣告