1.4.3.3 RB Tree Delete

紅黑樹節點的刪除: 在前面二元樹的筆記, 你可以看得出來刪除節點是很麻煩的, 那紅黑樹是一定會更複雜的, 因為紅黑樹在做刪除動作的時候還需要保證刪除節點後的樹也是平衡的. 因此, 通常在實際的開發中, 多數情況下不用真的去做紅黑樹節點的刪除, 而是採用其他的手段, 譬如: 僅標示此節點被刪除, 而不是真的刪除, 這樣你的樹就不用動了, 故在業務邏輯處理的過程中, 判斷一下這個節點是不是被砍掉了, 若是的話就跳過即可. 這其實跟很多公司在實作刪除資料的時候, 不是真的去砍資料, 而是把該筆資料在DB裡面用一個"Deleted"之類的欄位為true來作為已經刪除的意思.

紅黑樹的刪除演算法:

1. 如果刪除節點是葉子節點 1. 如果刪除節點是紅色的, 那就直接砍了, 不做別的事, 因為紅色不會影響黑色高度. 2. 如果刪除節點是黑色的, 那就要建立一個空節點來頂替被刪除的節點, 然後按照後面會提到的調整步驟進行調整

2. 如果刪除節點有一個子節點, 那就把後來要頂替被刪除節點的那個節點變成等頂替節點, 如果刪除節點為黑色, 而且頂替節點也為黑色, 那麼把頂替節點作為當前節點, 然後按照後面的調整步驟進行調整

3. 若刪除節點有兩個子節點, 那麼, 找到其中序後繼節點, 把這兩個節點的資料進行交換, 不要複製顏色, 也不要改變其原有的父子等關係, 然後重新進行刪除的動作, 此處的刪除是指對交換資料後的中序後繼節點做刪除, 如原本刪除節點為node(id = m, value = i), 中序後繼節點為node(id = n, value = j), 則資料交換後變成node(id = m, value = j), node(id = n, value = i), 然後對node(id=n)進行刪除的動作. 由於其中序後繼節點只可能是葉子節點或著只有一個子節點, 這樣就會簡化成前面的兩種情形了.

刪除步驟中提到的調整演算法:

1. 若當前節點是紅色的, 則直接把當前節點變成黑色的即可

2. 若當前節點是黑色的, 且同時為根節點, 則什麼都不用做

3. 若當前節點是黑色且兄弟節點為紅色, 當前節點為父節點的左子節點, 則把兄弟節點變成父節點的顏色, 把父節點變成紅色, 然後於父節點上執行左旋, 再重新開始判斷

4. 若當前節點是黑色且兄弟節點為紅色, 當前節點為父節點的右子節點, 則把兄弟節點變成父節點的顏色, 把父節點變成紅色, 然後於父節點上執行右旋, 再重新開始判斷

5. 若當前節點是黑色且父節點和兄弟節點都是黑色, 兄弟節點的兩個子節點全為黑色, 則把兄弟節點變紅, 然後把父節點當成新的當前節點, 再重新開始判斷

6. 若當前節點是黑色且兄弟節點為黑色, 兄弟節點的兩個子節點全為黑色, 但是父節點是紅色, 則把兄弟節點變紅色, 父節點變黑色

7. 若當前節點是黑色且兄弟節點為黑色, 兄弟節點的左子節點為紅色, 右子節點為黑色, 且當前節點是父節點的左子節點, 則把兄弟節點變紅色, 兄弟左子節點變黑, 然後對兄弟節點執行右旋, 再重新開始判斷

8. 若當前節點是黑色且兄弟節點為黑色, 兄弟節點的左子節點為黑色, 右子節點為紅色, 且當前節點是父節點的右子節點, 則把兄弟節點變紅色, 兄弟右子節點變黑, 然後對兄弟節點執行右旋, 再重新開始判斷

9. 若當前節點是黑色且兄弟節點為黑色, 兄弟節點的右子節點為紅色, 左子節點顏色不拘, 且當前節點是父節點的左子節點, 則把兄弟節點變成當前節點父節點的顏色, 並把當前節點的父節點變黑, 兄弟節點的右子節點變黑, 然後以當前節點的父節點為支點執行左旋

10. 若當前節點是黑色且兄弟節點為黑色, 兄弟節點的左子節點為紅色, 左子節點顏色不拘, 且當前節點是父節點的右子節點, 則把兄弟節點變成當前節點父節點的顏色, 並把當前節點的父節點變黑, 兄弟節點的左子節點變黑, 然後以當前節點的父節點為支點執行右旋

寫到這邊我腦海中第一個浮現的是這個畫面:

紅黑樹的效率: 紅黑樹的搜尋、插入與刪除的時間複雜度都是O(logn). 基本上跟二元樹是一樣的, 但實際上由於紅黑樹在插入和刪除的時候, 因為需要保持平衡的關係, 所以會比二元樹慢一些. 另外, 紅黑樹需要額外的空間來記錄顏色的資訊

其它的平衡樹: AVL Tree(發明者為: Adelson-Velskii及Landis)是最早的一種平衡樹, 其要求節點左子樹和右子樹的高度相差不超過1. 當插入和刪除節點的時候, 都要進行平衡的動作, 也就是每次操作會掃描整棵樹兩次, 一次向下搜尋節點, 一次向上平衡整棵樹. AVL Tree的效能基本上不如紅黑樹, 也不常用, 了解一下就好.