在B樹中，當節點分裂時元素被提升

假設有一個8階B樹，這意味着它可以有8個指針和7個元素。假設字母A到G存儲在這個B樹中。所以這個B樹只是一個包含7個元素的單個節點。在B樹中，當節點分裂時元素被提升

然後您嘗試將J插入到樹中。沒有空間，所以你必須拆分節點並創建一個新的根節點。哪個元素被提升到根節點？

來源

2010-04-04 neuromancer

當你要插入在全節點的新元素（2*t - 1鍵）

通過選擇節點的中間鍵（即中間的鍵）
你把它分解產生兩個新來的孩子，每個t-1鍵（根據以前的密鑰分割它）
中值保持在父節點
這樣就可以進行正常插入算法，尋找在那裏你應該把新的元素。

來源

2010-04-04 16:55:26 Jack

根據你的算法，d會在根節點？這本書顯示了e在根節點。 – neuromancer 2010-04-04 20:54:40

基本上，你會有8個元素（A B C D E F G J），所以有兩個「中間」元素。他們中的任何一個（D或E）都可以。傑克的回答談論的是在插入之前預分割節點的情況，這也是可能的，雖然不是必要的（可能在實際插入之前將節點拆分很長時間）。所以書和傑克都不對。 – jpalecek 2010-10-04 23:43:27

在B樹中，當節點分裂時元素被提升

回答

相關問題