1选脊、什么是紅黑樹(shù)鸣个？
??????紅黑樹(shù)是一個(gè)要求不那么嚴(yán)格的平衡二叉樹(shù)搜索樹(shù)（平衡二叉搜索樹(shù)/AVL樹(shù)=平衡二叉樹(shù)+二叉搜索樹(shù)）
【平衡二叉樹(shù)要求左右子樹(shù)高度差值<=1凹耙，紅黑樹(shù)放寬了這個(gè)要求嗦篱，只要求任意路徑的長(zhǎng)度只差不會(huì)超過(guò)2倍即可。更準(zhǔn)確的說(shuō)是任意路徑上的的黑色節(jié)點(diǎn)數(shù)相同即可】
2纹腌、紅黑樹(shù)有什么用？
紅黑樹(shù)可用于數(shù)據(jù)查找滞磺，因?yàn)槠洹跋鄬?duì)”平衡升薯，所以其查找效率略低于平衡二叉搜索樹(shù)，但是也非常高效击困。
3涎劈、平衡二叉搜索樹(shù)的查找效率更高，為什么還要紅黑樹(shù)阅茶？
??????平衡二叉樹(shù)的要求過(guò)于嚴(yán)格（左右子樹(shù)高度差值<=1）蛛枚，導(dǎo)致幾乎每一次插入/刪除節(jié)點(diǎn)都會(huì)破壞平衡二叉樹(shù)的結(jié)構(gòu)，需要將其重新調(diào)整為平衡二叉樹(shù)脸哀。
??????顯然，如果在那種插入、刪除很頻繁的場(chǎng)景中炫掐，平衡樹(shù)需要頻繁著進(jìn)行調(diào)整仓蛆，這會(huì)使平衡樹(shù)的性能大打折扣。而紅黑樹(shù)因?yàn)椴皇菄?yán)格的平衡蝌诡，所以可以避免這個(gè)問(wèn)題溉贿，同時(shí)紅黑樹(shù)又是一個(gè)“相對(duì)”平衡的二叉搜索樹(shù)，所以其查找性能也很好浦旱。
3宇色、紅黑樹(shù)的特點(diǎn)/性質(zhì)（最好背下來(lái)）
1、每個(gè)節(jié)點(diǎn)都有顏色（紅或黑）
2、根節(jié)點(diǎn)是黑色的
3宣蠕、葉節(jié)點(diǎn)時(shí)黑色的（注意：葉節(jié)點(diǎn)是空節(jié)點(diǎn)例隆，有值的節(jié)點(diǎn)都不是葉結(jié)點(diǎn)）
4、沒(méi)有兩個(gè)相鄰的紅色節(jié)點(diǎn)（或者說(shuō)紅色節(jié)點(diǎn)的子節(jié)點(diǎn)一定是黑色節(jié)點(diǎn)）
5植影、從根節(jié)點(diǎn)到葉結(jié)點(diǎn)的每條路徑包含的黑色節(jié)點(diǎn)相同（又叫：黑節(jié)點(diǎn)平衡）
4裳擎、從紅黑樹(shù)查找數(shù)據(jù)
與二叉搜索樹(shù)查找數(shù)據(jù)的過(guò)程一致
5、向紅黑樹(shù)中插入數(shù)據(jù)（插入的節(jié)點(diǎn)統(tǒng)一標(biāo)記為紅色）
為什么標(biāo)記位紅色思币？
答：每條路徑包含的黑色節(jié)點(diǎn)已經(jīng)相同了鹿响，將新插入的節(jié)點(diǎn)標(biāo)記位紅色，那么插入后每條路徑包含的黑色節(jié)點(diǎn)數(shù)沒(méi)變谷饿，所以依然相同
（若插入數(shù)據(jù)后破壞了紅黑樹(shù)的性質(zhì)惶我，則需要對(duì)紅黑樹(shù)進(jìn)行“再平衡”，使其滿(mǎn)足紅黑樹(shù)的性質(zhì)博投。并且新插入的節(jié)點(diǎn)最多只會(huì)破壞5條性質(zhì)中的1條）
插入數(shù)據(jù)分為了3種情況
1绸贡、插入的節(jié)點(diǎn)，其沒(méi)有父節(jié)點(diǎn)
2毅哗、插入的節(jié)點(diǎn)听怕，其父節(jié)點(diǎn)是黑色節(jié)點(diǎn)
3、插入的節(jié)點(diǎn)虑绵，其父節(jié)點(diǎn)是紅色節(jié)點(diǎn)
第一種情況：插入的節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)尿瞭，說(shuō)明插入的節(jié)點(diǎn)是根節(jié)點(diǎn)，此時(shí)直接將節(jié)點(diǎn)的顏色改為黑色即可
第二種情況：插入的節(jié)點(diǎn)翅睛，其父節(jié)點(diǎn)是黑色節(jié)點(diǎn)声搁，此時(shí)不需要采取措施。新插入的節(jié)點(diǎn)并沒(méi)有破壞紅黑樹(shù)的性質(zhì)
第三種情況：插入的節(jié)點(diǎn)捕发，其父節(jié)點(diǎn)是紅色節(jié)點(diǎn)疏旨。如圖
可以看到21和22同為紅色，破壞了“沒(méi)有兩個(gè)相鄰的紅色節(jié)點(diǎn)”性質(zhì)扎酷，需要進(jìn)行再平衡操作檐涝。
如何再平衡？（最好背下來(lái)）
分為以下情況（共同前提：插入節(jié)點(diǎn)的父節(jié)點(diǎn)是紅色）：
1法挨、插入節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)（即插入節(jié)點(diǎn)的叔叔節(jié)點(diǎn)骤铃，就是上圖中的27節(jié)點(diǎn)）是紅色
2、插入節(jié)點(diǎn)的父節(jié)點(diǎn)的兄弟節(jié)點(diǎn)是黑色
為什么要看其叔叔節(jié)點(diǎn)坷剧，而不是其父親節(jié)點(diǎn)?
答：這里其實(shí)跳步了惰爬，我們第一步還是調(diào)整其父親節(jié)點(diǎn)，但是其父親節(jié)點(diǎn)只有一種調(diào)整方法：由紅色變?yōu)楹谏蛊蟆５诙皆诳雌涫迨骞?jié)點(diǎn)的顏色撕瞧。所以這里直接跳過(guò)其父親節(jié)點(diǎn)的調(diào)整陵叽，看其叔叔節(jié)點(diǎn)的顏色
第一步：將其父節(jié)點(diǎn)顏色變?yōu)楹谏?br> 因?yàn)槠涓腹?jié)點(diǎn)顏色變成了黑色，所以包含其父節(jié)點(diǎn)的這條路徑多了一個(gè)黑色節(jié)點(diǎn)丛版。破壞了“從根節(jié)點(diǎn)到葉結(jié)點(diǎn)的每條路徑包含的黑色節(jié)點(diǎn)相同”性質(zhì)巩掺，如上面的13,17,25，22（變成了黑色）,21路徑
第二步：看其叔叔的顏色：
第一種情況：其叔叔節(jié)點(diǎn)為紅色（其父節(jié)點(diǎn)為紅色的前提下）
步驟：
1页畦、把叔叔節(jié)點(diǎn)變成黑色
2胖替、把其祖父節(jié)點(diǎn)（父節(jié)點(diǎn)的父節(jié)點(diǎn)）變成紅色。若其祖父節(jié)點(diǎn)為根節(jié)點(diǎn)豫缨，則不變色
3独令、把祖父節(jié)點(diǎn)當(dāng)做新插入的節(jié)點(diǎn)，重復(fù)1,2,3步驟直到其祖父節(jié)點(diǎn)為根節(jié)點(diǎn)
第二種情況：其叔叔節(jié)點(diǎn)為黑色（其父節(jié)點(diǎn)為紅色的前提下）
這種情況下又分為兩種情況：
1好芭、新插入的子節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)
2燃箭、新插入的子節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)
第一種情況：新插入的子節(jié)點(diǎn)是父節(jié)點(diǎn)的左子節(jié)點(diǎn)（其叔叔節(jié)點(diǎn)為黑色，并且其父節(jié)點(diǎn)為紅色的前提下）
步驟：（先變色舍败，在右旋）
1招狸、將其父節(jié)點(diǎn)變?yōu)楹谏?br>
2、將其祖父節(jié)點(diǎn)變?yōu)榧t色（其父節(jié)點(diǎn)是紅色邻薯，則其祖父節(jié)點(diǎn)必為黑色）
3裙戏、以其父節(jié)點(diǎn)為支點(diǎn)，進(jìn)行右旋操作（如何右旋厕诡？百度上有很形象的動(dòng)畫(huà)演示）
第二種情況：新插入的子節(jié)點(diǎn)是父節(jié)點(diǎn)的右子節(jié)點(diǎn)（其叔叔節(jié)點(diǎn)為黑色累榜，并且其父節(jié)點(diǎn)為紅色的前提下）
步驟：（先左旋將其變?yōu)榍闆r一，在按情況一的操作來(lái)進(jìn)行）
以新插入的節(jié)點(diǎn)為支點(diǎn)木人，進(jìn)行左旋操作，變?yōu)榍闆r一冀偶，此時(shí)將插入節(jié)點(diǎn)的父節(jié)點(diǎn)（上圖的P節(jié)點(diǎn)）當(dāng)做新插入的節(jié)點(diǎn)來(lái)進(jìn)行情況一步驟下的：變色醒第，右旋操作
6、紅黑樹(shù)的刪除操作：
下面我們開(kāi)始討論刪除操作（下面的葉子節(jié)點(diǎn)都是指非NULL的葉子節(jié)點(diǎn)）：
A. 刪除的是葉子節(jié)點(diǎn)且該葉子節(jié)點(diǎn)是紅色的 ---> 無(wú)需修復(fù)进鸠，因?yàn)樗粫?huì)破壞紅黑樹(shù)的5個(gè)特性
B. 刪除的是葉子節(jié)點(diǎn)且該葉子節(jié)點(diǎn)是黑色的 ---> 很明顯會(huì)破壞特性5稠曼，需要修復(fù)。
C. 刪除的節(jié)點(diǎn)（為了便于敘述我們將其稱(chēng)為P）下面有一個(gè)子節(jié)點(diǎn) S客年，對(duì)于這種情況我們通過(guò) 將P和S的值交換的方式霞幅，巧妙的將刪除P變?yōu)閯h除S，S是葉子節(jié)點(diǎn)量瓜，這樣C這種情況就會(huì)轉(zhuǎn) 換為A, B這兩種情況：
C1: P為黑色司恳，S為紅色 ---> 對(duì)應(yīng) A 這種情況
C2: P為黑色或紅色，S為黑色 --- > 對(duì)應(yīng) B 這種情況
**D. **刪除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)绍傲，對(duì)于這種情況扔傅，我們通過(guò)將P和它的后繼節(jié)點(diǎn)N的值交換的方 式耍共，將刪除節(jié)點(diǎn)P轉(zhuǎn)換為刪除后繼節(jié)點(diǎn)N，而后繼節(jié)點(diǎn)只可能是以下兩種情況：
D1: N是葉子節(jié)點(diǎn) --- > 對(duì)應(yīng)情況 A 或 B
D2: N有一個(gè)子節(jié)點(diǎn) ---- > 對(duì)應(yīng)情況 C
所以通過(guò)上面的分析我們發(fā)現(xiàn)猎塞，紅黑樹(shù)節(jié)點(diǎn)刪除后的修復(fù)操作都可以轉(zhuǎn)換為 A 或 B這兩種情況试读，而A不需要修復(fù)，所以我們只需要研究B這種情況如何修復(fù)就行了荠耽。
下面我們討論如何修復(fù)B中情況：(若沒(méi)有兄弟節(jié)點(diǎn)钩骇，則其兄弟節(jié)點(diǎn)是null節(jié)點(diǎn)，根據(jù)紅黑樹(shù)的性質(zhì)铝量，null節(jié)點(diǎn)為黑色)
