目錄

• 序言
• 紅黑樹必須滿足以下5條性質(zhì)
• 添加
• 刪除

一 序言

紅黑樹也是一種自平衡的二叉搜索樹吃谣，以前也叫做平衡二叉B樹(Symmetric Binary B-tree)

二 紅黑樹必須滿足以下5條性質(zhì)

1.節(jié)點是RED或者是BLACK

2. 根節(jié)點是BLACK
3. 葉子節(jié)點(外部節(jié)點冰肴，空節(jié)點)都是BLACK
4. RED節(jié)點的子節(jié)點都是BLACK
   4.1 RED節(jié)點的parent都是BLACK
   4.2 從根節(jié)點到葉子節(jié)點的所有路徑上不能有2個連續(xù)的RED節(jié)點
5. 從任一節(jié)點到葉子節(jié)點的所有路徑都包含相同數(shù)目的BLACK節(jié)點

image.png

2.1 請問下面這棵是紅黑樹嗎暑椰？

image.png

紅黑樹必須滿足以下5條性質(zhì)

1. 節(jié)點是RED或者BLACK
2. 根節(jié)點是BLACK
3. 葉子節(jié)點（外部節(jié)點美浦，空節(jié)點）都是BLACK
4. RED節(jié)點的子節(jié)點都是BLACK
   4.1 RED節(jié)點的子節(jié)點都是BLACK
   4.2 從根節(jié)點到葉子節(jié)點的所有路徑上不能有2個連續(xù)的RED節(jié)點
5. 從任一節(jié)點到葉子節(jié)點的所有路徑都包含相同數(shù)目的BLACK節(jié)點

2.2 紅黑樹的等價交換

• 紅黑樹和4階B樹（2-3-4樹）具有等價性
• BLACK 節(jié)點與它的 RED 子節(jié)點融合在一起失晴，形成1個B樹節(jié)點
• 紅黑樹的 BLACK 節(jié)點個數(shù) 與 4階B樹的節(jié)點總個數(shù) 相等
• 網(wǎng)上有些教程:用 2-3樹 與 紅黑樹 進行類比臭杰，這是極其不嚴(yán)謹(jǐn)?shù)模?-3樹 并不能完美匹配 紅黑樹 的所有情況
• 注意:因為PPT界面空間有限曹动，后面展示的紅黑樹都會省略NULL 節(jié)點

紅黑樹

image.png

等價交換后的4階B樹

image.png

2.3 幾個英文單詞

• parent:父節(jié)點
• sibling:兄弟節(jié)點
• uncle:叔父節(jié)點( parent 的兄弟節(jié)點)
• grand:祖父節(jié)點( parent 的父節(jié)點)

三 添加

已知

• B樹中，新元素必定是添加到葉子節(jié)點中
• 4階B樹所有節(jié)點的元素個數(shù) x 都符合 1 ≤ x ≤ 3
• 如果添加的是根節(jié)點饰恕，染成BLACK 即可

備注：建議新添加的節(jié)點默認為 RED挠羔，這樣能夠讓紅黑樹的性質(zhì)盡快滿足(性質(zhì) 1、2埋嵌、3破加、5 都滿足，性質(zhì) 4 不一定)

image.png

3.1 添加的所有情況

• 有 4 種情況滿足紅黑樹的性質(zhì) 4 :parent 為 BLACK

1.同樣也滿足 4階B樹 的性質(zhì)
2.因此不用做任何額外處理

image.png

• 有 8 種情況不滿足紅黑樹的性質(zhì) 4 :parent 為 RED( Double Red )

1. 其中前 4 種屬于B樹節(jié)點上溢的情況

image.png

3.2 修復(fù) - 修復(fù)性質(zhì)4 - LL\RR

判定條件:uncle 不是RED

1. parent 染成 BLACK雹嗦，grand 染成 RED
2. grand 進行單旋操作
   2.1 LL:右旋轉(zhuǎn)
   2.2 RR:左旋轉(zhuǎn)

image.png

3.3 添加 - 修復(fù)性質(zhì)4 - LR\RL

