[DSA] 紅黑樹 (Red-Black Tree) 介紹 - Part 2: Removal

    Data Structure and Algorithm   Data Structure and Algorithm   Tree  Comments

紅黑樹 (Red-Black Tree) 介紹 - Part 2: Removal

BST 重要概念: 我們希望 Removal 發生在 leaf node。

刪除節點有兩種: 刪除葉節點與刪除非葉節點。但我們希望 Removal 發生在 leaf node，因為從中間砍掉在組合回來是很麻煩的一件事。如下所示:

從上圖可知，我們想要刪除非葉節點，我們可以:

  • 將其左子樹中最大的點提上來補
  • 將其右子樹中最小的點提上來補
範例為 remove 16，然後 18 上去補 16 的位置。

於是我們可以將任何 remove node 改成 remove leaf node

且 Remove leaf 有三種情境:

  • Remove red node: easy
  • Remove black node

    • Black sibling and has red child: restructure

    • Black sibling and has black/null child: recolors

    • Red sibling: rotate 3-node

      找不到真兄弟，需要重新旋轉

Case 1: Remove Red node: easy

直接移除即可。

如下所示:

Case 2: Remove Black node: easy

有三種情形，如下。

Case 2-1. Black sibling and has red child

類似 2-3-4 Tree 中的 Transfer
> Transfer when borrowable

有黑色的兄弟跟紅色的姪子，需 Rotate and Recolor， 如下圖所示:

Case 2-2: Black sibling and has black child

類似 2-3-4 Tree 中的 Fuse
> Fuse and remove from upper level

有黑色的兄弟跟黑色的姪子或是沒有姪子(Null node)，直接 Recolor，如下圖所示:

  • 注意: 因為這邊操作是把爸把往下移跟兄弟變成新家，還需判斷:

    • 原本為紅色節點:

      改成黑色節點，結束。

      因為他在原本那層本來就是小弟，往下移不會有影響

    • 原本為黑色節點:

      則需在判斷 upper level 移掉這個點後
會有什麼影響，直到結束。

      因為他在原本那層是大哥，往下移則會少一層， 需要重新調整，如: 看有無兄弟可借等等的。

Case 2-3: Red sibling

此 Red sibling 為假兄弟，需 Rotate 3-node 後，再進行相關處理，看他是 Case 2-1: 有人可以借 或是 Case 2-2: 無人可借 的情形，如下所示:

轉完後發現:

  • 黑色的兄弟跟紅色的姪子，所以有人可借
  • 為 AVL RL 型

所以我們操作如下:

對照 2-3-4 Tree

Reference

Kaka LinSoftware Engineer

AIoT