B樹和紅黑樹

1.B樹

2.B樹和紅黑樹的關系

3.紅黑樹

1.B樹

B樹是一種平衡的多路搜尋樹，多用于檔案系統、資料庫的實作

1.1特點：

1. 1 個節點可以存儲超過 2 個元素、可以擁有超過 2 個子節點
2. 擁有二叉搜尋樹的一些性質
3. 平衡，每個節點的所有子樹高度一緻
4. 矮，查找比較次數少

1.2 n階B樹的性質

• 假設一個節點存儲元素的個數為x
  • 根節點： 1<= x <= n-1
  • 非根節點：ceiling(n/2) -1 <=x <=n-1
• 如果有子節點，子節點數目 y= x+1
  • 根節點的子節點數 2<=y<=n
  • 非根節點子節點數 ceiling(n/2) <=y <=n

有個結論：eg : n=4 2<=y<=4 是以稱4階B樹為 (2,4)樹、 2-3-4樹

1.3 B樹的搜尋

• 類似與BST

  

1. 先在節點内部從小到大開始搜尋元素
2. 如果命中，搜尋結束
3. 如果未命中，再去對應的子節點中搜尋元素，重複步驟 1

1.4 添加元素到B樹

• 以添加76為例

添加過程中，當節點的元素個數 等于n（階數），會産生

上溢

的現象

• 上溢過程中，可能導緻父節點的個數也等于n，那麼也會一直上溢，極端情況一直溢到根節點

1.5 B樹删除元素

• 删除的元素在葉子節點，則直接删除就可以
• 删除的元素在非葉子節點（複雜）

1. 先找到這個節點的前驅或素，覆寫所需删除元素的值

• 前驅和後繼元素必定在葉子節點中

1. 再把所選的前驅或後繼元素删除

以删除 元素60為例

(1) 找到前驅元素55 或 後繼元素 70
(2) 55或 70覆寫掉 60
(3) 删除葉子節點中 元素55 或 元素 70
(4) 根據B樹的性質來，調整B樹
           

• 删除元素後，可能會出現

  下溢

  ，（不滿足 ceiling(n/2)-1<=x <=n-1) ,這裡以5階B樹為例

删除元素 22

【22 24】為葉子節點，直接删除，變為【24】不滿足 2<=x <=4

如何解決下溢問題

首先，我們應該清楚 下溢的節點 元素的個數必然等于 ceiling(n/2)-2

• 如果下溢節點臨近的兄弟節點，有至少ceiling(n/2)個元素，可以向其借一個元素
  • 将父節點的元素 b（最大的元素）插入到下溢節點的0位置。
  • 用兄弟節點的元素a（最大元素）替代父節點的元素b

• 如果下溢節點臨近的兄弟節點，隻有 ceiling(n/2) − 1 個元素
  • 将父節點的元素 b 挪下來跟左右子節點進行合并
  • 合并後的節點元素個數等于ceiling(n/2) + ceiling(n/2) − 2，不超過 m − 1
  • 這個操作可能會導緻父節點下溢，依然按照上述方法解決，下溢現象可能會一直往上傳播

删除22，滿足第二種情況

關于紅黑樹和B樹

先學習4階B樹（2-3-4樹），将能更好地學習了解紅黑樹

紅黑樹（RBTree）

紅黑樹也是一種自平衡的BST，也成為平衡二叉B樹

紅黑樹必須滿足一下5種性質：

1. 節點是RED或BLACK
2. 根節點是BLACK
3. 葉子節點（外部節點，空節點）都是BLACK
4. RED節點的子節點都是BLACK
   • RED節點的parent都是BLACK
   • 從根節點到葉子節點的所有路徑上不能有兩個連續的RED節點
5. 從任一節點，到葉子節點的所有路徑都包含相同數目的BLACK節點

滿足了以上5種條件，就能保證平衡

2.1紅黑樹和 4階B樹的等價交換

• 紅黑樹 和 4階B樹 具有等價性
• BLACK節點 與它 的RED 節點 融合在一起，形成 1 個B樹節點
• 紅黑樹的黑色節點個數 等于 對應 B樹的節點的數目

2.2關于樹節點的幾個term（術語）

• 父節點/子節點
• 兄弟節點
• 叔父節點
• 祖父節點

2.3添加節點

