Chapter 10 2D3樹和2D3D4樹 - Ian-Liu-1990/Data-Structure GitHub Wiki

M-路樹

• 定義 : 可以是空，非空則必須滿足
  1. 所有節點的分支度必須至多M (即每個節點最多有 M 個兒子)
  2. 每個節點有N個關鍵值，K1, K2, K3, ...Kn 並有N+1個子樹A0, A1, A2, ...An且必須成立
     1. 每一個節點上的鍵值必須由小到大排列，K1 ＜ K2＜K3＜ ... ＜Kn, 鍵值順序從1開始
     2. 子樹Ai的所有鍵值均小於鍵值Ki+1但大於Ki
  3. Ai指到的子樹，0 ＜= i ＜= n亦是m-way搜尋樹
  4. 每個節點型態表示為n, A0, (K1, A1), (K2, A2), ...(Kn, An)

B Tree

• 定義 : 是一棵平衡過的 Ｍ 路樹，可以為空，但當高度H＞1必須滿足

  1. Root至少有兩個子節點
  2. Root以外的節點，每個節點至少有Ｍ/2取上限個子樹，至多有Ｍ個子節點
     • 相對節值數 : 至少有Ｍ/2取上限再-1個"鍵值"，至多有M-1個鍵值
  3. 所有樹葉必須在同一層(高度)

• Ｂ樹特性 :

1. Ｂ樹有根樹
2. Ｂ樹有序樹
3. Ｂ樹為平衡樹 : 外部節點，皆在同一層，包括AVL，紅黑，堆積，斜張樹和B Tree
4. 每個葉節點具相同深度／高度
5. 根節點至少２節點
6. 可放一列排序過的資料

• 空間與時間複雜度 :

算法	平均	最差
空間	O(n)	O(n)
搜尋	O(log n)	O(log n；Base : M 路)
插入	O(log n)	O(log n；Base : M 路)
刪除	O(log n)	O(log n；Base : M 路)

2-3樹，2-3-4樹

1. Ｂ樹是一棵ｍ路樹，可以為空Tree

2. 若非空Tree

   1. Root至少兩個子樹
   2. 除了Root之外的節點，每個節點至少有[ｍ／２]_取上限個子樹，至多ｍ個
   3. 所有失敗(Failure)節點必須同高度

3. 一棵Ｍ路樹的最多最少節點數與資料數

   1. 最少和最多節點數 : [(m^h) - 1]/(m-1)，其中最少m = M路/2取上限，最多m = M路，h為Root從高度=1算起

   2. 最少和最多資料個數 : (m^h) - 1，其中最少m = M路/2取上限，最多m = M路，h為Root從高度=1算起

插入，平均與最壞時間Ｏ(ｌｏｇmＮ)

• 45, 30, 40, 65, 68, 60, 70, 50 - 108高考技師
• 插入後，若要分裂將Ｍ/2取上限，由左而右從１～Ｎ數起

刪除，平均與最壞時間Ｏ(ｌｏｇmＮ)

• 刪除葉子上節點

  1. 若葉子節點刪除，不違反每個節點至少有[ｍ／２]_取上限個子樹，至多ｍ個，直接刪除

  2. 違反，檢查左右兄弟是否可借，借了不違反每個節點至少有[ｍ／２]_取上限個子樹，至多ｍ個．父節點向下填補刪除節點，兄弟節點向上填補父節點

  3. 違反且左右兄弟不夠借，父節點與任意左右兄弟向下合併，檢查原父節點所在節點是否違反每個節點至少有[ｍ／２]_取上限個子樹，至多ｍ個

     1. 不違反，不用再調動
     2. 違反 : 反覆2. 3.動作

• 刪除內部節點

  1. 若內部節點刪除，二元搜尋樹，(最大最小都在葉子上)找左子樹對大，或右子樹最小，填補刪除的內部節點

  2. 檢查葉子節點，是否違反每個節點至少有[ｍ／２]_取上限個子樹，至多ｍ個，若否直接刪除

  3. 違反，則依照葉子節點刪除法即可