删除从乙树中的节点

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 n我们删除D从叶（情形）

，但我认为这个答案也蛮好：

      P 

       CL       TX 
     AB EJK NO    QRS UV YZ 

因为叶节点EJK还有3个键满足分钟关键constrainsts。

请解释一下。

Answer 1

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

，以确保该算法屡试不爽，因此决定，对具有沿着从顶部的方式最小键（但合法）的细胞，将被合并。那是因为如果叶子需要父母的“捐赠”，他们的父母将能够提供。

注：我说：“叶子”，以简化的东西，但它也适用于沿途的每一个细胞。

注2：这就是为什么在insert你这样做，即使在特定的情况下，您可能没有到对面。