寫在前面

紅黑樹报强，對很多童鞋來說秉溉，是既熟悉又陌生哮缺。學校中學過铛只，只了解大概凯肋；工作中不怎么使用侮东，但面試又是重點宽闲。每次需要查看紅黑樹內(nèi)容時都很難以更生動形象的方式來理解其內(nèi)容容诬。沒錯览徒，本文內(nèi)容就是要解決這個問題芦缰，用簡單的語言，搭配靜圖和動圖(利用大腦圖形記憶方式)涕俗，讓你對紅黑樹有更深入的了解和更清晰的記憶，希望小伙伴們再次遇到紅黑樹的問題不至于頭大讨永，建議讀該文章姿勢: 打開兩個頁面，一個頁面看圖片和內(nèi)容旋恼，一個頁面看公式蜀细，像玩魔方一樣奕谭，多玩幾次就明白了

通過工具 (公眾號回復「工具」—>那些可以提高效率的工具—>紅黑樹) 動態(tài)感受紅黑樹的轉(zhuǎn)換過程

image

俺家司令買完東西后，我倆經(jīng)常會發(fā)生這樣的一段對話:

司令:你猜我買的這個多少錢？
我: 1000
司令: 高了
我: 500
司令: 低了:
我: 750
...... 直到最后猜中

這樣說大家應(yīng)該已經(jīng)猜到了是「二分查找法」，通過這個例子我想要引出的是 樹衡瓶，來看圖片

image

程序中的樹其實是我們?nèi)粘寿烟？吹降臉涞牡褂埃蛘甙l(fā)揮一下想象和屎，倒影也可以是樹根

二叉查找樹

二叉查找樹随常，Binary Search Tree 「BST」燃乍，要想了解二叉查找樹片效，我們首先看下二叉查找樹有哪些特性呢？

1. 某節(jié)點的左子樹節(jié)點值僅包含小于該節(jié)點值
2. 某節(jié)點的右子樹節(jié)點值僅包含大于該節(jié)點值
3. 左右子樹每個也必須是二叉查找樹
   看個圖就輕松理解上面三句話的意思了:

image

上圖英古，結(jié)合二叉查找樹的三條約束來看淀衣，非常好，沒有什么問題召调。再來看一個圖膨桥，依舊符合上面三條約束，感覺有問題嗎唠叛？

image

1. 這是一個走路一米六只嚣，一米八的樹
2. 這是一個畸形的樹，大風一掛很可能被折斷的樹
   從程序的角度來說這個樹不夠平衡艺沼，查找次數(shù)或時間復雜度 O(h)可能會隨著一條腿長無限增長

理科生在高中學習生物時學過一個關(guān)鍵字「去除頂端優(yōu)勢」册舞，通過去除植物頂端優(yōu)勢，側(cè)芽會迅速生長障般，慢慢變得強壯和平衡调鲸， 紅黑樹其實就是去除二叉查找樹頂端優(yōu)勢的解決方案盛杰，從而達到樹的平衡

紅黑樹

紅黑樹，Red-Black Tree 「RBT」是一個自平衡(不是絕對的平衡)的二叉查找樹(BST)藐石，樹上的每個節(jié)點都遵循下面的規(guī)則:

1. 每個節(jié)點都有紅色或黑色
2. 樹的根始終是黑色的 (黑土地孕育黑樹根饶唤，??)
3. 沒有兩個相鄰的紅色節(jié)點（紅色節(jié)點不能有紅色父節(jié)點或紅色子節(jié)點，并沒有說不能出現(xiàn)連續(xù)的黑色節(jié)點）
4. 從節(jié)點（包括根）到其任何后代NULL節(jié)點(葉子結(jié)點下方掛的兩個空節(jié)點贯钩，并且認為他們是黑色的)的每條路徑都具有相同數(shù)量的黑色節(jié)點

瞬間懵逼募狂？了解一下印象就行，開始玩魔方都是要照著魔方公式一點點玩的角雷，多玩幾次就熟悉了祸穷。紅黑樹也一樣，紅黑樹有兩大操作:

1. recolor (重新標記黑色或紅色)
2. rotation (旋轉(zhuǎn)勺三，這是樹達到平衡的關(guān)鍵)
   我們會先嘗試 recolor雷滚，如果 recolor 不能達到紅黑樹的 4 點要求，然后我們嘗試 rotation吗坚，其實紅黑樹的關(guān)鍵玩法就是弄清楚 recolor 和 rotation 的規(guī)則祈远，接下來看看詳細的算法公式吧 千萬別著急記憶公式，有圖示會逐步說明商源，就像魔方一樣车份，多玩幾次就懂了:
   假設(shè)我們插入的新節(jié)點為 X

• 1. 將新插入的節(jié)點標記為紅色
• 2. 如果 X 是根結(jié)點(root)，則標記為黑色
• 3. 如果 X 的 parent 不是黑色牡彻，同時 X 也不是 root:
  • 3.1 如果 X 的 uncle (叔叔) 是紅色
    • 3.1.1 將 parent 和 uncle 標記為黑色
    • 3.1.2 將 grand parent (祖父) 標記為紅色
    • 3.1.3 讓 X 節(jié)點的顏色與 X 祖父的顏色相同扫沼，然后重復步驟 2、3

話不多說庄吼，看下圖

image

跟著上面的公式走:

