c++ - 从 B 树中删除一个节点

Question

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

                            P

              CL                           TX
       AB    DEJK    NO               QRS    UV    YZ   

删除键D:

                    CLPTX
       AB    EJK    NO   QRS    UV    YZ  

这个答案是根据 thomas H 的 Introduction to Algorithms 编写的。科尔门页。没有 501

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

但我认为这个答案也很好:

                            P

              CL                           TX
       AB    EJK    NO               QRS    UV    YZ 

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

请解释一下。

Answer 1

删除算法是从上到下进行的，因此无法知道叶子是否足够。

为了确保算法每次都能正常工作，我们决定合并从顶部开始沿途具有最少 key (但合法)的单元格。那是因为如果叶子需要 parent 的“捐赠”，他们的 parent 将能够提供。

注意:我说“叶子”是为了简化事情，但它也适用于沿途的每个细胞。

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