从 B 树中删除一个节点

Question

最小键数 = 2 最大键数 = 5

                            P

              CL                           TX
       AB    DEJK    NO               QRS    UV    YZ

正在删除密钥 D:

                    CLPTX
       AB    EJK    NO   QRS    UV    YZ

这个答案是根据 Introduction to Algorithms by thomas H . Cormen 页。没有 501

它说：这是情况 3b：递归不能下降到节点 CL，因为它只有 2 个键，所以我们需要将 P 下推并将其与 CL 和 TX 合并以形成 CLPTX the n我们从叶子 (case1)

中删除 D

不过我觉得这个答案也不错：

                            P

              CL                           TX
       AB    EJK    NO               QRS    UV    YZ

因为叶子节点 EJK 仍然有 3 个密钥满足最小密钥约束。

请解释一下。

Answer 1

删除算法是从上到下的，所以不知道叶子够不够。

为了确保算法每次都能正常工作，我们决定合并从顶部开始具有最少密钥（但合法）的单元格。那是因为如果叶子需要 parent 中的 "donation"，他们的 parent 将能够提供它们。

注意：我说 "leaves" 是为了简化事情，但它也适用于沿途的每个单元格。

注意 2：这就是为什么在 insert 中你会做相反的事情，即使在特定情况下你可能不必这样做。

Deleting a node from B tree