m叉樹

在計算機科學中，m叉樹定義為節點的集合，通常以如下層次結構方式表示。

• 樹從根節點開始。
• 樹的每個節點都維護一個指向其子節點的指標列表。
• 子節點的數量小於或等於m。

m叉樹的典型表示實現了一個包含m個引用（或指標）的陣列來儲存子節點（注意，m是子節點數量的上限）。

m路搜尋樹

a. 為空，或者

b. 由包含b (1<=b<m) 個鍵kb的根節點和一組子樹Ta (a = 0..b) 組成，使得

• 如果k是T0中的鍵，則k <= k1
• 如果k是Ta (0<a<b) 中的鍵，則ka <= k <= ka+1
• 如果k是Tb中的鍵，則k > kb，並且
• 所有Ta都是非空的m路搜尋樹，或者所有Ta都是空的

m叉樹影像

與n個節點相關的完全m叉樹的高度為ceiling(log_mn)。

m階B樹是m路樹，其中

a. 所有葉子都應該在同一層，並且

b. 除根節點和葉子節點外的所有節點至少有m/2個子節點，最多有m個子節點。根節點至少有2個子節點，最多有m個子節點。

Arnab Chakraborty

更新於：2020年1月2日

2K+ 瀏覽量

開啟你的職業生涯

完成課程獲得認證

開始學習