• B樹添加節點，新元素必定添加到葉子節點中，此外4階B樹的節點個數要求在 【1，3】之間

• 建議新添加的節點預設為RED，能盡快滿足 紅黑樹的性質，除了性質4 (不能有兩個連續的RED節點)
  • 如果添加的是根節點，則染成BLACK

2.3.1添加的所有情況

• 滿足（性質4）：即父節點為BLACK（非空）

• 不滿足（性質4）：即父節點為RED

接下來修複性質4 -LL（右旋）\RR（左旋）

• 判定條件：叔父節點 為黑色空節點

1. 父節點 染成 BLACK， 祖父節點染成 RED
2. 祖父節點進行 單旋 操作

以添加52、60為例子

接下來修複性質4 -LR\RL

• 判定條件：叔父節點為黑色空節點

1. 自己染成 BLACK, 父節點 染成RED
2. 進行雙旋轉

LR: 父節點先右旋 祖父節點再左旋

RL：父節點先左旋 祖父節點再右旋

修複性質4 - 上溢-LL/RR

• 判定條件：叔父節點是 RED

1. 叔父節點 和 父節點 染成 BLACK
2. 祖父節點向上合并（染成RED）

祖父節點向上合并時，可能會出現上溢情況，

• 如果一直上溢到根節點，則直接染成黑色

修複性質4- 上溢-LR/RL

• 判定條件；叔父節點 為 RED

1. 父節點、祖父節點 染成 BLACK
2. 祖父節點 向上合并（染成黑色）

2.4删除節點

B樹中，最後真正被删除的元素都在葉子節點中

2.4.1 删除-RED節點

• 直接删除，不做任何調整

2.4.2 删除-BLACK節點

3種情況

1. 擁有2個RED子節點的BLACK節點
   • 不能直接删除，（找它的子節點代替删除）
2. 擁有1個RED子節點的BLACK節點
3. 為葉子節點

删除-擁有1個RED子節點的BLACK節點

判定條件：用以替代的子節點是RED節點

• 則将替代的子節點 染成 BLACK 即可保持紅黑樹性質

删除-BLACK為葉子節,兄弟節點為BLACK

• 條件1：如果兄弟節點 至少有一個 RED子節點 （如上圖删除 88）
  • 進行旋轉操作
  • 旋轉後的中心點 繼承 父節點的顔色
  • 旋轉後左右節點染色為BLACK
• 條件2；如果兄弟節點 沒有RED子節點
  • 将兄弟節點染成RED、 父節點染成BLACK(如下圖 删除88)

删除-BLACK為葉子節,兄弟節點為RED

• 将兄弟節點染成BLACK，父節點染成RED，進行旋轉
• 然後按照兄弟節點為BLACK的操作

紅黑樹的平衡

那5條性質僅能保證 紅黑樹 等價于 4階B樹

• 相比AVL樹，紅黑樹的平衡标準比較寬松：沒有一條路徑會大于其他路徑的2倍
  • AVL樹：每個左右子樹的高度差不超過1
• 紅黑樹的最大高度為 2*log2(n+1),依然為O(logn) 級别
• 搜尋的次數遠遠大于插入和删除，選擇AVL樹；搜尋、插入、删除次數幾乎差不多，選擇紅黑樹
• 相對于AVL樹來說，紅黑樹犧牲了部分平衡性以換取插入/删除操作時少量的旋轉操作，整體來說性能要優于AVL樹

紅黑樹的平衡标準比較寬松：沒有一條路徑會大于其他路徑的2倍

• AVL樹：每個左右子樹的高度差不超過1
• 紅黑樹的最大高度為 2*log2(n+1),依然為O(logn) 級别
• 搜尋的次數遠遠大于插入和删除，選擇AVL樹；搜尋、插入、删除次數幾乎差不多，選擇紅黑樹
• 相對于AVL樹來說，紅黑樹犧牲了部分平衡性以換取插入/删除操作時少量的旋轉操作，整體來說性能要優于AVL樹

紅黑樹的時間複雜度

搜尋：O(logn)

添加：O(logn)，O(1) 次的旋轉操作

删除：O(logn)，O(1) 次的旋轉操作

AVL樹的時間複雜度

搜尋、添加、删除都是O(logn) 複雜度，其中添加僅需O(1) 次旋轉調整、删除最多需要O(logn) 次旋轉調整