有点迷糊的 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$ 向下移动到新的合并节点中，以成为该节点的中间键。