0. 定義
R-B Tree俯画，全稱是Red-Black Tree，又稱為“紅黑樹(shù)”司草，它一種特殊的二叉查找樹(shù)艰垂。紅黑樹(shù)的每個(gè)節(jié)點(diǎn)上都有存儲(chǔ)位表示節(jié)點(diǎn)的顏色泡仗，可以是紅(Red)或黑(Black)。
紅黑樹(shù)的特性:
- 每個(gè)節(jié)點(diǎn)或者是黑色材泄，或者是紅色沮焕。
- 根節(jié)點(diǎn)是黑色。
- 每個(gè)葉子節(jié)點(diǎn)（NIL）是黑色拉宗。(注意：這里葉子節(jié)點(diǎn)峦树，是指為空(NIL或NULL)的葉子節(jié)點(diǎn)！)
- 如果一個(gè)節(jié)點(diǎn)是紅色的旦事，則它的子節(jié)點(diǎn)必須是黑色的魁巩。(沒(méi)有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
-
從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。
紅黑樹(shù)示例
1. 添加節(jié)點(diǎn)
注意：新添加的節(jié)點(diǎn)均為紅色
如果插入的是根節(jié)點(diǎn)姐浮，直接涂黑
如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色谷遂，不用調(diào)整
此時(shí)并未破壞原有的樹(shù)的特性。如果插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色
這時(shí)看叔叔節(jié)點(diǎn)
- 如果叔叔節(jié)點(diǎn)是紅色
將父節(jié)點(diǎn)和叔叔節(jié)點(diǎn)變?yōu)楹谏衾穑娓腹?jié)點(diǎn)變?yōu)榧t色肾扰，然后將祖父節(jié)點(diǎn)看做當(dāng)前節(jié)點(diǎn)繼續(xù)處理 - 如果叔叔節(jié)點(diǎn)是黑色
- 如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子蛋逾，則做LL旋轉(zhuǎn)集晚，互換父節(jié)點(diǎn)和祖父節(jié)點(diǎn)的顏色
- 如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的左孩子，當(dāng)前節(jié)點(diǎn)是其父節(jié)點(diǎn)的右孩子区匣，則做LR旋轉(zhuǎn)偷拔，第二次旋轉(zhuǎn)時(shí)互換祖父節(jié)點(diǎn)和新的父節(jié)點(diǎn)的顏色
- 如果父節(jié)點(diǎn)是祖父節(jié)點(diǎn)的右孩子，與上面兩種情況互為鏡像
2. 刪除節(jié)點(diǎn)
刪除節(jié)點(diǎn)和普通二叉查找樹(shù)刪除節(jié)點(diǎn)一樣亏钩，都是刪除其后繼節(jié)點(diǎn)莲绰。
以下
當(dāng)前節(jié)點(diǎn)均是指其后繼結(jié)點(diǎn)
如果當(dāng)前節(jié)點(diǎn)是紅色，直接刪除即可
如果當(dāng)前節(jié)點(diǎn)是黑色姑丑，且為根節(jié)點(diǎn)蛤签，直接刪除即可
如果當(dāng)前節(jié)點(diǎn)是黑色（由紅黑樹(shù)的性質(zhì)可以推斷，黑色節(jié)點(diǎn)必定有兄弟節(jié)點(diǎn)）
- 如果兄弟節(jié)點(diǎn)是紅色（則兄弟節(jié)點(diǎn)的孩子為黑色）
可以對(duì)父節(jié)點(diǎn)進(jìn)行左旋栅哀，交換父節(jié)點(diǎn)和兄弟節(jié)點(diǎn)的顏色顷啼，使當(dāng)前節(jié)點(diǎn)的兄弟節(jié)點(diǎn)變?yōu)楹谏^續(xù)進(jìn)行處理 - 如果兄弟節(jié)點(diǎn)是黑色昌屉，并且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左孩子
- 如果兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色
交換兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色钙蒙，把父節(jié)點(diǎn)當(dāng)做當(dāng)前節(jié)點(diǎn)，繼續(xù)處理 - 如果兄弟節(jié)點(diǎn)的右孩子為紅色
交換兄弟節(jié)點(diǎn)和父節(jié)點(diǎn)的顏色间驮，右孩子變黑躬厌，父節(jié)點(diǎn)左旋 - 如果兄弟節(jié)點(diǎn)的左孩子為紅色
交換兄弟節(jié)點(diǎn)和左子的顏色，兄弟節(jié)點(diǎn)右旋，此時(shí)變?yōu)橛易訛榧t色的情況
- 如果兄弟節(jié)點(diǎn)的兩個(gè)孩子都是黑色
- 如果兄弟節(jié)點(diǎn)是黑色扛施，并且當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的右孩子
與上面左孩子情況互為鏡像
3. 練習(xí)
跟著這篇文章操作一遍鸿捧，基本能全部掌握：數(shù)據(jù)結(jié)構(gòu)之紅黑樹(shù)插入與刪除全程演示
