---
# System prepended metadata

title: Red Black Tree Deletion | 紅黑樹刪除節點
tags: [資工筆記]

---

## 紅黑樹特性

1. root 為黑色節點
2. 所有 leaf 為黑色節點，值為 NIL
3. 若某節點為紅色則其 child 為黑色 (無兩個連續紅色節點)
4. 對任一節點，到 leaf 所經過的黑色節點數量一樣

為了符合以上特性，插入或刪除節點時需要作一些調整

## 刪除節點

按照 binary search tree 的方式處理節點 x (successor/predecessor y 的值移至 x，將 y 刪除)

### 示範圖說明

- 為樹的一部份，不是完整的樹喔~
- 灰色的點表示可以是紅的或黑的

### Case 0: x 和 y 原本的顏色為一黑一紅

- x 設為黑色

![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEilRc5c_mhPazUNRiID8EdXKFehdFNSV07xWzi5wrGW6pRnmVQ-q_zT0qNDtb9l8IhpuxolxnagMq8ccUXtv4iovjAIzJRu4Rzflay5J7s2nIzthVMEzfyhvIOJIZq6dWAqovbjKEtyf0I2DzV9qP_HoJQu3-lcqTPg82Hk50AZnfBvjTU/s1600/RBT_delete_case0.png)

### Case 1: x 的 sibling w 為紅色

- 以 x.p 為圓心，w 往上轉
- x.p 和 w 顏色互換
- 現在 x 有新的 sibling w (新的 w 是舊的 w 的小孩，必定為黑色) 繼續用 case2, 3, 4 處理

![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgqfsYAEA5ekNjWkusG3VT0o6Pq5SFQByaHibka-I2S3xTV53eZ4i8nnbfOhsLzkDkbGkCzDWZMrDg32nd8elawhLjiaa_PuOevlJ9nn3Ts9XMbE8lobIrt3sf6O79Zp_iSqCWmlp4bJbL3Meg9KWWIhPRMa5Pd5KxQPoJdVUedy5zNcC8/s1600/RBT_delete_case1.png)

### Case 2: x 的 sibling w 為黑色，w 的小孩皆為黑色

- w 設為紅色
- x.p 設為黑色
    - 如果 x.p 原本是紅色，x.p 設為黑色，處理結束
    - 如果 x.p 原本是黑色，x.p 視為新的 x，重新處理

![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhwkC9RK2MGc7v5Wsu4Kppt4ifU4y5ssmc9jJ-gsogcAHqJhCvqZqBEiab-ZHZ8BOiJNs0qRNURlUMhbs-GfT_VuFMi2DMfjVdSh941E2rBFTnyuOXFvv2u7lsY8Gau4NZAYksgmfPpyAyx4dRw23LrtVUCg-5KXyDhExy5bnwaYkwED2A/s1600/RBT_delete_case2.png)

### Case 3: x 的 sibling w 為黑色，w 的右小孩為黑色，左小孩為紅色

- 以 w 為圓心，左小孩往上轉
- w 和左小孩顏色互換
- 左小孩成為新的 w，繼續用 case 4 處理

![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgX-OjsLQvTqnRb2vkKuBaVhjugI8gctQrl_ZbvMXwHArQQ5vY9jiDGVm_fU5T0_nMO8-4rsr_ZEwNOtI2VJHrmIIAwUhQ3UcsItJDv-ay6xBMTmnzQvAeLIa_wQjaEe-jSXWgdoL83dvStiOv1hIEy8AGWoas-qGxbTVAInqjWAfFf_gk/s1600/RBT_delete_case3.png)

### Case 4: x 的 sibling w 為黑色，w 的右小孩為紅色

- 以 x.p 為圓心，w 往上轉
- w 設為 x.p 原本的顏色
- x.p 和右小孩設為黑色

![](https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEjMGLoDoIkkVFgDP2u_h2ksniIEq57gjB8eh62BbyX9dBqVj5Irz7Bo_tyXpLEUqrvt7dsDN3uNG5iUobR9MEqe5itxLe3s0hDi7DDGG1-Bl8dhhqrg_6pzIzTPxe4utbVstQWpqwIrIesfNgKt6ar3oWqVv2keiOCE9BtmGX0eUNdlWFA/s1600/RBT_delete_case4.png)

## 相關連結
[Red Black Tree Insertion | 紅黑樹新增節點](https://showsun63.blogspot.com/2025/01/RBT-insertion.html) 
[Red Black Tree Visualization | 紅黑樹模擬器](https://www.cs.usfca.edu/~galles/visualization/RedBlack.html)