紅黑樹是一個(gè)基本平衡的二叉樹，在查詢方面铲咨，與二叉查找樹思路相同;在插入方面躲胳，單次回溯不會(huì)超過2次旋轉(zhuǎn);在刪除方面，單次回溯不會(huì)超過3次旋轉(zhuǎn)!
紅黑樹由來：在1972年由Rudolf Bayer發(fā)明的纤勒，當(dāng)時(shí)被稱為平衡二叉B樹(symmetric binary B-trees)坯苹，后來，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改為如今的紅黑樹摇天，就此紅黑樹出現(xiàn)在軟件開發(fā)者的視野里!
一粹湃、摘要
在上篇文章中，我們詳細(xì)的介紹到平衡二叉查找樹的算法以及代碼實(shí)踐泉坐，我們知道平衡二叉查找樹是一個(gè)高度平衡的二叉樹为鳄，也就是說樹的高度差不能大于1，在刪除的時(shí)候腕让，可能需要多次調(diào)整孤钦，也就是左旋轉(zhuǎn)、右旋轉(zhuǎn)操作记某，在樹的深度很大的情況下司训，刪除效率會(huì)非常低，如何提高這種效率?
紅黑樹由此誕生了液南，了解過紅黑樹的朋友們一定知道壳猜，紅黑樹是一個(gè)基本平衡的二叉樹，英文全稱：red-black-tree滑凉，簡稱：RBT统扳，特性如下：
1.每個(gè)節(jié)點(diǎn)要么是黑色要么是紅色;
2.根節(jié)點(diǎn)是黑色;
3.每個(gè)葉子節(jié)點(diǎn)是黑色;(注意：這里葉子節(jié)點(diǎn)，是指為空的葉子節(jié)點(diǎn))
4.如果一個(gè)節(jié)點(diǎn)是紅色的畅姊，則它的子節(jié)點(diǎn)必須是黑色的;(說明父子節(jié)點(diǎn)之間不能出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn))
5.從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn);
關(guān)于它的特性咒钟，需要注意的是:
特性3中的葉子節(jié)點(diǎn)，是只為空(NIL 或 null)的節(jié)點(diǎn);
特性5若未，確保沒有一條路徑會(huì)比其他路徑長出倆倍朱嘴，因而，紅黑樹是相對的接近平衡的二叉樹!(比如粗合，包含相同數(shù)目為3的黑節(jié)點(diǎn)路線萍嬉，最短路線：`黑節(jié)點(diǎn) -> 黑節(jié)點(diǎn) -> 黑節(jié)點(diǎn)`，長度為3;最長路線：`黑節(jié)點(diǎn) -> 紅節(jié)點(diǎn) -> 黑節(jié)點(diǎn) -> 紅節(jié)點(diǎn) -> 黑節(jié)點(diǎn)`隙疚，長度為5)
紅黑樹示例圖壤追，如下：
紅黑樹，與二叉樹供屉，在查詢行冰、插入溺蕉、刪除方面，都是一樣的悼做，最大的不同點(diǎn)是疯特，插入、刪除需要重新調(diào)整樹的形態(tài)贿堰，以保持紅黑樹的特性!
二辙芍、算法思路
在上篇平衡二叉樹的文章中啡彬，我們了解到為了保證樹的高度差不超過1羹与，我們通過樹高超過1這么一個(gè)判斷條件，通過左旋轉(zhuǎn)庶灿、右旋轉(zhuǎn)來調(diào)整纵搁，從而保證樹的高度平衡!
對于紅黑樹，其實(shí)也是一樣的往踢，對于插入腾誉、刪除操作，主要也是通過左旋轉(zhuǎn)峻呕、右旋轉(zhuǎn)來進(jìn)行調(diào)整利职，相比平衡二叉樹，紅黑樹因?yàn)楣?jié)點(diǎn)有顏色標(biāo)簽瘦癌，多了一個(gè)顏色轉(zhuǎn)變操作!
同理猪贪，我們只需要分析出哪些場景下需要進(jìn)行調(diào)整，即可總結(jié)出算法讯私，從而寫出實(shí)踐代碼!
廢話也不多說來热押，下面我們一起來分析一下紅黑樹，在插入斤寇、刪除操作時(shí)桶癣，應(yīng)該怎么處理!
2.1、插入場景
將一個(gè)節(jié)點(diǎn)插入到紅黑樹中娘锁，需要執(zhí)行哪些步驟呢?
第一步：將紅黑樹當(dāng)作一顆二叉查找樹牙寞，將節(jié)點(diǎn)插入樹的底部;
第二步：默認(rèn)將插入的節(jié)點(diǎn)著色為紅色，如果是根節(jié)點(diǎn)莫秆，顏色著為黑色;
第三步：通過一系列的旋轉(zhuǎn)或著色等操作间雀，使之重新成為一顆紅黑樹;
對于第一步，比較好理解馏锡，紅黑樹其實(shí)就是二叉樹的一種特殊形態(tài)的樹形結(jié)構(gòu)雷蹂，先找到合適的位置，然后將節(jié)點(diǎn)插入到樹上杯道。
對于第二步匪煌，為什么新插入的節(jié)點(diǎn)要設(shè)置為紅色呢?
因?yàn)椴迦胫八懈镣獠抗?jié)點(diǎn)的路徑上黑色節(jié)點(diǎn)數(shù)目都相同责蝠，所以如果插入的節(jié)點(diǎn)是黑色，肯定會(huì)導(dǎo)致黑色節(jié)點(diǎn)數(shù)目不相同!
而相對的插入紅節(jié)點(diǎn)可能也會(huì)違反不能出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn)萎庭，如果違反條件霜医，直接進(jìn)行顏色轉(zhuǎn)換或者旋轉(zhuǎn)操作即可!
相對將插入的節(jié)點(diǎn)著色為黑色，紅色操作可能更簡單些!因?yàn)楦?jié)點(diǎn)為黑色驳规，如果是新插入的節(jié)點(diǎn)為根節(jié)點(diǎn)肴敛，直接將顏色設(shè)置為黑色!
既然新插入的節(jié)點(diǎn)為紅色，那么我們就繼續(xù)來分析一下吗购，新插入節(jié)點(diǎn)的場景医男，例如：
1.插入的節(jié)點(diǎn)，父親為黑色;
2.插入的節(jié)點(diǎn)捻勉，父親為紅色;
當(dāng)新插入的節(jié)點(diǎn)的父親為黑色時(shí)!因?yàn)樾虏迦氲墓?jié)點(diǎn)為紅色镀梭，因此不會(huì)違反任何特性!
當(dāng)新插入的節(jié)點(diǎn)的父親為紅色時(shí)!因?yàn)樾虏迦氲墓?jié)點(diǎn)為紅色，違反不能出現(xiàn)兩個(gè)連續(xù)的紅節(jié)點(diǎn)踱启，因此需要進(jìn)行調(diào)整!
這種場景有3種調(diào)整情況报账，為了便于下面分析，假設(shè)將新插入節(jié)點(diǎn)用z代替埠偿，z的父節(jié)點(diǎn)用a代替透罢，a的父節(jié)點(diǎn)用c代替，z的叔節(jié)點(diǎn)用y代替冠蒋，如下：
情況1：z的叔節(jié)點(diǎn)y是紅色的
case1調(diào)整過程如下：
調(diào)整說明：因?yàn)楣?jié)點(diǎn) z 是一個(gè)紅色節(jié)點(diǎn)羽圃，其父節(jié)點(diǎn) a 是紅色的，違反了特性4浊服，因此需要進(jìn)行調(diào)整统屈。因?yàn)槠涫骞?jié)點(diǎn) y 是紅色的，于是可以修改節(jié)點(diǎn) a牙躺、節(jié)點(diǎn) y 為黑色愁憔，此時(shí)節(jié)點(diǎn) c 的黑高會(huì)發(fā)生變化，由原來的黑高1變成黑高2孽拷，為了節(jié)點(diǎn) c 保持黑高不變吨掌，將其變成紅色。
此時(shí)脓恕，由于節(jié)點(diǎn) c 由黑色變成了紅色膜宋，如果節(jié)點(diǎn) c 的父節(jié)點(diǎn)是紅色，也會(huì)違反特性4炼幔，繼續(xù)將節(jié)點(diǎn) c 看成是節(jié)點(diǎn) z音五，向上回溯調(diào)整樹!
需要注意的是：對于新插入的節(jié)點(diǎn) z 是節(jié)點(diǎn)a 的左子樹的情況宙彪，操作與上述一致;對于新插入的節(jié)點(diǎn) z 是節(jié)點(diǎn) c 的右子樹的節(jié)點(diǎn)的情況，操作與上述對稱!
情況2：z的叔節(jié)點(diǎn)y是黑色摆寄，且z是一個(gè)左孩子
case2調(diào)整過程如下：
調(diào)整說明：這種情況诱建，并不能像上面那樣改變節(jié)點(diǎn)顏色就可以滿足要求，因?yàn)槿绻麑⒐?jié)點(diǎn)z 的父節(jié)點(diǎn) a 變成了黑色， 那么樹的黑高就會(huì)發(fā)生變化，必然會(huì)引起對性質(zhì)5的違反殉农。比如，此時(shí)節(jié)點(diǎn)y為黑色局荚， 節(jié)點(diǎn)c 的右子樹高度為2(忽略子樹)超凳，左子樹高也相同，如果簡單的修改節(jié)點(diǎn)a 為黑色耀态，那么節(jié)點(diǎn)c 的左子樹的黑高會(huì)比右子樹大1轮傍， 此時(shí)即使將節(jié)點(diǎn)c 修改為紅色也于事無補(bǔ)!
因此，單靠顏色轉(zhuǎn)變無非解決問題茫陆，需要進(jìn)行旋轉(zhuǎn)調(diào)整金麸。先繞節(jié)點(diǎn) a 的父節(jié)點(diǎn)進(jìn)行右旋轉(zhuǎn)，再將節(jié)點(diǎn) a簿盅、節(jié)點(diǎn) c 的顏色進(jìn)行互換!最終結(jié)果與插入前一致!
需要注意的是：對于新插入的節(jié)點(diǎn) z 是節(jié)點(diǎn) c 的右子樹的節(jié)點(diǎn)的情況，操作與上述對稱!
情況3：z的叔節(jié)點(diǎn)y是黑色揍魂，且z是一個(gè)右孩子
case3調(diào)調(diào)整過程如下：
調(diào)整說明：當(dāng)節(jié)點(diǎn) z 是一個(gè)右孩子時(shí)桨醋，先繞節(jié)點(diǎn) a 進(jìn)行左旋轉(zhuǎn)，之后樹的形態(tài)就變成如上面介紹的情況2现斋，再進(jìn)行右旋轉(zhuǎn)喜最、顏色轉(zhuǎn)變，即可實(shí)現(xiàn)紅黑樹的特性!
需要注意的是：對于新插入的節(jié)點(diǎn) z 是節(jié)點(diǎn) c 的右子樹的節(jié)點(diǎn)的情況庄蹋，操作與上述對稱!
以上就是紅黑樹新增節(jié)點(diǎn)時(shí)瞬内，所有可能的操作以及調(diào)整方式!
可以得出如下結(jié)論：對插入節(jié)點(diǎn)后的調(diào)整所做的旋轉(zhuǎn)操作不會(huì)超過2次!
2.2、刪除場景
我們繼續(xù)來看看刪除場景限书，對于二叉查找樹操作虫蝶，我們知道有如下步驟：
當(dāng)刪除節(jié)點(diǎn)，只有左子樹時(shí)倦西，將右子樹向上移動(dòng);
當(dāng)刪除節(jié)點(diǎn)能真，只有右子樹時(shí)，將左子樹向上移動(dòng);
當(dāng)刪除節(jié)點(diǎn)扰柠，有左粉铐、右子樹時(shí)，通過找到刪除節(jié)點(diǎn)的右節(jié)點(diǎn)的最末端左子樹卤档，也就是后繼節(jié)點(diǎn)蝙泼，進(jìn)行替換并刪除;
二叉查找樹刪除過程圖：
紅黑樹的操作也是如此，步驟如下;
第一步：將紅黑樹當(dāng)作一顆二叉查找樹劝枣，將節(jié)點(diǎn)刪除;
第二步：通過旋轉(zhuǎn)和變色等一系列來修正該樹汤踏，使之重新成為一棵紅黑樹;
在第一步中倡缠，首先我們重點(diǎn)要弄清楚什么是刪除節(jié)點(diǎn)?
這個(gè)刪除節(jié)點(diǎn)，某些情況下并非我們真正傳入的刪除值茎活，對于擁有左子樹昙沦、右子樹的節(jié)點(diǎn)來說，刪除節(jié)點(diǎn)指的是被刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)或者前驅(qū)節(jié)點(diǎn)!
可能有點(diǎn)繞载荔，例如上圖中擁有左子樹盾饮、右子樹的刪除場景，我們傳入需要?jiǎng)h除的節(jié)點(diǎn)是 80懒熙，但是實(shí)際上刪除節(jié)點(diǎn)的是85節(jié)點(diǎn)(85是一個(gè)葉子節(jié)點(diǎn))丘损，然后將80節(jié)點(diǎn)內(nèi)容替換成85，做了一個(gè)偷天換日的操作!
因此無論對于哪種情況工扎，我們可以得出結(jié)論：刪除節(jié)點(diǎn)一定是一個(gè)單分支節(jié)點(diǎn)或者葉子節(jié)點(diǎn)徘钥，了解這個(gè)結(jié)論對于后面我們的紅黑樹刪除過程分析會(huì)非常有用!
清楚刪除流程之后，剩下的重點(diǎn)就是如何進(jìn)行修正肢娘，以滿足紅黑樹的特性呈础，那么，哪些場景下的刪除需要進(jìn)行調(diào)整橱健，我們一起來看一下!
2.2.1而钞、刪除的節(jié)點(diǎn)為紅色
當(dāng)刪除的節(jié)點(diǎn)為紅色時(shí)，這種情況直接將刪除節(jié)點(diǎn)移除拘荡，理由如下：
樹中各個(gè)節(jié)點(diǎn)的黑高沒有變化;
刪除后滿足性質(zhì)4臼节，因?yàn)椴粫?huì)出現(xiàn)紅紅相連的情況;
刪除的不可能是根節(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)是黑色的;
2.2.2珊皿、刪除的節(jié)點(diǎn)為黑色
當(dāng)刪除的節(jié)點(diǎn)為黑色時(shí)网缝，因?yàn)閯h除節(jié)點(diǎn)的父節(jié)點(diǎn)失去了一個(gè)黑色子節(jié)點(diǎn)，這種情況會(huì)導(dǎo)致左右子樹不平衡蟋定，因此需要進(jìn)行調(diào)整粉臊，假設(shè)x為被刪節(jié)點(diǎn)的替換節(jié)點(diǎn)，也就是說：
當(dāng)被刪節(jié)點(diǎn)的左子樹為空時(shí)溢吻，x為被刪節(jié)點(diǎn)的右孩子;
當(dāng)被刪節(jié)點(diǎn)的右子樹為空時(shí)维费，x為被刪節(jié)點(diǎn)的左孩子;
當(dāng)被刪節(jié)點(diǎn)的左、右子樹都為空時(shí)促王，x是空節(jié)點(diǎn)(即刪除的是終端節(jié)點(diǎn));
當(dāng)被刪節(jié)點(diǎn)的左犀盟、右子樹都不為空時(shí)，x為被刪節(jié)點(diǎn)的右子樹的最末端的左子樹蝇狼，也就是中序遍歷直接后繼的右孩子;
w為x的兄弟節(jié)點(diǎn)阅畴，有以下幾種情況!
1)x的兄弟節(jié)點(diǎn)w是紅色的
case1調(diào)整過程如下：
調(diào)整說明：因?yàn)楣?jié)點(diǎn) c 的左子樹被刪去了一個(gè)黑色節(jié)點(diǎn)，導(dǎo)致節(jié)點(diǎn) c 的左子樹黑高少了1迅耘，所以節(jié)點(diǎn)c 是不平衡的贱枣〖嗍穑可以對節(jié)點(diǎn)c 進(jìn)行一次左旋，然后修改節(jié)點(diǎn)80和節(jié)點(diǎn)120的顏色纽哥。
此時(shí)钠乏，x的父親節(jié)點(diǎn)c依然不平衡，節(jié)點(diǎn)x 的兄弟節(jié)點(diǎn)w 變成黑色的!
繼續(xù)看下面的分析春塌，這種不平衡由下面的幾種情況進(jìn)行處理!
2)x的兄弟節(jié)點(diǎn)w是黑色的晓避，并且w的兩個(gè)子節(jié)點(diǎn)都是黑色的
當(dāng)x的兄弟節(jié)點(diǎn) w 是黑色的，并且w的兩個(gè)子節(jié)點(diǎn)都是黑色的時(shí)只壳，此時(shí)需要分兩種情況!
情況2.1：x的父節(jié)點(diǎn)為紅色
case2.1調(diào)整過程如下：
調(diào)整說明：在刪除節(jié)點(diǎn)后俏拱，左圖節(jié)點(diǎn) c 不平衡，節(jié)點(diǎn)c 左子樹的黑高為hl+1吼句，節(jié)點(diǎn)c 左子樹的黑高為hr+2锅必，左子樹黑高小于右子樹黑高。因此直接將節(jié)點(diǎn)c 修改為黑色惕艳，節(jié)點(diǎn) w 修改為紅色搞隐，此時(shí)的黑高又恢復(fù)如初!但是節(jié)點(diǎn)c 作為子節(jié)點(diǎn)，因?yàn)楹诟邷p少尔艇，需要繼續(xù)向上回溯調(diào)整樹的黑高尔许，此時(shí)節(jié)點(diǎn)c 作為新的節(jié)點(diǎn)x。
情況2.2：x的父節(jié)點(diǎn)為黑色
case2.2調(diào)整過程如下：
調(diào)整說明：只需要將節(jié)點(diǎn) w 修改為紅色终娃，繼續(xù)向上回溯調(diào)整樹的黑高，此時(shí)節(jié)點(diǎn) c 作為新的節(jié)點(diǎn)x蒸甜。
3)x的兄弟節(jié)點(diǎn)w是黑色的棠耕，并且w的右孩子是紅色的
當(dāng)x的兄弟節(jié)點(diǎn)w是黑色的，并且w的右孩子是紅色的柠新，此時(shí)也需要分四種情況!
情況3.1：x的父節(jié)點(diǎn)為黑色窍荧，w的左孩子是黑色的
case3.1調(diào)整過程如下：
調(diào)整說明：因?yàn)閯h除節(jié)點(diǎn)導(dǎo)致節(jié)點(diǎn)c 不平衡，對節(jié)點(diǎn)c 進(jìn)行一次左旋轉(zhuǎn)恨憎，將節(jié)點(diǎn)w 的右孩子顏色修改為黑色蕊退。此時(shí)節(jié)點(diǎn)c 已經(jīng)達(dá)到平衡，同時(shí)節(jié)點(diǎn)w 也達(dá)到平衡憔恳，整棵樹已經(jīng)平衡了!
情況3.2：x的父節(jié)點(diǎn)為黑色瓤荔，w的左孩子是紅色的
case3.2調(diào)整過程如下：
調(diào)整說明：同樣的，對節(jié)點(diǎn)c 進(jìn)行一次左旋轉(zhuǎn)钥组，將節(jié)點(diǎn)w 的右孩子顏色修改為黑色输硝。此時(shí)節(jié)點(diǎn)c 已經(jīng)達(dá)到平衡，同時(shí)節(jié)點(diǎn)w 也達(dá)到平衡程梦，整棵樹已經(jīng)平衡了!
情況3.3：x的父節(jié)點(diǎn)為紅色点把，w的左孩子是黑色的
case3.3調(diào)整過程如下：
調(diào)整說明：對節(jié)點(diǎn)c 進(jìn)行一次左旋轉(zhuǎn)橘荠，將節(jié)點(diǎn) w 的右孩子顏色修改為黑色，同時(shí)將節(jié)點(diǎn)80 和節(jié)點(diǎn)100 顏色進(jìn)行互換郎逃。此時(shí)節(jié)點(diǎn)c 已經(jīng)達(dá)到平衡哥童，同時(shí)節(jié)點(diǎn)w 也達(dá)到平衡，整棵樹已經(jīng)平衡了!
情況3.4：x的父節(jié)點(diǎn)為紅色褒翰，w的左孩子是紅色的
case3.4調(diào)整過程如下：
調(diào)整說明：同樣的贮懈，對節(jié)點(diǎn)c 進(jìn)行一次左旋轉(zhuǎn)，將節(jié)點(diǎn) w 的右孩子顏色修改為黑色影暴，同時(shí)將節(jié)點(diǎn)80 和節(jié)點(diǎn)100 顏色進(jìn)行互換错邦。此時(shí)節(jié)點(diǎn)c 已經(jīng)達(dá)到平衡，同時(shí)節(jié)點(diǎn)w 也達(dá)到平衡型宙，整棵樹已經(jīng)平衡了!
4)x的兄弟節(jié)點(diǎn)w是黑色的撬呢，而且w的左孩子是紅色的，w的右孩子是黑色的
當(dāng)x的兄弟節(jié)點(diǎn)w是黑色的妆兑，而且w的左孩子是紅色的魂拦，w的右孩子是黑色的，此時(shí)也需要分2種情況!
情況4.1：x的父節(jié)點(diǎn)為紅色
case4.1調(diào)整過程如下：
調(diào)整說明：對節(jié)點(diǎn)w 進(jìn)行一次右旋轉(zhuǎn)搁嗓，將節(jié)點(diǎn)90和節(jié)點(diǎn)100 進(jìn)行顏色互換芯勘，此時(shí)節(jié)點(diǎn)x 和節(jié)點(diǎn)w 的關(guān)系變成：x的兄弟節(jié)點(diǎn)w是黑色的，并且w的右孩子是紅色的腺逛。此時(shí)按照case3.3情況進(jìn)行處理即可!
情況4.2：x的父節(jié)點(diǎn)為黑色
case4.2調(diào)整過程如下：
調(diào)整說明：同樣的荷愕，對節(jié)點(diǎn)w 進(jìn)行一次右旋轉(zhuǎn)，將節(jié)點(diǎn)90和節(jié)點(diǎn)100進(jìn)行顏色互換棍矛，此時(shí)節(jié)點(diǎn)x 和節(jié)點(diǎn)w 的關(guān)系變成：x的兄弟節(jié)點(diǎn)w是黑色的安疗，并且w的右孩子是紅色的。此時(shí)按照case3.1情況進(jìn)行處理即可!
刪除的場景相比插入要多很多够委，情況也比較復(fù)雜荐类，但是基本有自己的規(guī)律，我們只需要把規(guī)律總結(jié)出來茁帽，然后就可以用邏輯代碼來實(shí)現(xiàn)!
需要注意的是：此次節(jié)點(diǎn)x 位于節(jié)點(diǎn)c 的左子樹玉罐，如果位于右子樹，操作與之對稱!
可以得出如下結(jié)論：對刪除節(jié)點(diǎn)后的調(diào)整所做的旋轉(zhuǎn)操作不會(huì)超過3次!
三潘拨、代碼實(shí)踐
接下來吊输，我們從代碼層面來定義一下樹的實(shí)體結(jié)構(gòu)，如下：
public?class?RBTNode<E?extends?Comparable<E>>?{?
????/**節(jié)點(diǎn)顏色*/?
????boolean?color;?
????/**節(jié)點(diǎn)關(guān)鍵字*/?
Ekey;?
????/**父節(jié)點(diǎn)*/?
????RBTNode<E>?parent;?
????/**左子節(jié)點(diǎn)*/?
RBTNodeleft;?
????/**右子節(jié)點(diǎn)*/?
RBTNoderight;?
public?RBTNode(E?key,?boolean?color,?RBTNode<E>?parent,?RBTNode<E>?left,?RBTNode<E>?right)?{?
this.key?=?key;?
????????this.color?=?color;?
????????this.parent?=?parent;?
this.left?=?left;?
this.right?=?right;?
????}?
????@Override?
public?String?toString()?{?
return?"RBTNode{"?+?
"color="?+?(color???"red":"black")?+?
",?key="?+?key?+?
'}';?
????}?
}?
我們創(chuàng)建一個(gè)算法類RBTSolution战秋，完整實(shí)現(xiàn)如下：
public?class?RBTSolution<E?extends?Comparable<E>>?{?
????/**根節(jié)點(diǎn)*/?
public?RBTNode<E>?root;?
????/**?
*?顏色常量false表示紅色璧亚，true表示黑色?
?????*/?
privatestatic?final?boolean?RED?=?false;?
privatestatic?final?boolean?BLACK?=?true;?
????/*?
*?新建結(jié)點(diǎn)(key)，并將其插入到紅黑樹中?
*?參數(shù)說明：key?插入結(jié)點(diǎn)的鍵值?
?????*/?
public?void?insert(E?key)?{?
System.out.println("插入["?+?key?+?"]:");?
RBTNode?node=new?RBTNode(key,?BLACK,null,null,null);?
????????//?如果新建結(jié)點(diǎn)失敗，則返回癣蟋。?
if?(node?!=null)?
insert(node);?
????}?
????/*?
?????*?將結(jié)點(diǎn)插入到紅黑樹中?
?????*?
?????*?參數(shù)說明：?
?????*?????node?插入的結(jié)點(diǎn)????????//?對應(yīng)《算法導(dǎo)論》中的node?
?????*/?
private?voidinsert(RBTNode<E>?node)?{?
int?cmp;?
RBTNode?y?=null;?
????????RBTNode<E>?x?=?this.root;?
????????//?1.?將紅黑樹當(dāng)作一顆二叉查找樹透硝，將節(jié)點(diǎn)添加到二叉查找樹中。?
while?(x?!=null)?{?
????????????y?=?x;?
cmp?=?node.key.compareTo(x.key);?
????????????if?(cmp?<?0)?
x?=?x.left;?
else?
x?=?x.right;?
????????}?
????????node.parent?=?y;?
if?(y!=null)?{?
cmp?=?node.key.compareTo(y.key);?
????????????if?(cmp?<?0)?
y.left?=?node;?
else?
y.right?=?node;?
}else?{?
????????????this.root?=?node;?
????????}?
????????//?2.?設(shè)置節(jié)點(diǎn)的顏色為紅色?
????????node.color?=?RED;?
????????//?3.?將它重新修正為一顆二叉查找樹?
????????insertFixUp(node);?
????}?
????/*?
?????*?紅黑樹插入修正函數(shù)?
?????*?
?????*?在向紅黑樹中插入節(jié)點(diǎn)之后(失去平衡)疯搅，再調(diào)用該函數(shù)濒生；?
?????*?目的是將它重新塑造成一顆紅黑樹。?
?????*?
?????*?參數(shù)說明：?
?????*?????node?插入的結(jié)點(diǎn)????????//?對應(yīng)《算法導(dǎo)論》中的z?
?????*/?
????private?void?insertFixUp(RBTNode<E>?node)?{?
????????RBTNode<E>?parent,?gparent;?
????????//?若“父節(jié)點(diǎn)存在幔欧，并且父節(jié)點(diǎn)的顏色是紅色”?
while?(((parent?=?parentOf(node))!=null)?&&?isRed(parent))?{?
????????????gparent?=?parentOf(parent);?
????????????//若“父節(jié)點(diǎn)”是“祖父節(jié)點(diǎn)的左孩子”?
if?(parent?==?gparent.left)?{?
//Case?1條件：叔叔節(jié)點(diǎn)是紅色?
RBTNode?uncle?=?gparent.right;?
if?((uncle!=null)?&&?isRed(uncle))?{?
????????????????????setBlack(uncle);?
????????????????????setBlack(parent);?
????????????????????setRed(gparent);?
????????????????????node?=?gparent;?
continue;?
????????????????}?
//Case?3條件：叔叔是黑色罪治，且當(dāng)前節(jié)點(diǎn)是右孩子?
if?(parent.right?==?node)?{?
????????????????????RBTNode<E>?tmp;?
????????????????????leftRotate(parent);?
????????????????????tmp?=?parent;?
????????????????????parent?=?node;?
????????????????????node?=?tmp;?
????????????????}?
//Case?2條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是左孩子礁蔗。?
????????????????setBlack(parent);?
????????????????setRed(gparent);?
????????????????rightRotate(gparent);?
}else?{????//若“z的父節(jié)點(diǎn)”是“z的祖父節(jié)點(diǎn)的右孩子”?
//Case?1條件：叔叔節(jié)點(diǎn)是紅色?
RBTNode?uncle?=?gparent.left;?
if?((uncle!=null)?&&?isRed(uncle))?{?
????????????????????setBlack(uncle);?
????????????????????setBlack(parent);?
????????????????????setRed(gparent);?
????????????????????node?=?gparent;?
continue;?
????????????????}?
//Case?2條件：叔叔是黑色觉义，且當(dāng)前節(jié)點(diǎn)是左孩子?
if?(parent.left?==?node)?{?
????????????????????RBTNode<E>?tmp;?
????????????????????rightRotate(parent);?
????????????????????tmp?=?parent;?
????????????????????parent?=?node;?
????????????????????node?=?tmp;?
????????????????}?
//Case?3條件：叔叔是黑色，且當(dāng)前節(jié)點(diǎn)是右孩子浴井。?
????????????????setBlack(parent);?
????????????????setRed(gparent);?
????????????????leftRotate(gparent);?
????????????}?
????????}?
????????//?將根節(jié)點(diǎn)設(shè)為黑色?
????????setBlack(this.root);?
????}?
????/*?
?????*?刪除結(jié)點(diǎn)(z)晒骇，并返回被刪除的結(jié)點(diǎn)?
?????*?
?????*?參數(shù)說明：?
?????*?????tree?紅黑樹的根結(jié)點(diǎn)?
?????*?????z?刪除的結(jié)點(diǎn)?
?????*/?
public?void?remove(E?key)?{?
????????RBTNode<E>?node;?
if?((node?=?search(root,key))?!=?null)?
????????????remove(node);?
????}?
????/*?
?????*?刪除結(jié)點(diǎn)(node)，并返回被刪除的結(jié)點(diǎn)?
?????*?
?????*?參數(shù)說明：?
?????*?????node?刪除的結(jié)點(diǎn)?
?????*/?
????private?void?remove(RBTNode<E>?node)?{?
????????RBTNode<E>?child,?parent;?
????????boolean?color;?
//?被刪除節(jié)點(diǎn)的"左右孩子都不為空"的情況磺浙。?
if?(?(node.left!=null)?&&?(node.right!=null)?)?{?
//?被刪節(jié)點(diǎn)的后繼節(jié)點(diǎn)洪囤。(稱為"取代節(jié)點(diǎn)")?
//?用它來取代"被刪節(jié)點(diǎn)"的位置，然后再將"被刪節(jié)點(diǎn)"去掉撕氧。?
RBTNodereplace?=?node;?
????????????//?獲取后繼節(jié)點(diǎn)?
replace?=?replace.right;?
while?(replace.left?!=?null)?
replace?=?replace.left;?
//"node節(jié)點(diǎn)"不是根節(jié)點(diǎn)(只有根節(jié)點(diǎn)不存在父節(jié)點(diǎn))?
if?(parentOf(node)!=null)?{?
if?(parentOf(node).left?==?node)?
parentOf(node).left?=?replace;?
else?
parentOf(node).right?=?replace;?
}else?{?
//"node節(jié)點(diǎn)"是根節(jié)點(diǎn)瘤缩，更新根節(jié)點(diǎn)。?
this.root?=replace;?
????????????}?
//?child是"取代節(jié)點(diǎn)"的右孩子伦泥，也是需要"調(diào)整的節(jié)點(diǎn)"剥啤。?
//"取代節(jié)點(diǎn)"肯定不存在左孩子！因?yàn)樗且粋€(gè)后繼節(jié)點(diǎn)不脯。?
child?=replace.right;?
parent?=?parentOf(replace);?
//?保存"取代節(jié)點(diǎn)"的顏色?
color?=?colorOf(replace);?
//"被刪除節(jié)點(diǎn)"是"它的后繼節(jié)點(diǎn)的父節(jié)點(diǎn)"?
????????????if?(parent?==?node)?{?
parent?=replace;?
}else?{?
????????????????//?child不為空?
if?(child!=null)?
????????????????????setParent(child,?parent);?
parent.left?=?child;?
replace.right?=?node.right;?
setParent(node.right,?replace);?
????????????}?
replace.parent?=?node.parent;?
replace.color?=?node.color;?
replace.left?=?node.left;?
node.left.parent?=?replace;?
????????????if?(color?==?BLACK)?
????????????????removeFixUp(child,?parent);?
node?=null;?
return?;?
????????}?
if?(node.left?!=null)?{?
child?=?node.left;?
}else?{?
child?=?node.right;?
????????}?
????????parent?=?node.parent;?
//?保存"取代節(jié)點(diǎn)"的顏色?
????????color?=?node.color;?
if?(child!=null)?
????????????child.parent?=?parent;?
//"node節(jié)點(diǎn)"不是根節(jié)點(diǎn)?
if?(parent!=null)?{?
if?(parent.left?==?node)?
parent.left?=?child;?
else?
parent.right?=?child;?
}else?{?
????????????this.root?=?child;?
????????}?
????????if?(color?==?BLACK)?
????????????removeFixUp(child,?parent);?
node?=null;?
????}?
????/*?
?????*?紅黑樹刪除修正函數(shù)?
?????*?
?????*?在從紅黑樹中刪除插入節(jié)點(diǎn)之后(紅黑樹失去平衡)铐殃，再調(diào)用該函數(shù)；?
?????*?目的是將它重新塑造成一顆紅黑樹跨新。?
?????*?
?????*?參數(shù)說明：?
?????*?????node?待修正的節(jié)點(diǎn)?
?????*/?
????private?void?removeFixUp(RBTNode<E>?node,?RBTNode<E>?parent)?{?
????????RBTNode<E>?other;?
while?((node==null?||?isBlack(node))?&&?(node?!=?this.root))?{?
if?(parent.left?==?node)?{?
other?=?parent.right;?
????????????????if?(isRed(other))?{?
//Case?1:?x的兄弟w是紅色的?
????????????????????setBlack(other);?
????????????????????setRed(parent);?
????????????????????leftRotate(parent);?
other?=?parent.right;?
????????????????}?
if?((other.left==null?||?isBlack(other.left))?&&?
(other.right==null?||?isBlack(other.right)))?{?
//Case?2:?x的兄弟w是黑色，且w的倆個(gè)孩子也都是黑色的?
????????????????????setRed(other);?
????????????????????node?=?parent;?
????????????????????parent?=?parentOf(node);?
}else?{?
if?(other.right==null?||?isBlack(other.right))?{?
//Case?4:?x的兄弟w是黑色的坏逢，并且w的左孩子是紅色域帐，右孩子為黑色。?
setBlack(other.left);?
????????????????????????setRed(other);?
????????????????????????rightRotate(other);?
other?=?parent.right;?
????????????????????}?
//Case?3:?x的兄弟w是黑色的是整；并且w的右孩子是紅色的肖揣，左孩子任意顏色。?
????????????????????setColor(other,?colorOf(parent));?
????????????????????setBlack(parent);?
setBlack(other.right);?
????????????????????leftRotate(parent);?
????????????????????node?=?this.root;?
????????????????????break;?
????????????????}?
}else?{?
other?=?parent.left;?
????????????????if?(isRed(other))?{?
//Case?1:?x的兄弟w是紅色的?
????????????????????setBlack(other);?
????????????????????setRed(parent);?
????????????????????rightRotate(parent);?
other?=?parent.left;?
????????????????}?
if?((other.left==null?||?isBlack(other.left))?&&?
(other.right==null?||?isBlack(other.right)))?{?
//Case?2:?x的兄弟w是黑色浮入，且w的倆個(gè)孩子也都是黑色的?
????????????????????setRed(other);?
????????????????????node?=?parent;?
????????????????????parent?=?parentOf(node);?
}else?{?
if?(other.left==null?||?isBlack(other.left))?{?
//Case?4:?x的兄弟w是黑色的龙优，并且w的左孩子是紅色，右孩子為黑色事秀。?
setBlack(other.right);?
????????????????????????setRed(other);?
????????????????????????leftRotate(other);?
other?=?parent.left;?
????????????????????}?
//Case?3:?x的兄弟w是黑色的彤断；并且w的右孩子是紅色的野舶，左孩子任意顏色。?
????????????????????setColor(other,?colorOf(parent));?
????????????????????setBlack(parent);?
setBlack(other.left);?
????????????????????rightRotate(parent);?
????????????????????node?=?this.root;?
????????????????????break;?
????????????????}?
????????????}?
????????}?
if?(node!=null)?
????????????setBlack(node);?
????}?
????/**?
?????*?查詢節(jié)點(diǎn)?
*?@paramkey?
*?@return?
?????*/?
public?RBTNode<E>?search(E?key)?{?
return?search(root,?key);?
????}?
????/*?
*?(遞歸實(shí)現(xiàn))查找"紅黑樹x"中鍵值為key的節(jié)點(diǎn)?
?????*/?
private?RBTNode?search(RBTNode?x,?Ekey)?{?
if?(x==null)?
return?x;?
int?cmp?=?key.compareTo(x.key);?
????????if?(cmp?<?0)?
return?search(x.left,?key);?
else?if?(cmp?>?0)?
return?search(x.right,?key);?
else?
return?x;?
????}?
????/**?
?????*?中序遍歷?
?????*?@param?node?
?????*/?
public?void?middleTreeIterator(RBTNode<E>?node){?
if(node?!=null){?
middleTreeIterator(node.left);//遍歷當(dāng)前節(jié)點(diǎn)左子樹?
System.out.println("key:"?+?node.key);?
middleTreeIterator(node.right);//遍歷當(dāng)前節(jié)點(diǎn)右子樹?
????????}?
????}?
????private?RBTNode<E>?parentOf(RBTNode<E>?node)?{?
return?node!=null???node.parent?:?null;?
????}?
????private?boolean?colorOf(RBTNode<E>?node)?{?
return?node!=null???node.color?:?BLACK;?
????}?
????private?boolean?isRed(RBTNode<E>?node)?{?
return?((node!=null)&&(node.color==RED))???true?:?false;?
????}?
????private?boolean?isBlack(RBTNode<E>?node)?{?
return?!isRed(node);?
????}?
????private?void?setBlack(RBTNode<E>?node)?{?
if?(node!=null)?
????????????node.color?=?BLACK;?
????}?
????private?void?setRed(RBTNode<E>?node)?{?
if?(node!=null)?
????????????node.color?=?RED;?
????}?
????private?void?setParent(RBTNode<E>?node,?RBTNode<E>?parent)?{?
if?(node!=null)?
????????????node.parent?=?parent;?
????}?
????private?void?setColor(RBTNode<E>?node,?boolean?color)?{?
if?(node!=null)?
????????????node.color?=?color;?
????}?
????/*?
?????*?對紅黑樹的節(jié)點(diǎn)(x)進(jìn)行左旋轉(zhuǎn)?
?????*?
?????*?左旋示意圖(對節(jié)點(diǎn)x進(jìn)行左旋)：?
?????*??????px??????????????????????????????px?
?????*?????/???????????????????????????????/?
?????*????x???????????????????????????????y?
*???/??\--(左旋)-.???????????/?\????????????????#?
?????*??lx???y??????????????????????????x??ry?
?????*?????/???\???????????????????????/??\?
?????*????ly???ry?????????????????????lx??ly?
?????*?
?????*?
?????*/?
????private?void?leftRotate(RBTNode<E>?x)?{?
????????//?設(shè)置x的右孩子為y?
RBTNode?y?=?x.right;?
????????//?將?“y的左孩子”?設(shè)為?“x的右孩子”宰衙；?
????????//?如果y的左孩子非空平道，將?“x”?設(shè)為?“y的左孩子的父親”?
x.right?=?y.left;?
if?(y.left?!=?null)?
y.left.parent?=?x;?
????????//?將?“x的父親”?設(shè)為?“y的父親”?
????????y.parent?=?x.parent;?
if?(x.parent?==null)?{?
????????????this.root?=?y;????????????//?如果?“x的父親”?是空節(jié)點(diǎn)，則將y設(shè)為根節(jié)點(diǎn)?
}else?{?
if?(x.parent.left?==?x)?
x.parent.left?=?y;????//?如果?x是它父節(jié)點(diǎn)的左孩子供炼，則將y設(shè)為“x的父節(jié)點(diǎn)的左孩子”?
else?
x.parent.right?=?y;????//?如果?x是它父節(jié)點(diǎn)的左孩子一屋，則將y設(shè)為“x的父節(jié)點(diǎn)的左孩子”?
????????}?
????????//?將?“x”?設(shè)為?“y的左孩子”?
y.left?=?x;?
????????//?將?“x的父節(jié)點(diǎn)”?設(shè)為?“y”?
????????x.parent?=?y;?
????}?
????/*?
?????*?對紅黑樹的節(jié)點(diǎn)(y)進(jìn)行右旋轉(zhuǎn)?
?????*?
?????*?右旋示意圖(對節(jié)點(diǎn)y進(jìn)行左旋)：?
?????*????????????py???????????????????????????????py?
?????*???????????/????????????????????????????????/?
?????*??????????y????????????????????????????????x?
*?????????/??\--(右旋)-.????????????/??\?????????????????????#?
?????*????????x???ry???????????????????????????lx???y?
?????*???????/?\???????????????????????????????????/?\???????????????????#?
?????*??????lx??rx????????????????????????????????rx??ry?
?????*?
?????*/?
????private?void?rightRotate(RBTNode<E>?y)?{?
????????//?設(shè)置x是當(dāng)前節(jié)點(diǎn)的左孩子。?
RBTNode?x?=?y.left;?
????????//?將?“x的右孩子”?設(shè)為?“y的左孩子”袋哼；?
//?如果"x的右孩子"不為空的話冀墨，將?“y”?設(shè)為?“x的右孩子的父親”?
y.left?=?x.right;?
if?(x.right?!=?null)?
x.right.parent?=?y;?
????????//?將?“y的父親”?設(shè)為?“x的父親”?
????????x.parent?=?y.parent;?
if?(y.parent?==null)?{?
????????????this.root?=?x;????????????//?如果?“y的父親”?是空節(jié)點(diǎn)，則將x設(shè)為根節(jié)點(diǎn)?
}else?{?
if?(y?==?y.parent.right)?
y.parent.right?=?x;????//?如果?y是它父節(jié)點(diǎn)的右孩子涛贯，則將x設(shè)為“y的父節(jié)點(diǎn)的右孩子”?
else?
y.parent.left?=?x;????//?(y是它父節(jié)點(diǎn)的左孩子)?將x設(shè)為“x的父節(jié)點(diǎn)的左孩子”?
????????}?
????????//?將?“y”?設(shè)為?“x的右孩子”?
x.right?=?y;?
????????//?將?“y的父節(jié)點(diǎn)”?設(shè)為?“x”?
????????y.parent?=?x;?
????}?
}?
測試代碼诽嘉，如下：
public?class?RBTClient?{?
public?static?void?main(String[]?args)?{?
RBTSolution
????????//插入節(jié)點(diǎn)?
System.out.println("========插入元素========");?
tree.insert(new?Integer(100));?
tree.insert(new?Integer(85));?
tree.insert(new?Integer(120));?
tree.insert(new?Integer(60));?
tree.insert(new?Integer(90));?
tree.insert(new?Integer(80));?
tree.insert(new?Integer(130));?
System.out.println("========中序遍歷元素========");?
????????//中序遍歷?
????????tree.middleTreeIterator(tree.root);?
System.out.println("========查找key為100的元素========");?
????????//查詢節(jié)點(diǎn)?
RBTNode
System.out.println("查找結(jié)果："?+?searchResult);?
System.out.println("========刪除key為90的元素========");?
????????//刪除節(jié)點(diǎn)?
????????tree.remove(90);?
System.out.println("========再次中序遍歷元素========");?
????????//中序遍歷?
????????tree.middleTreeIterator(tree.root);?
????}?
}?
輸出結(jié)果如下：
========插入元素========?
插入[100]:?
插入[85]:?
插入[120]:?
插入[60]:?
插入[90]:?
插入[80]:?
插入[130]:?
========中序遍歷元素========?
key:60?
key:80?
key:85?
key:90?
key:100?
key:120?
key:130?
========查找key為100的元素========?
查找結(jié)果：RBTNode{color=red,key=100}?
========刪除key為90的元素========?
========再次中序遍歷元素========?
key:60?
key:80?
key:85?
key:100?
key:120?
key:130?
四、總結(jié)
本篇文章疫蔓，前前后后寫了大概一個(gè)星期含懊，尤其是刪除邏輯，比較復(fù)雜衅胀，如果有理解不對的地方岔乔，歡迎網(wǎng)友們指出!
以下是紅黑樹總結(jié)：
1、紅黑樹是一個(gè)基本平衡的二叉樹滚躯，在查詢方面雏门，與二叉查找樹思路相同;在插入方面，單次回溯不會(huì)超過2次旋轉(zhuǎn);在刪除方面掸掏，單次回溯不會(huì)超過3次旋轉(zhuǎn)!
2茁影、相比于平衡二叉樹，紅黑樹在查詢丧凤、插入方面募闲，效率差不多;在刪除方面，平衡二叉樹最多需要log(n)次變化愿待，以達(dá)到嚴(yán)格平衡浩螺，而紅黑樹最多不會(huì)超過3次變化，因此效率要高于平衡二叉樹!
3仍侥、在實(shí)際應(yīng)用中要出，很多語言都實(shí)現(xiàn)了紅黑樹的數(shù)據(jù)結(jié)構(gòu)，比如 Java 中的 TreeMap农渊、 TreeSet患蹂，以及 jdk1.8 中的 HashMap!
以上內(nèi)容都是我自己的一些感想，分享出來歡迎大家指正，順便求一波關(guān)注传于，有問題的或者更好的想法的小伙伴可以評論私信我哦~或者點(diǎn)擊Java分享交流群一起聊天啊
作者：炸雞可樂
