Q

插入在2-3-4樹

2013-07-06 35 views 1 likes

1

考慮在其中每個數據項是字母的以下2-3-4樹（即最小二度的B樹）。字母的通常字母排序在構建樹時使用。插入在2-3-4樹

enter image description here

什麼是上述樹插入G的結果呢？

我得到的答案

enter image description here

但在解決關鍵的答案是

enter image description here

誰能解釋如何獲得通過該解決方案提供了關鍵的答案嗎？

2013-07-06 Deepak Mishra

A

回答

2

只要不違反不變量，操作在技術上是有效的。 CLRS中的插入算法會一路分解，所以它會像你一樣分裂根。

但是，另一個實現可能會觀察到第二個孩子是空的，第一個孩子已滿。這意味着可以完成「旋轉」並且根節點數不受影響。輪換涉及將L推入第二個孩子（預先計劃），並將我拉到L的根部前一個位置。現在第一個孩子只有兩個條目，你可以插入它。

Animated insertion using the CLRS method you used

2014-01-19 18:50:40

相關問題