紅黑樹(shù)的概述：

紅黑樹(shù)本質(zhì)上是一種二叉查找樹(shù)橙喘，但它在二叉查找樹(shù)的基礎(chǔ)上額外添加了一個(gè)標(biāo)記（顏色）时鸵，同時(shí)具有一定的規(guī)則。這些規(guī)則使紅黑樹(shù)保證了一種平衡厅瞎，插入饰潜、刪除初坠、查找的最壞時(shí)間復(fù)雜度都為 O(logn)。

紅黑樹(shù)的性質(zhì)：

1囊拜、每個(gè)節(jié)點(diǎn)要么是紅色某筐，要么是黑色比搭；
2冠跷、根節(jié)點(diǎn)永遠(yuǎn)是黑色的；
3身诺、所有的葉節(jié)點(diǎn)都是是黑色的（注意這里說(shuō)葉子節(jié)點(diǎn)其實(shí)是上圖中的 NIL 節(jié)點(diǎn)）蜜托；
4、每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)一定都是黑色霉赡；
5橄务、從任一節(jié)點(diǎn)到其子樹(shù)中每個(gè)葉子節(jié)點(diǎn)的路徑都包含相同數(shù)量的黑色節(jié)點(diǎn)。

紅黑樹(shù)的旋轉(zhuǎn)

左旋：將一個(gè)向右傾斜的紅色鏈接旋轉(zhuǎn)為向左鏈接穴亏。對(duì)比操作前后蜂挪，可以看出，該操作實(shí)際上是將紅線鏈接的兩個(gè)節(jié)點(diǎn)中的一個(gè)較大的節(jié)點(diǎn)移動(dòng)到根節(jié)點(diǎn)上嗓化。

image

image

紅黑樹(shù)的插入與調(diào)整

因?yàn)橐獫M足紅黑樹(shù)的這五條性質(zhì)严肪，如果我們插入的是黑色節(jié)點(diǎn)，那就違反了性質(zhì)五谦屑，需要進(jìn)行大規(guī)模調(diào)整驳糯；如果我們插入的是紅色節(jié)點(diǎn)，那就只有在要插入節(jié)點(diǎn)的父節(jié)點(diǎn)也是紅色的時(shí)候違反性質(zhì)四或者當(dāng)插入的節(jié)點(diǎn)是根節(jié)點(diǎn)時(shí)氢橙，違反性質(zhì)二酝枢，所以，我們把要插入的節(jié)點(diǎn)的顏色變成紅色悍手。

不需要調(diào)整的情況：
1帘睦、當(dāng)插入的節(jié)點(diǎn)是根節(jié)點(diǎn)時(shí)，直接涂黑即可谓苟；
2官脓、當(dāng)要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)是黑色的時(shí)候，這個(gè)時(shí)候插入一個(gè)紅色的節(jié)點(diǎn)并沒(méi)有對(duì)這五個(gè)性質(zhì)產(chǎn)生破壞涝焙。所以直接插入不用在進(jìn)行調(diào)整操作卑笨。

需要調(diào)整的情況：即插入節(jié)點(diǎn)的父結(jié)點(diǎn)也是紅色。
因?yàn)樽笥覍?duì)稱的緣故仑撞，在此只討論父結(jié)點(diǎn)位于祖父節(jié)點(diǎn)的左支的情況（N 為插入節(jié)點(diǎn)）：

1赤兴、叔叔節(jié)點(diǎn)是紅色
這時(shí)候只進(jìn)行換色操作：將父結(jié)點(diǎn)和叔叔節(jié)點(diǎn)涂成黑色妖滔，祖父節(jié)點(diǎn)涂成紅色。

image

2桶良、叔叔節(jié)點(diǎn)是黑色座舍，插入節(jié)點(diǎn)位于父節(jié)點(diǎn)的右支
這時(shí)候需要將父結(jié)點(diǎn)當(dāng)成新的插入節(jié)點(diǎn)，并以他為支點(diǎn)進(jìn)行左旋操作陨帆，進(jìn)入情況3 曲秉。

image

image

紅黑樹(shù)的刪除與調(diào)整

如果被刪除結(jié)點(diǎn)有孩子亥鸠，則需要選一個(gè)合適的孩子節(jié)點(diǎn)作為新的根節(jié)點(diǎn)，稱為當(dāng)前節(jié)點(diǎn)识啦。
1负蚊、只有左孩子或只有右孩子，則讓該孩子作為當(dāng)前節(jié)點(diǎn)替代被刪除結(jié)點(diǎn)颓哮；
2家妆、左右孩子均存在，則用被刪除結(jié)點(diǎn)的中序后繼結(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)替代被刪除結(jié)點(diǎn)题翻。

注意：替代只是值的互換揩徊，顏色不變。
即：當(dāng)前節(jié)點(diǎn)是黑色嵌赠，被刪除結(jié)點(diǎn)是紅色塑荒。替換后，當(dāng)前節(jié)點(diǎn)位于被刪除結(jié)點(diǎn)的位置姜挺，是紅色齿税；被刪除結(jié)點(diǎn)位于當(dāng)前節(jié)點(diǎn)原來(lái)的位置，是黑色炊豪。

不需要調(diào)整的情況：
1凌箕、被刪除結(jié)點(diǎn)的是紅色的；
2词渤、被刪除結(jié)點(diǎn)只有一個(gè)孩子牵舱，用孩子的值替換被刪除節(jié)點(diǎn)，刪除孩子結(jié)點(diǎn)缺虐。

需要調(diào)整的情況：（被刪除節(jié)點(diǎn)為黑色）
因?yàn)樽笥覍?duì)稱的緣故芜壁，在此只討論父結(jié)點(diǎn)位于祖父節(jié)點(diǎn)的左支的情況：
1、兄弟節(jié)點(diǎn)為紅色
這時(shí)候需要互換父結(jié)點(diǎn)和兄弟節(jié)點(diǎn)的顏色，并進(jìn)行左旋操作慧妄。

image

image

image

image

紅黑樹(shù)的查找

與二叉排序樹(shù)的查找一樣：從根節(jié)點(diǎn)出發(fā)翘瓮，待找值較大時(shí)往右子樹(shù)方向查找，待找值較小時(shí)往左子樹(shù)方向查找裤翩，直到找到匹配的結(jié)點(diǎn)资盅。若找不到則查找失敗。

紅黑樹(shù)的應(yīng)用

Epoll 實(shí)現(xiàn)踊赠、Java集合中的 TreeSet 和 TreeMap呵扛、C++ STL 中的 set、map筐带，以及 Linux 虛擬內(nèi)存的管理今穿，都是通過(guò)紅黑樹(shù)去實(shí)現(xiàn)的。
在平時(shí)也可以應(yīng)用于各種管理系統(tǒng)的查找算法中伦籍，借此提高效率蓝晒。

在線生成紅黑樹(shù)

看完本教程，如果你還不太能清楚的寫(xiě)出紅黑樹(shù)的構(gòu)造過(guò)程帖鸦，那么芝薇，這一個(gè)網(wǎng)站將能很好地幫助到你。它不僅支持手動(dòng)輸入結(jié)點(diǎn)值作儿，也能隨機(jī)生成結(jié)點(diǎn)洛二，更重要的是，該網(wǎng)站把每一次插入、刪除的調(diào)整步驟都展現(xiàn)了出來(lái)灭红。趕緊試試吧侣滩！
在線生成紅黑樹(shù)（含變形步驟）

更多內(nèi)容請(qǐng)移步微信公眾號(hào) “ 暗星涌動(dòng) ”