B树 学习笔记3 - 从B树上中删除关键字

接上，算法导论 - 18.3 从B树中删除关键字
这一节没有给出伪代码，写起来怕是会有坑，放点参考：
https://www.youtube.com/watch?v=svfnVhJOfMc
https://www.geeksforgeeks.org/b-tree-set-3delete/ (含代码)
$$
在删除关键字时，要重新安排这个结点的孩子，并且必须保证一个结点不会再删除期间变得太小。
$$
过程 B-TREE-DELETE 从以 x$x$ 为根的子树中删除关键字 k$k$ 。
我们设计的这个过程必须保证，无论何时，结点 x$x$ 递归调用自身时， x$x$ 中关键字个数至少为 t$t$ (即比最少要求多一个以上)。
$$
这个加强的条件使得将一个关键字删除时，可以不用向上回溯(有一个例外，稍后解释)。
$$
B-TREE-DELETE( x, k$x,k$ ) 过程：
$$
$$1. 如果关键字 k$k$ 有可能在结点 x$x$ 中，并且 x$x$ 是叶结点，若可能则从 x$x$ 中删除 k$k$ 。
$$
$$2. 如果关键字 k$k$ 在结点 x$x$ 中，并且 x$x$ 是内部结点，则做一下操作：
$$$$$$a. 关键字 k$k$ 前的结点 y$y$ ，若 y$y$ 的关键字多于 k$k$ 个，则找出关键字 k$k$ 的前驱 k′$k^{\prime }$ ，递归地删除 k′$k^{\prime }$ ，并在 x$x$ 中用 k′$k^{\prime }$ 替换 k$k$ 。
$$$$$$b. 关键字 k$k$ 后的结点 z$z$ ，若 z$z$ 的关键字多于 k$k$ 个，则找出关键字 k$k$ 的后继 k′$k^{\prime }$ ，递归地删除 k′$k^{\prime }$ ，并在 x$x$ 中用 k′$k^{\prime }$ 替换 k$k$ 。
$$$$$$c. 无法删除，( y, z$y,z$ 结点关键字不能减少)，则将 y, z, k$y,z,k$ 合并，然后释放 z$z$ 并递归地从 y$y$ 中删除 k$k$ 。
$$
$$3. 如果关键字 k$k$ 当前不在内部结点 x$x$ 中，则确定可能包含 k$k$ 的子树的根 x.ci$x.c_i$ 。如果 x.ci$x.c_i$ 只有 t−1$t-1$ 个关键字，必须执行步骤 3a 或 3b 来保证降至一个至少包含 t$t$ 个关键字的结点。然后通过对 x$x$ 的某个合适的子结点进行递归而结束。
$$$$$$a. 如果 x.ci$x.c_i$ 只有 t−1$t-1$ 个关键字，但是它的一个相邻的兄弟至少包含 t$t$ 个关键字，则旋转(若是右兄弟就左旋，左兄弟就右旋)，这样 x.ci$x.c_i$ 就多了一个关键字。
$$$$$$b. 如果 x.ci$x.c_i$ 以及 x.ci$x.c_i$ 的所有相邻兄弟都只包含 t−1$t-1$ 个关键字，则将 x.ci$x.c_i$ 与一个兄弟合并。(即将 x.ci$x.c_i$ 旁边的一个关键字下推，合并到新结点，成为中间关键字)
$$
$$


$$
$$
由于一棵 B树中的大部分结点都在叶结点中，于是预估删除操作经常用于从叶结点中删除关键字。这样 B-TREE-DELETE 过程只要沿树下降一遍即可不需要向上回溯。
然而，当要删除某个内部结点的关键字时，该过程也要沿树下降一趟，但可能还要返回删除关键字的那个结点，以用其前驱或后继来取代被删除的关键字。
$$
$$
删除操作需要 O(h)$O(h)$ 次磁盘操作。所需CPU时间为 O(th)=O(tlogtn)$O(th)=O(tlo{g}_{t}n)$ 。