排序數組2-4 +樹的線性時間

Question

我需要以下問題有所幫助：

描述給定大小爲n的有序陣列構建了一個2-4 +樹包含 相同的密鑰的算法作爲數組。該算法應該在時間O（n）上運行。

我已經知道如何在線性時間內從有序數組中構建紅黑樹（因爲插入後修復樹的函數的分攤時間爲O（1））。

但是，我沒有看到這個技巧如何幫助我使用2-4 +樹： 與插入這些樹之後的攤銷固定時間有什麼關係？ （我不知道它是什麼...）

還是我完全錯了？順便說一下，我不能使用我們在O（n）中從紅黑樹構造2-4樹的類中看到的技巧，它必須是一個簡單的數組，以2-4 +樹算法。

在此先感謝

Answer 1

紅/黑樹和2-3-4 B樹之間有密切的聯繫。實際上，兩者是彼此等距的，這意味着任何2-3-4B樹可以被編碼爲紅黑樹，反之亦然。 This older question討論細節。

使用此連接，您應該能夠調整用於在線性時間內構建一棵紅黑樹的算法，而不是在線性時間構造一個2-3-4 B樹。您可以構建紅黑樹，然後遍歷它以確定要構建的B樹的結構，也可以嘗試更改算法以直接構建B樹。

希望這會有所幫助！