刪除從乙樹中的節點

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你這樣做，即使在特定的情況下，您可能沒有到對面。