將2-3樹分成小於和大於給定值X

Question

我需要編寫函數，它接收一些關鍵字x並將2-3樹分割成2到2-3棵樹。在第一棵樹中，所有的節點都比x大，而第二個則小於x。我需要使其複雜度爲O（logn）。先感謝任何想法。

編輯 我想過要在樹上找到關鍵字x。並且在將它的兩棵子樹（如果它們存在的情況下大一些或小一些）分成兩棵樹後開始上升並且每次都檢查我還沒有檢查過的子樹並加入到其中一棵樹中。我的問題是，所有的葉子必須在同一水平。

Answer 1

假設你已經在講座中覆蓋了2-3-4 trees，這裏是一個提示：看看你是否也可以爲2-3棵樹應用相同的插入算法。特別是，使插入始終在葉中開始，然後適當地重構樹。完成後，確定你得到的算法的複雜性。

Answer 2

如果從根移動到您的密鑰和一個點，比關鍵字大，另一個在休息，然後作出更大的節點是你的大的樹的一部分的節點分割每個節點的話，說的有在最高點的最左端的節點（不要修復樹，最後完成），直到你到達密鑰，你將得到你的樹。然後你只需要在你使用的路徑上修復兩棵樹（注意兩棵樹上都存在相同的路徑）。