寫在前面
紅黑樹，對(duì)很多童鞋來(lái)說(shuō)，是既熟悉又陌生。學(xué)校中學(xué)過(guò)，只了解大概；工作中不怎么使用，但面試又是重點(diǎn)。每次需要查看紅黑樹內(nèi)容時(shí)都很難以更生動(dòng)形象的方式來(lái)理解其內(nèi)容。沒(méi)錯(cuò)，本文內(nèi)容就是要解決這個(gè)問(wèn)題，用簡(jiǎn)單的語(yǔ)言，搭配靜圖和動(dòng)圖(利用大腦圖形記憶方式)，讓你對(duì)紅黑樹有更深入的了解和更清晰的記憶，希望小伙伴們?cè)俅斡龅郊t黑樹的問(wèn)題不至于頭大，建議讀該文章姿勢(shì): 打開兩個(gè)頁(yè)面，一個(gè)頁(yè)面看圖片和內(nèi)容，一個(gè)頁(yè)面看公式，像玩魔方一樣，多玩幾次就明白了
通過(guò)工具 (公眾號(hào)回復(fù)「工具」—>那些可以提高效率的工具—>紅黑樹) 動(dòng)態(tài)感受紅黑樹的轉(zhuǎn)換過(guò)程
俺家司令買完?yáng)|西后，我倆經(jīng)常會(huì)發(fā)生這樣的一段對(duì)話:
司令:你猜我買的這個(gè)多少錢？
我: 1000
司令: 高了
我: 500
司令: 低了:
我: 750
...... 直到最后猜中
這樣說(shuō)大家應(yīng)該已經(jīng)猜到了是「二分查找法」，通過(guò)這個(gè)例子我想要引出的是 樹，來(lái)看圖片
程序中的樹其實(shí)是我們?nèi)粘？吹降臉涞牡褂?，或者發(fā)揮一下想象，倒影也可以是樹根
二叉查找樹
二叉查找樹，Binary Search Tree 「BST」，要想了解二叉查找樹，我們首先看下二叉查找樹有哪些特性呢？
- 某節(jié)點(diǎn)的左子樹節(jié)點(diǎn)值僅包含小于該節(jié)點(diǎn)值
- 某節(jié)點(diǎn)的右子樹節(jié)點(diǎn)值僅包含大于該節(jié)點(diǎn)值
- 左右子樹每個(gè)也必須是二叉查找樹
看個(gè)圖就輕松理解上面三句話的意思了:
上圖，結(jié)合二叉查找樹的三條約束來(lái)看，非常好，沒(méi)有什么問(wèn)題。再來(lái)看一個(gè)圖，依舊符合上面三條約束，感覺(jué)有問(wèn)題嗎？
- 這是一個(gè)走路一米六，一米八的樹
- 這是一個(gè)畸形的樹，大風(fēng)一掛很可能被折斷的樹
從程序的角度來(lái)說(shuō)這個(gè)樹不夠平衡，查找次數(shù)或時(shí)間復(fù)雜度 O(h)可能會(huì)隨著一條腿長(zhǎng)無(wú)限增長(zhǎng)
理科生在高中學(xué)習(xí)生物時(shí)學(xué)過(guò)一個(gè)關(guān)鍵字「去除頂端優(yōu)勢(shì)」，通過(guò)去除植物頂端優(yōu)勢(shì)，側(cè)芽會(huì)迅速生長(zhǎng)，慢慢變得強(qiáng)壯和平衡， 紅黑樹其實(shí)就是去除二叉查找樹頂端優(yōu)勢(shì)的解決方案，從而達(dá)到樹的平衡
紅黑樹
紅黑樹，Red-Black Tree 「RBT」是一個(gè)自平衡(不是絕對(duì)的平衡)的二叉查找樹(BST)，樹上的每個(gè)節(jié)點(diǎn)都遵循下面的規(guī)則:
- 每個(gè)節(jié)點(diǎn)都有紅色或黑色
- 樹的根始終是黑色的 (黑土地孕育黑樹根，??)
- 沒(méi)有兩個(gè)相鄰的紅色節(jié)點(diǎn)（紅色節(jié)點(diǎn)不能有紅色父節(jié)點(diǎn)或紅色子節(jié)點(diǎn)，并沒(méi)有說(shuō)不能出現(xiàn)連續(xù)的黑色節(jié)點(diǎn)）
- 從節(jié)點(diǎn)（包括根）到其任何后代NULL節(jié)點(diǎn)(葉子結(jié)點(diǎn)下方掛的兩個(gè)空節(jié)點(diǎn)，并且認(rèn)為他們是黑色的)的每條路徑都具有相同數(shù)量的黑色節(jié)點(diǎn)
瞬間懵逼？了解一下印象就行，開始玩魔方都是要照著魔方公式一點(diǎn)點(diǎn)玩的，多玩幾次就熟悉了。紅黑樹也一樣，紅黑樹有兩大操作:
- recolor (重新標(biāo)記黑色或紅色)
- rotation (旋轉(zhuǎn)，這是樹達(dá)到平衡的關(guān)鍵)
我們會(huì)先嘗試 recolor，如果 recolor 不能達(dá)到紅黑樹的 4 點(diǎn)要求，然后我們嘗試 rotation，其實(shí)紅黑樹的關(guān)鍵玩法就是弄清楚 recolor 和 rotation 的規(guī)則，接下來(lái)看看詳細(xì)的算法公式吧 千萬(wàn)別著急記憶公式，有圖示會(huì)逐步說(shuō)明，就像魔方一樣，多玩幾次就懂了:
假設(shè)我們插入的新節(jié)點(diǎn)為 X
- 將新插入的節(jié)點(diǎn)標(biāo)記為紅色
- 如果 X 是根結(jié)點(diǎn)(root)，則標(biāo)記為黑色
-
- 如果 X 的 parent 不是黑色，同時(shí) X 也不是 root:
- 3.1 如果 X 的 uncle (叔叔) 是紅色
- 3.1.1 將 parent 和 uncle 標(biāo)記為黑色
- 3.1.2 將 grand parent (祖父) 標(biāo)記為紅色
- 3.1.3 讓 X 節(jié)點(diǎn)的顏色與 X 祖父的顏色相同，然后重復(fù)步驟 2、3
話不多說(shuō)，看下圖
跟著上面的公式走:
- 將新插入的 X 節(jié)點(diǎn)標(biāo)記為紅色
- 發(fā)現(xiàn) X 的 parent (P) 同樣為紅色，這違反了紅黑樹的第三條規(guī)則「不能有兩個(gè)連續(xù)相鄰的紅色節(jié)點(diǎn)」
- 發(fā)現(xiàn) X 的 uncle (U) 同樣為紅色
- 將 P 和 U 標(biāo)記為黑色
- 將 X 和 X 的 grand parent (G) 標(biāo)記為相同的顏色，即紅色，繼續(xù)重復(fù)公式 2、3
- 發(fā)現(xiàn) G 是根結(jié)點(diǎn)，標(biāo)記為黑色
- 結(jié)束
剛剛說(shuō)了 X 的 uncle 是紅色的情況，接下來(lái)要說(shuō)是黑色的情況
-
- 如果 X 的 parent 不是黑色，同時(shí) X 也不是 root:
- 3.2 如果 X 的 uncle (叔叔) 是黑色，我們要分四種情況處理
- 3.2.1 左左 (P 是 G 的左孩子，并且 X 是 P 的左孩子)
- 3.2.2 左右 (P 是 G 的左孩子，并且 X 是 P 的右孩子)
- 3.2.3 右右 (和 3.2.1 鏡像過(guò)來(lái)，恰好相反)
- 3.2.4 右左 (和 3.2.2 鏡像過(guò)來(lái)，恰好相反)
當(dāng)出現(xiàn) uncle 是黑色的時(shí)候我們第一步要考慮的是 旋轉(zhuǎn) ，這里先請(qǐng)小伙伴不要關(guān)注紅黑樹的第 4 條規(guī)則，主要是為了演示如何旋轉(zhuǎn)的，來(lái)一點(diǎn)點(diǎn)看，不要看圖就慌，有解釋的??:
左左情況
這種情況很簡(jiǎn)單，想象這是一根繩子，手提起 P 節(jié)點(diǎn)，然后變色即可
左右
左旋: 使 X 的父節(jié)點(diǎn) P 被 X 取代，同時(shí)父節(jié)點(diǎn) P 成為 X 的左孩子，然后再應(yīng)用 左左情況
右右
與左左情況一樣，想象成一根繩子
右左
右旋: 使 X 的父節(jié)點(diǎn) P 被 X 取代，同時(shí)父節(jié)點(diǎn) P 成為 X 的右孩子，然后再應(yīng)用 右右情況
你說(shuō)的動(dòng)圖在哪里，你個(gè)大騙子，別著急，現(xiàn)在就為小伙伴們奉上動(dòng)圖演示，來(lái)說(shuō)明公式的使用:
案例一
插入 10，20，30，15 到一個(gè)空樹中
向空樹中第一次插入數(shù)字 10，肯定是 root 節(jié)點(diǎn)
-
root 節(jié)點(diǎn)標(biāo)記成黑色
image 向樹中插入新節(jié)點(diǎn) 20，標(biāo)記為紅色
-
20 > 10，并發(fā)現(xiàn) 10 沒(méi)有葉子節(jié)點(diǎn)，將新節(jié)點(diǎn) 20 作為 10 的右孩子
image 向樹中插入新節(jié)點(diǎn) 30，標(biāo)記為紅色
30 > 10，查找 10 的右子樹，找到 20
30 > 20，繼續(xù)查找 20 的右子樹，發(fā)現(xiàn) 20 沒(méi)有葉子節(jié)點(diǎn)，將值插在此處
30 和 20 節(jié)點(diǎn)都為紅色，30 為右孩子，20 也為右孩子，觸發(fā)了 右右情況
通過(guò)一次旋轉(zhuǎn)，提起 20 節(jié)點(diǎn)
-
20 節(jié)點(diǎn)是根結(jié)點(diǎn)，標(biāo)記為黑色
image 向樹中插入新節(jié)點(diǎn) 15，標(biāo)記為紅色
通過(guò)比對(duì)大小和判斷是否有葉子節(jié)點(diǎn)，最終插值為 10 節(jié)點(diǎn)的右孩子
15 和 10 節(jié)點(diǎn)都為紅色，15 的 uncle 節(jié)點(diǎn) 30 也為紅色
按照公式，將 15 的 parent 10 和 uncle 30 更改為黑色
讓 15 節(jié)點(diǎn) grand parent 20 的顏色與 15 節(jié)點(diǎn)的顏色一樣，變?yōu)榧t色
-
20 為根結(jié)點(diǎn)，將其改為黑色
image
繼續(xù)插入其他節(jié)點(diǎn)只不過(guò)反復(fù)應(yīng)用上面的公式，上面應(yīng)用到的紅黑樹工具，可以暫停動(dòng)畫效果，一幀一幀的看紅黑樹的轉(zhuǎn)換過(guò)程，這樣通過(guò)練習(xí)，查看公式，觀察變化三管齊下，紅黑樹的入門理解應(yīng)該完全不再是問(wèn)題了
靈魂追問(wèn)
- jdk 1.8 HashMap 中有使用到紅黑樹，你知道觸發(fā)條件是什么嗎？有讀過(guò)源碼是如何 put 和 remove 的嗎？
- 這里講的是紅黑樹的 insert，delete 又是什么規(guī)則呢？
- 哪些場(chǎng)景可以應(yīng)用紅黑樹？
- 你了解各種樹的時(shí)間復(fù)雜度嗎？
- 留個(gè)小作業(yè)，應(yīng)用工具將 [10 70 32 34 13 56 32 56 21 3 62 4 ] 逐個(gè)插入到樹中，理解紅黑樹 recolor 和 rotation 的轉(zhuǎn)換規(guī)則
提高效率工具
[center]
推薦閱讀
- 只會(huì)用 git pull ？有時(shí)候你可以嘗試更優(yōu)雅的處理方式
- 雙親委派模型：大廠高頻面試題，輕松搞定
- 面試還不知道BeanFactory和ApplicationContext的區(qū)別？
- 如何設(shè)計(jì)好的RESTful API
- 程序猿為什么要看源碼？
歡迎持續(xù)關(guān)注公眾號(hào)：「日拱一兵」
- 前沿 Java 技術(shù)干貨分享
- 高效工具匯總
- 面試問(wèn)題分析與解答
- 技術(shù)資料領(lǐng)取
后續(xù)文章會(huì)為你講解各種時(shí)間空間復(fù)雜度，以及多線程，ElasticSearch 等問(wèn)題
以讀偵探小說(shuō)思維輕松趣味學(xué)習(xí) Java 技術(shù)棧相關(guān)知識(shí)，本著將復(fù)雜問(wèn)題簡(jiǎn)單化，抽象問(wèn)題具體化和圖形化原則逐步分解技術(shù)問(wèn)題，技術(shù)持續(xù)更新，請(qǐng)持續(xù)關(guān)注......
