多路樹

多路樹是指可以有超過兩個子樹的樹。如果一個多路樹最多有 m 個子樹，那麼這個樹被稱為 m 階多路樹（或 m 路樹）。

與已經研究過的其他樹一樣，m 階多路樹中的節點將由 m-1 個鍵欄位和指向子樹的指標組成。

5 階多路樹

為了讓 m 階多路樹的處理更容易，會在每個節點的鍵上施加某種約束或順序，從而形成 m 階多路搜尋樹（或 m 路搜尋樹）。根據定義，m 階多路搜尋樹是一種 m 路樹，應該滿足以下條件：

• 每個節點與 m 個子樹和 m-1 個鍵欄位相關聯
• 每個節點中的鍵按升序排列。
• 前 j 個子樹中的鍵小於第 j 個鍵。
• 後 m-j 個子樹中的鍵高於第 j 個鍵。

Arnab Chakraborty

更新日期：2020 年 1 月 3 日

13K+ 次瀏覽

開啟你的職業生涯

完成課程後即可獲得證書

開始