一与倡、初識紅黑樹
1衰琐、紅黑樹的英文是什么焙矛？紅黑樹和二叉搜索樹有什么關(guān)系？
- 紅黑樹（Red Black Tree）：也是一種自平衡的二叉搜索樹
- 以前也叫做平衡二叉 B 樹（Symmetric Binary B-Tree）
image.png
2织堂、紅黑樹必須滿足以下 5 條性質(zhì)？
- ①節(jié)點(diǎn)都是 Red 或者 Black
- ②根節(jié)點(diǎn)是 Black
- ③葉子節(jié)點(diǎn)（外部節(jié)點(diǎn)奶陈、空節(jié)點(diǎn)）都是 Black
- ④Red 節(jié)點(diǎn)的子節(jié)點(diǎn)都是 Black（推導(dǎo)一：Red 節(jié)點(diǎn)的 parent 都是 Black易阳；推導(dǎo)二：從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑不能有 2 個連續(xù)的 Red 節(jié)點(diǎn)）
- ⑤從任一節(jié)點(diǎn)到葉子節(jié)點(diǎn)的所有路徑都包含相同數(shù)目的 Black 節(jié)點(diǎn)
image.png
3、紅黑樹與哪階 B 樹等價吃粒？
- 紅黑樹 和 4階(2-3-4)B樹具有等價性
image.png
image.png
二潦俺、紅黑圖添加
1、紅黑樹添加的所有情況（總共有 12 種情況）徐勃？
- 往紅黑樹添加新節(jié)點(diǎn)黑竞，都是往葉子節(jié)點(diǎn)上添加，并成為新的葉子節(jié)點(diǎn)疏旨。
image.png
2很魂、將添加節(jié)點(diǎn)的 12 種情況歸類之一：parent 為 Black（有四種情況）
- 直接也滿足 4階B樹 的性質(zhì)
- 因此不用做任何處理
3、將添加節(jié)點(diǎn)的 12 種情況歸類之二：parent 為 Red && uncle 不是 Red && LL/RR（有兩種情況）
- parent 染成 Black檐涝，grand 染成 Red
- grand 進(jìn)行單旋操作
image.png
4遏匆、將添加節(jié)點(diǎn)的 12 種情況歸類之三：parent 為 Red && uncle 不是 Red && LR/RL (有兩種情況)
- 把自己染成 Black，grand 染成 Red
- 進(jìn)行下面之一的雙旋操作
- LR：parent 左旋轉(zhuǎn)谁榜，grand 右旋轉(zhuǎn)
- RL：parent 右旋轉(zhuǎn)幅聘，grand 左旋轉(zhuǎn)
image.png
5、將添加節(jié)點(diǎn)的 12 種情況歸類之四：parent 為 Red && uncle 是 Red (有四種情況)
- parent窃植、uncle 染成 Black
- grand 向上合并（染成 Red帝蒿，當(dāng)做是新添加的節(jié)點(diǎn)進(jìn)行處理）
- grand 向上合并時，可能繼續(xù)發(fā)生上溢（若上溢持續(xù)到根節(jié)點(diǎn)巷怜，只需將根節(jié)點(diǎn)染成 Black）
image.png
image.png
image.png
二葛超、紅黑樹的補(bǔ)充
1、為什么紅黑樹的 5 條性質(zhì)就能讓紅黑樹也稱為平衡二叉搜索樹延塑？
- 首先不要拿 AVL 樹的平衡去衡量紅黑樹的平衡
- 紅黑樹的平衡其實(shí)就是 B 樹的平衡
- 相比 AVL 樹绣张，紅黑樹的平衡標(biāo)準(zhǔn)比較寬松：沒有一條路徑會大于其他路徑的 2 倍
2、AVL樹 和 紅黑樹之間如何選擇关带？（最重要侥涵，一定要切記）
image.png
image.png
三、紅黑樹刪除節(jié)點(diǎn)
1、紅黑樹刪除的奧義是什么芜飘？
- 在 B 樹中务豺，最后真正被刪除的元素都在葉子節(jié)點(diǎn)中
- 紅黑樹等價于四階(2-3-4)B樹，并且紅黑樹是二叉搜索樹的子集
2嗦明、紅黑樹刪除太復(fù)雜冲呢，后面再看吧。
image.png
image.png
image.png
image.png
image.png
