有点迷糊的 B 树 delete 操作

本文主要是介绍有点迷糊的 B 树 delete 操作，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1. 如果键 $k$ 在节点 $x$ 中，且 $x$ 是叶子节点，则从 $x$ 中删除键 $k$ 。

2. 如果键 $k$ 在节点 $x$ 中，且 $x$ 是内部节点，请执行以下操作：

a. 如果节点 $x$ 中位于 $k$ 之前的子节点 $y$ 至少有 $t$ 个键，则在以 $y$ 为根的子树中找到 $k$ 的前驱值 ${k}'$ 。将 $x$ 中的 $k$ 替换为 ${k}'$ ,并递归地删除 ${k}'$ 。

b. 对称地，如果节点 $x$ 中位于 $k$ 后面的子节点 $z$ 至少有 $t$ 个键，则在以 $z$ 为根的子树中找到 $k$ 的后继值 ${k}'$ 。将 $x$ 中的 $k$ 替换为 ${k}'$ ，并递归地删除 ${k}'$ 。

c. 否则，如果 $y$ 和 $z$ 都只有 $t-1$ 键，那么将 $k$ 和 $z$ 都合并到 $y$ 中，然后，递归地从 $y$ 中删除 $k$ 。

3. 如果键 $k$ 不存在于内部节点 $x$ 中，则确定必须包含 $k$ 的相应子树的根 $c_{i}\left [ x \right ]$ 。如果 $c_{i}\left [ x \right ]$ 只有 $t-1$ 键，则根据需要执行步骤 3a 或 3b，以确保下降到至少包含 $t$ 键的节点。

a. 如果 $c_{i}\left [ x \right ]$ 只有 $t-1$ 个键，但有一个具有 $t$ 个键的兄弟节点，则通过将一个键从 $x$ 向下移动到 $c_{i}\left [ x \right ]$ 中，将一个键从 $c_{i}\left [ x \right ]$ 的左或右同级的兄弟节点中向上移动到 $x$ 中，并将相应的子级从兄弟节点中移动到 $c_{i}\left [ x \right ]$ 中，为 $c_{i}\left [ x \right ]$ 提供一个额外的键。(《算导》上没说明)

b. 如果 $c_{i}\left [ x \right ]$ 和所有 $c_{i}\left [ x \right ]$ 的兄弟节点都只有 $t-1$ 键，则将 $c_{i}$ 与其中一个同级节点合并，并将一个键从 $x$ 向下移动到新的合并节点中，以成为该节点的中间键。

我一开始看得时候，没有分清楚算法中强调“x 是内部节点，但是 k 在其中或者不在其中”这个条件的意义。后来发现，这样说，只是为了方便在节点下降的过程中（搜索 k 的过程中），就已经开始进行 merge 或者 sibling 操作，而不需要等到回溯的过程中进行 merge 和 sibling。

也有回溯版本的，从最底层往上进行 merge 和 sibling 操作：https://www.cnblogs.com/nullzx/p/8729425.html

这篇关于有点迷糊的 B 树 delete 操作的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

原文地址:
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.chinasem.cn/article/1060832。如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈，一经查实，立即删除！我们的邮箱：23002807@qq.com