紅黑樹紅黑樹和AVL 樹一樣都是平衡二叉搜索樹。但是 AVL 樹 比紅黑樹更加嚴(yán)格AVL 樹要求左右子樹的高度差 1 而紅黑樹只能保證最長(zhǎng)路徑不超過(guò)最短路徑的 2 倍。AVL 樹通過(guò)旋轉(zhuǎn)控制平衡為了達(dá)到它嚴(yán)格的規(guī)定需要旋轉(zhuǎn)的次數(shù)較多。紅黑樹通過(guò)旋轉(zhuǎn) 變色控制平衡同時(shí)也因?yàn)橐?guī)定比較寬松所以旋轉(zhuǎn)的次數(shù)少。在插入方面顯然是紅黑樹更具有效率優(yōu)勢(shì)。在查找方面由于 AVL樹 比 紅黑樹 更平衡一些所以效率更快但它們的效率都是 O (log n)級(jí)別的所以紅黑樹瑕不掩瑜多數(shù)情況下使用的都比比AVL樹更多。紅黑樹的規(guī)則上面提到紅黑樹能保證最長(zhǎng)路徑不超過(guò)最短路徑的 2 倍。它是如何做到的呢這和紅黑樹的構(gòu)造規(guī)則相關(guān)如下1.每個(gè)節(jié)點(diǎn)不是紅色就是黑色。2.根節(jié)點(diǎn)是黑色的。3.如果一個(gè)節(jié)點(diǎn)是紅色的它的兩個(gè)孩子必須是黑色即不能連續(xù)出現(xiàn)兩次紅色節(jié)點(diǎn)。4.對(duì)于任意一個(gè)節(jié)點(diǎn)從該節(jié)點(diǎn)到其所有NULL節(jié)點(diǎn)的簡(jiǎn)單路徑上均包含相同數(shù)量的黑色節(jié)點(diǎn)。這四條規(guī)則共同約束了樹的結(jié)構(gòu)最終保證了紅黑樹的核心性質(zhì)從任意節(jié)點(diǎn)出發(fā)到其所有葉子節(jié)點(diǎn)的最長(zhǎng)路徑不會(huì)超過(guò)最短路徑的 2 倍。舉一些例子仔細(xì)觀察你會(huì)發(fā)現(xiàn)這些樹都滿足了紅黑樹的規(guī)則同時(shí)它們也做到了最長(zhǎng)路徑不超過(guò)最短路徑的2倍。紅黑樹的調(diào)整AVL樹于1962年誕生紅黑樹比它晚了 10 年所謂前人栽樹后人乘涼紅黑樹 的旋轉(zhuǎn)調(diào)整邏輯和 AVL樹 完全一致AVL樹在上一篇博客講過(guò)那么我們接下來(lái)所需要討論就是紅黑樹的專屬調(diào)整邏輯變色。在講調(diào)整邏輯之前我們得先搞清楚什么情況下需要調(diào)整。從第一個(gè)規(guī)則可知新插入的節(jié)點(diǎn)非黑即紅我們來(lái)分類討論黑當(dāng)插入節(jié)點(diǎn)為黑色時(shí)我們會(huì)違法第四個(gè)規(guī)則因?yàn)椴迦胍粋€(gè)黑色節(jié)點(diǎn)無(wú)論如何都不能保持每條路徑上的黑色節(jié)點(diǎn)相同了注意走到空節(jié)點(diǎn)才算一條路徑所以絕對(duì)不能插入黑色節(jié)點(diǎn)。沒(méi)錯(cuò)即使插入節(jié)點(diǎn)是 root 我們也應(yīng)該插入紅色節(jié)點(diǎn)然后再讓它變色。紅既然不能插入黑色那么插入的必然就是紅色節(jié)點(diǎn)了。但是插入紅色節(jié)點(diǎn)的情況有兩種通過(guò)父節(jié)點(diǎn)來(lái)區(qū)分。父節(jié)點(diǎn)為黑沒(méi)有違法任何規(guī)則即滿足紅黑樹故無(wú)需調(diào)整。父節(jié)點(diǎn)為紅違反第三個(gè)規(guī)則此時(shí)我們就需要進(jìn)行調(diào)整了。那么如何調(diào)整呢先看圖上圖是一顆新插入了節(jié)點(diǎn)的紅黑樹為了方便說(shuō)明我們對(duì)調(diào)整所需的相關(guān)節(jié)點(diǎn)進(jìn)行標(biāo)記新節(jié)點(diǎn)為 c意為current表示當(dāng)前節(jié)點(diǎn)新節(jié)點(diǎn)的父節(jié)點(diǎn)為 p 意為parent表示父節(jié)點(diǎn)父節(jié)點(diǎn)的兄弟為 u意為uncle表示 “叔叔” 節(jié)點(diǎn)父節(jié)點(diǎn)的父節(jié)點(diǎn)為 g意為grandparent意為 “爺爺” 節(jié)點(diǎn)。對(duì)紅黑樹的調(diào)整最關(guān)鍵的就是 “叔叔” 節(jié)點(diǎn)。在上面這顆樹中 p 和u 存在且為紅色g 為黑色此時(shí)我們將 p 和 u 變?yōu)楹谏玤 變?yōu)榧t色完美解決啦但當(dāng) u 不存在或者u 為黑色的時(shí)候單純的變色是無(wú)法解決問(wèn)題的比如u 不存在時(shí)此時(shí)樹的結(jié)構(gòu)違反第四個(gè)規(guī)則。從根節(jié)點(diǎn)到 g 再到 g 的右孩子這條路徑比其他路徑少一個(gè)黑節(jié)點(diǎn)。那么怎么辦答案是旋轉(zhuǎn)只需要對(duì) g 為根節(jié)點(diǎn)的樹進(jìn)行一次右單旋即可解決問(wèn)題。當(dāng) c 節(jié)點(diǎn)插入在 p 的不同位置時(shí)使用的旋轉(zhuǎn)方法不同u 為黑色時(shí)u 是黑色節(jié)點(diǎn)的情況是什么樣的按照之前的邏輯既然我們需要調(diào)整了那么 c 與 p 必然是紅色節(jié)點(diǎn)g 必然是黑色節(jié)點(diǎn)如果 u 是黑色原來(lái)的樹不是違反規(guī)則了嗎我們難道能給一顆違反規(guī)則的樹插入節(jié)點(diǎn)嗎我們當(dāng)然不能給一顆違反規(guī)則的樹插入節(jié)點(diǎn)但是想象一下當(dāng)我們某次調(diào)整時(shí)對(duì) g 進(jìn)行變色本來(lái)是黑色的 g 變成了 紅色。此時(shí)如果 g 的父節(jié)點(diǎn)也是紅色那么我們的調(diào)整并沒(méi)有將樹調(diào)整好需要繼續(xù)向上進(jìn)行我們將 g 設(shè)置為 c 當(dāng)前節(jié)點(diǎn)就有可能出現(xiàn)新的 c 節(jié)點(diǎn)的 u 節(jié)點(diǎn)為黑色的情況。對(duì)于這樣一顆樹我們要做的是 變色加旋轉(zhuǎn) 。經(jīng)過(guò) 變色加旋轉(zhuǎn) 處理的不需要繼續(xù)向上調(diào)整。這里給出插入的核心代碼因?yàn)榇a量比較大這里只貼了核心代碼的一部分另一部分邏輯類似。