當前位置:聚美館>智慧生活>心理>

m階B樹是幾叉平衡樹

心理 閱讀(2.81W)
m階B樹是幾叉平衡樹

m取幾就是幾叉平衡

描述一顆 B樹時需要指定它的階數,階數表示了一個結點 最多 有多少個孩子結點,一般用字母 M 表示階數。

當 M取 2 時,就是我們常見的二叉搜尋樹。

而B樹,根結點的階數M >= 2(至少有兩個子節點),其他節點數必須 >= 3 。

其實,M階 就是 M樹。

一顆 M樹上,最多有 M 個子樹。例如

2(叉)樹,即內含 1個數據項 和 2 個子樹(這裏的子樹 也叫做 引用、連結等)

3(叉)樹,即內含 2個數據項 和 3 個子樹

4(叉)樹,即內含 3個數據項 和 4 個子樹

5(叉)樹,即內含 4個數據項 和 5 個子樹

故,M(叉)樹,即內含(M-1)個數據項 和 M 個子樹

所以,M階 可理解爲 M(叉)樹,即內含(M-1)個數據項和 M 個子樹。

注意:

在B樹中,M>=3,所以B樹至少是 3(叉)樹(不太嚴謹的說法)

M階,確切的是指 平衡的 M 路查找樹 。