数据结构
网络
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 千+ 浏览
广告