跳去內容

B-樹

出自維基百科，自由嘅百科全書

B-樹係種數據結構，可以話係二元搜尋樹嘅廣義化。

定義

[編輯]
睇埋：樹 (抽象資料類型)

定義上，一樖 m-order 嘅 B-樹係一樖樹型數據，並且有以下嘅特性[1]:Ch. 7.12：

  • 每粒節點頂攏有 m 粒子節點；
  • 每粒唔係葉（葉節點 = 冇子節點嘅節點）唔係根嘅節點有最少 m/2 咁多粒子節點；
  • 如果根節點唔係葉節點，佢就最少 2 粒子節點；
  • 一粒唔係葉、有 c 粒子節點嘅節點，會帶有 c-1 件 search key，啲 search key 會幫手界定啲子樹嘅值要點分割；
  • 啲葉節點冚唪唥都喺同一層。

好似下圖就係一樖 m = 5 嘅 B-樹。

睇埋

[編輯]

參考資料

[編輯]
  1. ↑ John Bullinaria, (2019). Lecture Notes for Data Structures and Algorithms (PDF). School of Computer Science, University of Birmingham.
 B-樹係電算楔位文，你可以編輯佢充實內容。
由「https://zh-yue.wikipedia.org/w/index.php?title=B-樹&oldid=2117054」收