寫在前面
紅黑樹，對很多童鞋來說，是既熟悉又陌生。學校中學過，隻了解大概；工作中不怎麼使用，但面試又是重點。每次需要檢視紅黑樹内容時都很難以更生動形象的方式來了解其内容。沒錯，本文内容就是要解決這個問題，用簡單的語言，搭配靜圖和動圖(利用大腦圖形記憶方式)，讓你對紅黑樹有更深入的了解和更清晰的記憶，希望小夥伴們再次遇到紅黑樹的問題不至于頭大，建議讀該文章姿勢: 打開兩個頁面，一個頁面看圖檔和内容，一個頁面看公式，像玩魔方一樣，多玩幾次就明白了
通過工具 動态感受紅黑樹的轉換過程
俺家司令買完東西後，我倆經常會發生這樣的一段對話:
司令:你猜我買的這個多少錢？我: 1000司令: 高了我: 500司令: 低了:我: 750...... 直到最後猜中
這樣說大家應該已經猜到了是「二分查找法」，通過這個例子我想要引出的是 樹，來看圖檔
程式中的樹其實是我們日常看到的樹的倒影，或者發揮一下想象，倒影也可以是樹根
二叉查找樹
二叉查找樹，Binary Search Tree 「BST」，要想了解二叉查找樹，我們首先看下二叉查找樹有哪些特性呢？
- 某節點的左子樹節點值僅包含小于該節點值
- 某節點的右子樹節點值僅包含大于該節點值
- 左右子樹每個也必須是二叉查找樹
看個圖就輕松了解上面三句話的意思了:
上圖，結合二叉查找樹的三條限制來看，非常好，沒有什麼問題。再來看一個圖，依舊符合上面三條限制，感覺有問題嗎？
- 這是一個走路一米六，一米八的樹
- 這是一個畸形的樹，大風一挂很可能被折斷的樹
從程式的角度來說這個樹不夠平衡，查找次數或時間複雜度 O(h)可能會随着一條腿長無限增長
理科生在高中學習生物時學過一個關鍵字「去除頂端優勢」，通過去除植物頂端優勢，側芽會迅速生長，慢慢變得強壯和平衡， 紅黑樹其實就是去除二叉查找樹頂端優勢的解決方案，進而達到樹的平衡
紅黑樹
紅黑樹，Red-Black Tree 「RBT」是一個自平衡(不是絕對的平衡)的二叉查找樹(BST)，樹上的每個節點都遵循下面的規則:
- 每個節點都有紅色或黑色
- 樹的根始終是黑色的 (黑土地孕育黑樹根，????)
- 沒有兩個相鄰的紅色節點（紅色節點不能有紅色父節點或紅色子節點，并沒有說不能出現連續的黑色節點）
- 從節點（包括根）到其任何後代NULL節點(葉子結點下方挂的兩個空節點，并且認為他們是黑色的)的每條路徑都具有相同數量的黑色節點
瞬間懵逼？了解一下印象就行，開始玩魔方都是要照着魔方公式一點點玩的，多玩幾次就熟悉了。紅黑樹也一樣，紅黑樹有兩大操作:
- recolor (重新标記黑色或紅色)
- rotation (旋轉，這是樹達到平衡的關鍵)
我們會先嘗試 recolor，如果 recolor 不能達到紅黑樹的 4 點要求，然後我們嘗試 rotation，其實紅黑樹的關鍵玩法就是弄清楚 recolor 和 rotation 的規則，接下來看看詳細的算法公式吧 千萬别着急記憶公式，有圖示會逐漸說明，就像魔方一樣，多玩幾次就懂了:假設我們插入的新節點為 X
- 1. 将新插入的節點标記為紅色
- 2. 如果 X 是根結點(root)，則标記為黑色
- 3. 如果 X 的 parent 不是黑色，同時 X 也不是 root:
-
- 3.1.1 将 parent 和 uncle 标記為黑色
- 3.1.2 将 grand parent (祖父) 标記為紅色
- 3.1.3 讓 X 節點的顔色與 X 祖父的顔色相同，然後重複步驟 2、3
- 3.1 如果 X 的 uncle (叔叔) 是紅色
話不多說，看下圖
跟着上面的公式走:
- 将新插入的 X 節點标記為紅色
- 發現 X 的 parent (P) 同樣為紅色，這違反了紅黑樹的第三條規則「不能有兩個連續相鄰的紅色節點」
- 發現 X 的 uncle (U) 同樣為紅色
- 将 P 和 U 标記為黑色
- 将 X 和 X 的 grand parent (G) 标記為相同的顔色，即紅色，繼續重複公式 2、3
- 發現 G 是根結點，标記為黑色
- 結束
剛剛說了 X 的 uncle 是紅色的情況，接下來要說是黑色的情況
- 3. 如果 X 的 parent 不是黑色，同時 X 也不是 root:
-
- 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 鏡像過來，恰好相反)
- 3.2 如果 X 的 uncle (叔叔) 是黑色，我們要分四種情況處理
當出現 uncle 是黑色的時候我們第一步要考慮的是 旋轉 ，這裡先請小夥伴不要關注紅黑樹的第 4 條規則，主要是為了示範如何旋轉的，來一點點看，不要看圖就慌，有解釋的????:
左左情況
這種情況很簡單，想象這是一根繩子，手提起 P 節點，然後變色即可
左右
左旋: 使 X 的父節點 P 被 X 取代，同時父節點 P 成為 X 的左孩子，然後再應用 左左情況
右右
與左左情況一樣，想象成一根繩子
右左
右旋: 使 X 的父節點 P 被 X 取代，同時父節點 P 成為 X 的右孩子，然後再應用 右右情況
你說的動圖在哪裡，你個大騙子，别着急，現在就為小夥伴們奉上動圖示範，來說明公式的使用:
案例一
插入 10，20，30，15 到一個空樹中
- 向空樹中第一次插入數字 10，肯定是 root 節點
- root 節點标記成黑色
- 向樹中插入新節點 20，标記為紅色
- 20 > 10，并發現 10 沒有葉子節點，将新節點 20 作為 10 的右孩子
- 向樹中插入新節點 30，标記為紅色
- 30 > 10，查找 10 的右子樹，找到 20
- 30 > 20，繼續查找 20 的右子樹，發現 20 沒有葉子節點，将值插在此處
- 30 和 20 節點都為紅色，30 為右孩子，20 也為右孩子，觸發了 右右情況
- 通過一次旋轉，提起 20 節點
- 20 節點是根結點，标記為黑色
- 向樹中插入新節點 15，标記為紅色
- 通過比對大小和判斷是否有葉子節點，最終插值為 10 節點的右孩子
- 15 和 10 節點都為紅色，15 的 uncle 節點 30 也為紅色
- 按照公式，将 15 的 parent 10 和 uncle 30 更改為黑色
- 讓 15 節點 grand parent 20 的顔色與 15 節點的顔色一樣，變為紅色
- 20 為根結點，将其改為黑色
繼續插入其他節點隻不過反複應用上面的公式，上面應用到的紅黑樹工具，可以暫停動畫效果，一幀一幀的看紅黑樹的轉換過程，這樣通過練習，檢視公式，觀察變化三管齊下，紅黑樹的入門了解應該完全不再是問題了
靈魂追問
- jdk 1.8 HashMap 中有使用到紅黑樹，你知道觸發條件是什麼嗎？有讀過源碼是如何 put 和 remove 的嗎？
- 這裡講的是紅黑樹的 insert，delete 又是什麼規則呢？
- 哪些場景可以應用紅黑樹？
- 你了解各種樹的時間複雜度嗎？
- 留個小作業，應用工具将 [10 70 32 34 13 56 32 56 21 3 62 4 ] 逐個插入到樹中，了解紅黑樹 recolor 和 rotation 的轉換規則
推薦閱讀：
- IntelliJ IDEA的這個接口調試工具真是太太太太太好用了！
- 隻有程式員才能看懂的笑話，情人節快樂！
- 淺談疫情下的就業形勢
- 新來個技術總監，禁止我們使用Lombok！
喜歡我可以給我設為星标哦
好文章，我 在看