普通的二叉搜索樹在最壞的情況下泽论，可能退化成一個鏈表翼悴。而又因為二叉搜索樹的所有操作的性能（添加鹦赎，刪除古话，查找等）陪踩，與二叉搜索樹的高度有關膊毁。在最壞的情況下婚温，二叉搜索樹的高度和元素個數(shù)相同，此時二叉搜索樹的效率降為了O(n)級別篱竭。
所以為了防止我們的二叉搜索樹退化成一個鏈表掺逼，就產(chǎn)生了平衡二叉樹吕喘。平衡二叉樹可以保證它的左右兩個子樹的高度差不會超過1氯质。平衡二叉樹有很多實現(xiàn)闻察，一個經(jīng)典實現(xiàn)就是紅黑樹辕漂。
紅黑樹
在紅黑樹中將樹中的節(jié)點劃分為兩種狀態(tài)钉嘹，分別用黑色和紅色來表示隧期。
紅黑樹為了保證自己能夠平衡子樹仆潮，所以制訂以下五個規(guī)則：
1性置、每個節(jié)點必須有顏色鹏浅，要么黑色隐砸，要么紅色季希，沒有別的顏色峰尝。
2武学、根節(jié)點必須是黑色
3火窒、所有的空節(jié)點(nil節(jié)點)都認為是黑色節(jié)點。
4曲掰、紅色的節(jié)點不能連續(xù)栏妖，即一個紅色的節(jié)點奖恰，它的父節(jié)點和子節(jié)點不能也是紅色的吊趾，
5、無論從哪一個節(jié)點起始瑟啃，到它每個葉子節(jié)點的路徑中论泛，黑色節(jié)點數(shù)量必須相同。
在對紅黑樹進行添加蛹屿、刪除等操作之后屁奏，必須使紅黑樹符合這5個規(guī)則错负。
那么問題來了坟瓢，在添加刪除操作之后，樹中節(jié)點的數(shù)量都變了犹撒，是怎么保證整個樹滿足上述這些規(guī)則呢折联？
這里涉及到3種操作，變色识颊、左旋和右旋诚镰。通過這個三種操作，在增刪節(jié)點之后調(diào)整樹的形狀結(jié)構，使它滿足上述5個規(guī)則怕享。這也是紅黑樹能保持平衡的原因执赡。
變色操作我們在下文的添加、刪除節(jié)點的實際操作中函筋，再進行在描述沙合。
先來說一下左右旋。
左旋
左旋是指以某節(jié)點為支點跌帐，進行逆時針旋轉(zhuǎn)首懈。如下圖，是以2為支點進行的左旋：
文字描述一下就是谨敛，2的右孩子節(jié)點4究履，變?yōu)榱?的父節(jié)點，2由父節(jié)點變?yōu)?的左孩子脸狸。同時最仑，4原來的左孩子變?yōu)?的右孩子。
右旋
右旋與左旋相反炊甲，即以某節(jié)點為支點進行順時針旋轉(zhuǎn)泥彤。同樣，我們看下圖卿啡，是以5為支點進行的右旋:
文字描述同樣反過來吟吝，5的左孩子節(jié)點3，變?yōu)?的父節(jié)點颈娜，5由父節(jié)點變?yōu)?的右孩子剑逃。3原來的右孩子變?yōu)?的左孩子。
插入新節(jié)點
首先是在樹中找到新節(jié)點正確的位置官辽，尋找位置的過程與普通的二叉搜索樹相同蛹磺，只是將新插入的節(jié)點默認為紅色節(jié)點。為什么默認為紅色同仆？因為如果你將新節(jié)點默認為黑色称开，則插入后肯定會打破原本符合規(guī)則的紅黑樹（上述第5條規(guī)則）。但是乓梨，如果你將新節(jié)點定為紅色鳖轰，則有可能不用任何操作就符合紅黑樹規(guī)則，如下圖扶镀，當新插入的紅色節(jié)點蕴侣，它的父親節(jié)點為黑色時候，此時已經(jīng)滿足紅黑樹規(guī)則了臭觉。所以用紅色比黑色好昆雀。
如果很不巧辱志，新插入的節(jié)點的父親節(jié)點也為紅色，因為紅色節(jié)點不能連續(xù)狞膘，所以我們需要調(diào)整紅黑樹的結(jié)構使其滿足規(guī)則揩懒。在調(diào)整的過程中我們會遇到3種需要處理的情況，我們來一一進行說明挽封。
情況1：
插入新節(jié)點40已球，此時它的父節(jié)點為紅色，并且它的叔叔節(jié)點（即51）也為紅色辅愿。此時我們需要進行變色操作智亮。將該節(jié)點的父親節(jié)點、叔叔節(jié)點都變?yōu)楹谏愦娓腹?jié)點變?yōu)榧t色阔蛉。
此時上圖已經(jīng)滿足紅黑樹的規(guī)則。但有的時候我們經(jīng)過了變色操作后癞埠，仍不滿足紅黑樹的規(guī)則状原，會遇到下面的情況。
情況2：
如圖苗踪，我們插入新的節(jié)點53遭笋，在按情況1的操作變色后，變成了這樣:
此時徒探，49與44為兩個連續(xù)的紅色，顯然不符合規(guī)則喂窟。此時的操作為：我們將49看做當前節(jié)點测暗，將當前節(jié)點的父節(jié)點44變?yōu)楹谏娓腹?jié)點35置為紅色磨澡，以祖父節(jié)點為支點進行左旋碗啄。
此時情況2就處理完成了。
最后我們說一下情況3的情景稳摄，如下圖：
我們向樹中插入新節(jié)點37稚字，在按情況1的操作變色后，變成了這樣：
情況3：
此時厦酬，49與44為兩個連續(xù)的紅色胆描，顯然不符合規(guī)則。而我們只需以49為支點仗阅，進行一次右旋昌讲，就變成了情況2。如下圖减噪。
再按情況2進行一次操作就符合規(guī)則了短绸。
3種情況我們說明完了车吹，但是你可能還會有這樣的疑問，什么時候進行左旋醋闭，什么時候進行右旋窄驹；什么時候以父節(jié)點為支點旋轉(zhuǎn)，什么時候又以祖父節(jié)點為支點旋轉(zhuǎn)证逻？
那么我們可以總結(jié)一下乐埠，當遇到連續(xù)的紅色節(jié)點應該怎么辦：當前節(jié)點我們叫它X，如果X相對于父節(jié)點的左右位置和父節(jié)點相對于祖父節(jié)點的左右位置相同瑟曲，此時饮戳，就以祖父節(jié)點為支點，進行反向旋轉(zhuǎn)洞拨。例如：X為父節(jié)點的左孩子扯罐，X的父節(jié)點同樣也是其祖父節(jié)點的左孩子，此時以祖父節(jié)點為支點進行右旋烦衣；
如果X相對于父節(jié)點的左右位置和父節(jié)點相對于祖父節(jié)點的左右位置不同歹河，則以X的父節(jié)點為支點，進行旋轉(zhuǎn)花吟，旋轉(zhuǎn)方向與X相對于父節(jié)點左右位置相反秸歧。例如：X為其父節(jié)點的左孩子，X的父節(jié)點為祖父節(jié)點的右孩子衅澈，此時以X的父節(jié)點為支點進行一次右旋键菱。
刪除節(jié)點
在紅黑樹中刪除節(jié)點，肯定要涉及到要刪的這個節(jié)點是紅色的還是黑色的今布。刪除紅色比較簡單经备，我們先說一下刪除紅色節(jié)點。
刪除節(jié)點要考慮這個節(jié)點所處的位置部默，所以我們羅列一下紅色的節(jié)點所有可能的位置情況侵蒙。
- 它是一個葉子節(jié)點。
- 它既有左子樹也有右子樹傅蹂。
你可能會發(fā)現(xiàn)為什么少了一種情況纷闺？它不能只有左子樹或者只有右子樹嗎?我們可以看下圖:
很明顯均芽，這四種情況都不符合紅黑樹的規(guī)則昔期，所以根本不會出現(xiàn)這種情況。
而對于既有左子樹也有右子樹的情況尸执。我們可以先和普通的二叉搜索樹的刪除操作一樣婚夫，將它與前驅(qū)或者后繼交換一下波桩。它就又變成第一種情況——成為了一個葉子節(jié)點。所以我們只需考慮當它是葉子節(jié)點的情況请敦。
很簡單镐躲，直接刪除紅色葉子節(jié)點储玫。
接下來我們看一下當要刪除的節(jié)點是黑色的時候應該怎么辦。
同樣我們列一下節(jié)點位置可能的情況：
- 它是一個葉子節(jié)點萤皂。
- 它只有左子樹撒穷，或只有右子樹。
- 它既有左子樹也有右子樹裆熙。
第三種情況和刪除紅色節(jié)點時的處理方法一樣端礼，可以轉(zhuǎn)換成第一種或第二種情況，所以我們只關心前兩種情況入录。
當要刪除的黑色節(jié)點只有一個子樹時：
它的左孩子或者右孩子一定是紅色的蛤奥，因為如果是黑色的就不符合紅黑樹的規(guī)則了。
操作方法為：我們只需要將它的子節(jié)點變黑僚稿，然后代替它的位置就完成了凡桥。
最后我們看一下最難處理的一種情況。
要刪除的黑色節(jié)點是葉子節(jié)點時：
情況1：待刪除黑色節(jié)點20蚀同，它的兄弟節(jié)點為紅色缅刽。
此時的操作為，將兄弟節(jié)點和父節(jié)點顏色交換蠢络，即父親變紅衰猛，兄弟變黑。然后以父節(jié)點為支點進行左旋刹孔。(旋轉(zhuǎn)方向同樣是與待刪除節(jié)點的左右位置相同)
此時會變成了下述的情況4啡省，再按情況4進行操作就可以了。
情況2：待刪除黑色節(jié)點20髓霞，它的兄弟節(jié)點為黑色卦睹，并且它擁有紅色的遠侄子節(jié)點，近侄子節(jié)點有沒有都可以酸茴。（侄子節(jié)點即兄弟節(jié)點的子節(jié)點，遠侄子節(jié)點就是兢交，當前節(jié)點如果是其父節(jié)點的左孩子薪捍，那么它的遠侄子節(jié)點就是兄弟節(jié)點的右孩子，近侄子同理）
操作方法為：將遠侄子節(jié)點變黑配喳，兄弟節(jié)點與父親節(jié)點互換顏色酪穿，最后以父節(jié)點為支點進行左旋。(為什么是左旋晴裹？因為待刪除的20是左孩子被济，我們要將左子樹長度拉長，將它沉下來涧团，使它變成多余的節(jié)點好刪除它只磷，如果它是右孩子经磅，則進行右旋)
操作后如下圖就完成了。
情況3：待刪除黑色節(jié)點20钮追，它的兄弟節(jié)點為黑色预厌，但它沒有紅色的遠侄子節(jié)點(即nil點，記住元媚，nil點算黑色)轧叽，只有紅色的近侄子節(jié)點。
操作方法為：將兄弟節(jié)點與近侄子節(jié)點交換顏色刊棕，再以兄弟節(jié)點進行右旋炭晒。（旋轉(zhuǎn)方向很好記，因為此處旋轉(zhuǎn)的目的是為了創(chuàng)造遠侄子甥角，近侄子節(jié)點是左節(jié)點网严，所以就只能右旋了，如果近侄子是右節(jié)點則進行左旋蜈膨。）
操作后如下圖:
此時有了紅色的遠侄子屿笼，就滿足了情況2，再按情況2進行一次操作就完成了翁巍。
情況4：待刪除黑色節(jié)點20驴一，它的兄弟節(jié)點為黑色，遠侄子灶壶、近侄子節(jié)點都沒有肝断。(即兩個nil節(jié)點，nil節(jié)點算黑色)
操作方法為：將兄弟節(jié)點變?yōu)榧t色驰凛，同時最關鍵的是胸懈，將當前節(jié)點20的父節(jié)點50，看做當前節(jié)點恰响，繼續(xù)遞歸的進行這四種情況的判斷趣钱，直到當前節(jié)點為紅色，或者當前節(jié)點是根節(jié)點才停止胚宦。最后將當前節(jié)點變?yōu)楹谏首有。?/strong>
我們將上圖紅黑樹按流程演示一下:
第一步按情況4操作，將55變紅枢劝。并將父節(jié)點50看做當前節(jié)點井联，繼續(xù)操作。
此時當前節(jié)點61為紅色跃洛，滿足停止遞歸條件，將61變?yōu)楹谏找椋Ｖ够憬摺Ｕ麄€操作完成。
此時有關紅黑樹的知識就說完了穴张。
以上所有內(nèi)容都為自己查閱資料學習理解之后手敲的细燎。盡量得采用通俗易懂的描述和解釋讓讀者更明白。27張圖都是自己親自畫的皂甘，花費了四天才寫完玻驻，如果覺得寫的還可以，麻煩點亮喜歡支持一下偿枕，如果還是不懂璧瞬，可以下方留言QQ等聯(lián)系方式，我親自告訴你渐夸。
