2-3樹 - 分裂難度

我的任務是創建一棵2-3樹。我已經完成了必要的所有必要的課程和方法，但是我的拆分方法存在困難。我可能已經過度地表達了這種想法，而我的腦袋正在旋轉，我似乎無法擺脫自己陷入的思路。2-3樹 - 分裂難度

如果我只需要分裂一個葉節點，我就沒有問題。我的思想似乎被卡住的地方是我必須拆分葉節點，然後拆分上面的父節點。根據我的理解，分開孩子，然後分開，然後連接孩子將根據哪個孩子最初分裂而有所不同。

即，如果我有以下樹，我的第一個分裂發生在葉節點（比如根的第二個孩子的第三個孩子13 | 14）。這種分裂的過程與說根的第三個孩子（19,20）的第一個孩子不同。

          9 |18 
      3 | 6       12 | 15       21 | 24 
1 | 2 4 | 5 7 | 8  10 | 11 13 | 14 16 | 17  19 | 20 22 | 23 25 |26

，我有問題我的分裂法的部分是：

if (upperRight != null) 
    { 
     if (childIndex == 0) 
     { 
      parent.connectChild(1, newRight); 
      newRight.connectChild(0, child1); 
      newRight.connectChild(1, child2); 
     } 
     else if (childIndex == 1) 
     { 
      upperRight.connectChild(0, newRight); 
     } 
     else if (childIndex == 2) 
     { 
      upperRight.connectChild(0, newRight); 
     } 
    } 
    else 
    { 
     Node temp = parent.disconnectChild(1); 
     parent.connectChild(1, newRight); 
     parent.connectChild(2, temp); 

     if (childIndex == 0) 
     { 
      temp = newRight.disconnectChild(0); 
      newRight.connectChild(0, child1); 
      newRight.connectChild(1, child2); 
      newRight.connectChild(2, temp); 
     } 
     else if (childIndex == 1) 
     { 
      thisNode.connectChild(1, child1); 
      newRight.connectChild(1, child2); 
     } 
     else if (childIndex == 2) 
     { 
      temp = newRight.disconnectChild(0); 
      thisNode.connectChild(1, child1); 
      newRight.connectChild(0, child2); 
      newRight.connectChild(1, temp); 
     } 
    } 
    return newRight;

如果有人可以幫助我直接就如何看待這個區別我將不勝感激。我收到的輸出要麼是我的孩子以不正確的順序，要麼是我覆蓋了一些孩子，或者兩者都有。

來源

2012-08-11 NYC Canuck

在Robert Sedgwich的算法的Balanced Search Trees中討論了使用四節點來幫助分裂的技術。

來源

2013-06-06 00:35:58

2-3樹 - 分裂難度

回答

相關問題