1. 將新插入的 X 節(jié)點標記為紅色
2. 發(fā)現(xiàn) X 的 parent (P) 同樣為紅色缎除，這違反了紅黑樹的第三條規(guī)則「不能有兩個連續(xù)相鄰的紅色節(jié)點」
3. 發(fā)現(xiàn) X 的 uncle (U) 同樣為紅色
4. 將 P 和 U 標記為黑色
5. 將 X 和 X 的 grand parent (G) 標記為相同的顏色，即紅色总寻，繼續(xù)重復公式 2器罐、3
6. 發(fā)現(xiàn) G 是根結(jié)點，標記為黑色
7. 結(jié)束

剛剛說了 X 的 uncle 是紅色的情況渐行，接下來要說是黑色的情況

• 3. 如果 X 的 parent 不是黑色轰坊，同時 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 鏡像過來，恰好相反)
    • 3.2.4 右左 (和 3.2.2 鏡像過來旁理，恰好相反)
      當出現(xiàn) uncle 是黑色的時候我們第一步要考慮的是 旋轉(zhuǎn) 樊零，這里先請小伙伴不要關(guān)注紅黑樹的第 4 條規(guī)則，主要是為了演示如何旋轉(zhuǎn)的，來一點點看驻襟，不要看圖就慌夺艰，有解釋的??:

左左情況

這種情況很簡單，想象這是一根繩子沉衣，手提起 P 節(jié)點郁副，然后變色即可

image

左右

左旋: 使 X 的父節(jié)點 P 被 X 取代，同時父節(jié)點 P 成為 X 的左孩子豌习，然后再應(yīng)用 左左情況

image

右右

與左左情況一樣存谎，想象成一根繩子

image

右左

右旋: 使 X 的父節(jié)點 P 被 X 取代，同時父節(jié)點 P 成為 X 的右孩子肥隆，然后再應(yīng)用 右右情況

image

你說的動圖在哪里既荚，你個大騙子，別著急栋艳，現(xiàn)在就為小伙伴們奉上動圖演示恰聘，來說明公式的使用:

案例一

插入 10，20吸占，30晴叨，15 到一個空樹中

1. 向空樹中第一次插入數(shù)字 10，肯定是 root 節(jié)點

2. root 節(jié)點標記成黑色

   
   
   image

3. 向樹中插入新節(jié)點 20矾屯，標記為紅色

4. 20 > 10兼蕊，并發(fā)現(xiàn) 10 沒有葉子節(jié)點，將新節(jié)點 20 作為 10 的右孩子

   
   
   image

5. 向樹中插入新節(jié)點 30问拘，標記為紅色

6. 30 > 10遍略，查找 10 的右子樹惧所，找到 20

7. 30 > 20骤坐，繼續(xù)查找 20 的右子樹，發(fā)現(xiàn) 20 沒有葉子節(jié)點下愈，將值插在此處

8. 30 和 20 節(jié)點都為紅色纽绍，30 為右孩子，20 也為右孩子势似，觸發(fā)了 右右情況

9. 通過一次旋轉(zhuǎn)拌夏，提起 20 節(jié)點

10. 20 節(jié)點是根結(jié)點，標記為黑色

    
    
    image

11. 向樹中插入新節(jié)點 15履因，標記為紅色

12. 通過比對大小和判斷是否有葉子節(jié)點障簿，最終插值為 10 節(jié)點的右孩子

13. 15 和 10 節(jié)點都為紅色，15 的 uncle 節(jié)點 30 也為紅色

14. 按照公式栅迄，將 15 的 parent 10 和 uncle 30 更改為黑色

15. 讓 15 節(jié)點 grand parent 20 的顏色與 15 節(jié)點的顏色一樣站故，變?yōu)榧t色

16. 20 為根結(jié)點，將其改為黑色

    
    
    image

繼續(xù)插入其他節(jié)點只不過反復應(yīng)用上面的公式，上面應(yīng)用到的紅黑樹工具西篓，可以暫停動畫效果愈腾，一幀一幀的看紅黑樹的轉(zhuǎn)換過程，這樣通過練習岂津，查看公式虱黄，觀察變化三管齊下，紅黑樹的入門理解應(yīng)該完全不再是問題了

靈魂追問

1. jdk 1.8 HashMap 中有使用到紅黑樹吮成，你知道觸發(fā)條件是什么嗎橱乱？有讀過源碼是如何 put 和 remove 的嗎？
2. 這里講的是紅黑樹的 insert粱甫，delete 又是什么規(guī)則呢仅醇？
3. 哪些場景可以應(yīng)用紅黑樹？
4. 你了解各種樹的時間復雜度嗎魔种？
5. 留個小作業(yè)析二，應(yīng)用工具將 [10 70 32 34 13 56 32 56 21 3 62 4 ] 逐個插入到樹中，理解紅黑樹 recolor 和 rotation 的轉(zhuǎn)換規(guī)則

提高效率工具

image

[center]

推薦閱讀

• 只會用 git pull 节预？有時候你可以嘗試更優(yōu)雅的處理方式
• 雙親委派模型：大廠高頻面試題叶摄，輕松搞定
• 面試還不知道BeanFactory和ApplicationContext的區(qū)別？
• 如何設(shè)計好的RESTful API
• 程序猿為什么要看源碼安拟？

歡迎持續(xù)關(guān)注公眾號：「日拱一兵」

• 前沿 Java 技術(shù)干貨分享
• 高效工具匯總
• 面試問題分析與解答
• 技術(shù)資料領(lǐng)取

后續(xù)文章會為你講解各種時間空間復雜度蛤吓，以及多線程，ElasticSearch 等問題

以讀偵探小說思維輕松趣味學習 Java 技術(shù)棧相關(guān)知識糠赦，本著將復雜問題簡單化会傲，抽象問題具體化和圖形化原則逐步分解技術(shù)問題，技術(shù)持續(xù)更新拙泽，請持續(xù)關(guān)注......

image