判定條件:uncle 不是RED

1. 自己染成BLACK范舀，grand染成RED
2. 進行雙旋操作
   2.1 LR:parent 左旋轉(zhuǎn)， grand 右旋轉(zhuǎn)
   2.2 RL:parent 右旋轉(zhuǎn)了罪， grand 左旋轉(zhuǎn)

image.png

3.4 添加-修復(fù)性質(zhì)4-上溢-LL

判定條件:uncle 是RED

1. parent锭环、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，當(dāng)做是新添加的節(jié)點進行處理
   2.2 grand 向上合并時泊藕，可能繼續(xù)發(fā)生上溢
   2.3 若上溢持續(xù)到根節(jié)點辅辩，只需將根節(jié)點染成 BLACK

上溢-LL.png

3.5 添加-修復(fù)性質(zhì)4-上溢-RR

判定條件:uncle 是RED

1. parent、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED吱七，當(dāng)做是新添加的節(jié)點進行處理

上溢-RR.png

3.6 添加-修復(fù)性質(zhì)4-上溢-LR

判定條件:uncle 是RED

1. parent汽久、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED，當(dāng)做是新添加的節(jié)點進行處理

上溢-LR.png

3.7 添加-修復(fù)性質(zhì)4-上溢-RL

判定條件:uncle 是RED

1. parent踊餐、uncle 染成 BLACK
2. grand 向上合并
   2.1 染成 RED景醇，當(dāng)做是新添加的節(jié)點進行處理

上溢-RL.png

四 刪除

B樹中，最后真正被刪除的元素都在葉子節(jié)點中

刪除.png

4.1 刪除 – RED節(jié)點

• 直接刪除吝岭，不用作任何調(diào)整

刪除-RED節(jié)點.png

4.2 刪除-BLACK節(jié)點

有 3 種情況

1. 擁有 2 個 RED 子節(jié)點的 BLACK 節(jié)點
   1.1 不可能被直接刪除三痰，因為會找它的子節(jié)點替代刪除
   1.2 因此不用考慮這種情況

2. 擁有 1 個 RED 子節(jié)點的 BLACK 節(jié)點

3. BLACK 葉子節(jié)點

image.png

4.3 刪除 – 擁有1個RED子節(jié)點的BLACK節(jié)點

判定條件:用以替代的子節(jié)點是 RED

將替代的子節(jié)點染成BLACK 即可保持紅黑樹性質(zhì)

image.png

image.png

4.4 刪除 – BLACK葉子節(jié)點 – sibling為BLACK

1. BLACK 葉子節(jié)點被刪除后，會導(dǎo)致B樹節(jié)點下溢(比如刪除88)

2. 如果 sibling 至少有 1 個 RED 子節(jié)點
   2.1 進行旋轉(zhuǎn)操作
   2.2 旋轉(zhuǎn)之后的中心節(jié)點繼承 parent 的顏色
   2.3 旋轉(zhuǎn)之后的左右節(jié)點染為 BLACK

• 下圖是3種需要刪除的情況

image.png

• 下圖對應(yīng)著刪除節(jié)點88后窜管，旋轉(zhuǎn)之后的樣子

image.png

4.5 刪除 – BLACK葉子節(jié)點 – sibling為BLACK

判定條件:sibling 沒有 1 個 RED 子節(jié)點

• 將 sibling 染成 RED散劫、parent 染成 BLACK 即可修復(fù)紅黑樹性質(zhì)

如果 parent 是 BLACK

1. 會導(dǎo)致parent 也下溢
2. 這時只需要把 parent 當(dāng)做被刪除的節(jié)點處理即可

image.png

項目連接地址 - 12_RedBlackTree

本文參考 MJ老師的 戀上數(shù)據(jù)結(jié)構(gòu)與算法

《戀上數(shù)據(jù)結(jié)構(gòu)與算法一》筆記

本人技術(shù)水平有限，如有錯誤歡迎指正幕帆。
書寫整理不易获搏，您的打賞點贊是對我最大的支持和鼓勵。