紅黑樹
首先要理解二叉查找樹
二叉查找樹（BST）具備什么特性呢鲁冯？
左子樹上所有結(jié)點(diǎn)的值均小于或等于它的根結(jié)點(diǎn)的值。
右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值色查。
左薯演、右子樹也分別為二叉排序樹。
- 二叉查找樹是二分查找的思想秧了，查找所需的最大次數(shù)等同于二叉樹的高度跨扮。
- 在插入節(jié)點(diǎn)的時(shí)候也是利用類似的方法，一層一層比較大小验毡，找到合適的插入位置衡创。
- 如右圖，這樣雖然滿足了二叉查找樹的條件晶通，但是這個(gè)是瘸腿的二叉查找樹璃氢，就和鏈表沒有區(qū)別了。這是二叉查找樹的缺點(diǎn)
- 解決二叉查找樹多次插入新節(jié)點(diǎn)而導(dǎo)致的不平衡的方法狮辽，就是使用紅黑樹一也。
- 紅黑樹是一種自平衡的二叉查找樹。除了符合二叉查找樹的基本特性外喉脖，還具有下列的附加特性：
- 節(jié)點(diǎn)是紅色或黑色椰苟。
- 根節(jié)點(diǎn)是黑色。
- 每個(gè)葉子節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NIL節(jié)點(diǎn)）树叽。
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色舆蝴。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
- 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
- 上面一系列的規(guī)則，保證了紅黑樹的自平衡洁仗。紅黑樹從根到葉子的最長(zhǎng)路徑不會(huì)超過最短路徑的2倍
- 當(dāng)插入或刪除節(jié)點(diǎn)的時(shí)候层皱，紅黑樹的規(guī)則有可能被打破，這個(gè)時(shí)候需要進(jìn)行調(diào)整來維持紅黑樹的規(guī)則京痢。
如下圖奶甘，如果向原紅黑樹插入值為21的新節(jié)點(diǎn)，由于父節(jié)點(diǎn)22是紅色節(jié)點(diǎn)祭椰，因此這種情況打破了紅黑樹的規(guī)則4（每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色）臭家，必須進(jìn)行調(diào)整，使之重新符合紅黑樹的規(guī)則方淤。
- 調(diào)整的方法有兩種：
- 變色：紅變黑钉赁，黑變紅
- 旋轉(zhuǎn)：左旋轉(zhuǎn)和右旋轉(zhuǎn)
變換規(guī)則
- 旋轉(zhuǎn)和顏色變換規(guī)則：所有插入的點(diǎn)默認(rèn)為紅色
-
變顏色的情況：當(dāng)前結(jié)點(diǎn)的父親是紅色，且它的祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)也是紅色（叔叔結(jié)點(diǎn)）：
（1）把父節(jié)點(diǎn)設(shè)為黑色
（2）把叔叔也設(shè)為黑色
（3）把祖父也就是父親的父親設(shè)為紅色（爺爺）
（4）把指針定義到祖父結(jié)點(diǎn)設(shè)為當(dāng)前要操作的（爺爺）分析的點(diǎn)變換的規(guī)則
左旋：當(dāng)前父結(jié)點(diǎn)是紅色携茂，叔叔是黑色的時(shí)候你踩，且當(dāng)前的結(jié)點(diǎn)是右子樹。左旋以父節(jié)點(diǎn)作為左旋
-
右旋：當(dāng)前父結(jié)點(diǎn)是紅色讳苦，叔叔是黑色的時(shí)候带膜，且當(dāng)前的結(jié)點(diǎn)是左子樹。右旋
（1）把父節(jié)點(diǎn)變?yōu)楹谏?/strong>
（2）把祖父結(jié)點(diǎn)變?yōu)榧t色（爺爺）
（3）把祖父結(jié)點(diǎn)旋轉(zhuǎn)（爺爺）
變色
為了重新符合紅黑樹的規(guī)則鸳谜，嘗試把紅色節(jié)點(diǎn)變?yōu)楹谏ヅ海蛘甙押谏?jié)點(diǎn)變?yōu)榧t色。
-
下圖所表示的是紅黑樹的一部分咐扭，需要注意節(jié)點(diǎn)25并非根節(jié)點(diǎn)芭挽。因?yàn)楣?jié)點(diǎn)21和節(jié)點(diǎn)22連續(xù)出現(xiàn)了紅色，不符合規(guī)則4蝗肪，所以把節(jié)點(diǎn)22從紅色變成黑色：
-
但這樣并不算完袜爪，因?yàn)閼{空多出的黑色節(jié)點(diǎn)打破了規(guī)則5，所以發(fā)生連鎖反應(yīng)薛闪，需要繼續(xù)把節(jié)點(diǎn)25從黑色變成紅色：
-
此時(shí)仍然沒有結(jié)束辛馆，因?yàn)楣?jié)點(diǎn)25和節(jié)點(diǎn)27又形成了兩個(gè)連續(xù)的紅色節(jié)點(diǎn)，需要繼續(xù)把節(jié)點(diǎn)27從紅色變成黑色：
左旋轉(zhuǎn)
- 左旋轉(zhuǎn)豁延，就是將S點(diǎn)旋轉(zhuǎn)到根節(jié)點(diǎn)怀各，S節(jié)點(diǎn)的左邊都掛到E節(jié)點(diǎn)的右邊
- 就是將要旋轉(zhuǎn)的子結(jié)點(diǎn)的左邊掛到之前節(jié)點(diǎn)E的右邊
右旋轉(zhuǎn)
將要旋轉(zhuǎn)的子結(jié)點(diǎn)的右邊移到之前結(jié)點(diǎn)E的左邊
舉例說明
- 首先我們要插入結(jié)點(diǎn)6，按照二叉查找樹放在如下位置术浪。
-
我們發(fā)現(xiàn)結(jié)點(diǎn)6和結(jié)點(diǎn)7是紅色的瓢对，不滿足規(guī)則，下一步要判斷是變色還是旋轉(zhuǎn)
當(dāng)前結(jié)點(diǎn)的父親是紅色胰苏，且它的祖父結(jié)點(diǎn)的另一個(gè)子結(jié)點(diǎn)也是紅色硕蛹，我們要進(jìn)行的是變色。把父節(jié)點(diǎn)和叔叔設(shè)為黑色，把祖父也就是父親的父親設(shè)為紅色（爺爺）
-
我們發(fā)現(xiàn)結(jié)點(diǎn)5和結(jié)點(diǎn)12還是不滿足規(guī)則法焰。變色是說父親結(jié)點(diǎn)和叔叔結(jié)點(diǎn)都是紅色秧荆。不滿足，我們用旋轉(zhuǎn)埃仪。結(jié)點(diǎn)12位于結(jié)點(diǎn)5的右子樹上乙濒。用左旋。
[圖片上傳失敗...(image-b433f8-1585661664741)]
-
對(duì)結(jié)點(diǎn)5還要進(jìn)行右旋卵蛉。
（1）把父節(jié)點(diǎn)變?yōu)楹谏?/p>
（2）把祖父結(jié)點(diǎn)變?yōu)榧t色（爺爺）
（3）以爺爺結(jié)點(diǎn)旋轉(zhuǎn)
以上颁股。上面的紅黑樹就沒有問題了
