面經手冊 · 第5篇《看圖說話，講解2-3平衡樹「紅黑樹的前身」》
作者：小傅哥
博客：//bugstack.cn
沉澱、分享、成長，讓自己和他人都能有所收穫！😄
一、前言
講道理5年開發，沒用過數據結構，你只是在做CRUD！
很多時候大部分程序員👨💻頭疼於，查詢慢、效率低、一堆的關聯SQL，主要原因是在程序設計上沒有做出很好的數據結構。當然也還有一部分是由於老業務代碼，或者沒有用到一些大數據服務等。
數據結構、算法、設計模式，是每一個程序員成長過程中的內功心法修鍊，而你的新技能用的再絢、多線程使的再6、加鎖玩的再牛🐂，也只能說明你這個人身體好，但身體好是不能抗住子彈的。只有身體+心法都好，都能縱橫捭闔。
這一章節是結合HashMap的延展，在Jdk1.8中HashMap是使用桶數組+鏈表和紅黑樹實現，所以順着上一章節的核心原理和API功能講解後，本來這一章節想直接進入到紅黑樹，但如果想把紅黑樹學明白，就需要了解他的來龍去脈，也就是它的前身2-3樹🌲。
二、面試題
謝飛機，考你幾個簡單的知識點🦀
- 飛機，看你簡歷寫了解數據結構，可以簡單介紹下2-3樹嗎？
- 這種樹節點有什麼特點，與你了解其他的樹結構對比下？
- 你看這個圖，向裏面插入和刪除節點，要怎麼操作？
🤥飛機，回去等消息吧！
三、什麼是2-3樹
日常的學習和一部分夥伴的面試中，竟然會聽👂到的是；從HashMap中文紅黑樹、從數據庫索引為B+Tree，但問2-3樹的情況就不是很多了。
1. 為什麼使用樹結構
從最根本的原因來看，使用樹結構就是為了提升整體的效率；插入、刪除、查找(索引)，尤其是索引操作。因為相比於鏈表，一個平衡樹的索引時間複雜度是O(logn)，而數組的索引時間複雜度是O(n)。
從以下的圖上可以對比，兩者的索引耗時情況；
- 從上圖可以看到，使用樹結構有效的降低時間複雜度，提升數據索引效率。
- 另外這個標準的樹結構，是二叉搜索樹(Binary Search Tree)。除此之外樹形結構還有；AVL樹、紅黑樹、2-3樹等
2. 二叉搜索樹退化鏈表
在樹的數據結構中，最先有點是二叉查找樹，也就是英文縮寫BST樹。在使用數據插入的過程中，理想情況下它是一個平衡的二叉樹，但實際上可能會出現二叉樹都一邊倒，讓二叉樹像列表一樣的數據結構。從而樹形結構的時間複雜度也從O(logn)升級到O(n)，如下圖；
- 二叉搜索樹的數據插入過程是，插入節點與當前樹節點做比對，小於在左，大於在右。
- 隨着數據的插入順序不同，就會出現完全不同的數據結構。可能是一棵平衡二叉樹，也極有可能退化成鏈表的樹。
- 當樹結構退化成鏈表以後，整個樹索引的性能也跟着退化成鏈表。
綜上呢，如果我們希望在插入數據後又保持樹的特點，O(logn)的索引性能，那麼就需要在插入時進行節點的調整
3. 2-3樹解決平衡問題
2-3樹是什麼結構，它怎麼解決平衡問題的。帶着問題我們繼續🤔。
2-3樹是一種非常巧妙的結構，在保持樹結構的基礎上，它允許在一個節點中可以有兩個元素，等元素數量等於3個時候再進行調整。通過這種方式呢，來保證整個二叉搜索樹的平衡性。
這樣說可能還沒有感覺，來看下圖；
- 左側是二叉搜索樹，右側是2-3平衡樹，分別插入節點4、5，觀察樹形結構變化。
- 二叉搜索樹開始出現偏移，節點一遍倒。
- 2-3樹通過一個節點中存放2到3個元素，來調整樹形結構，保持平衡。所謂的保持平衡就是從根節點，到每一個最底部的自己點，鏈路長度一致。
2-3樹已經可以解決平衡問題那麼，數據是怎麼存放和調整的呢，接下來我們開始分析。
四、2-3樹使用
1. 樹結構定義和特點性質
2-3樹，讀法；二三樹，特性如下；
| 序號 | 描述 | 示意圖 |
|---|---|---|
| 1 | 2-，1個數據節點2個樹杈 | |
| 2 | 3-，2個數據節點3個樹杈 | |
| 3 | 三叉與兩叉的不同點在於，除了兩邊的節點，中間件還有一個節點。這個節點是介於2、4之間的值。 | |
| 4 | 當隨着插入數據，會出現臨時的一個節點中，有三個元素。這時會被調整成一個二叉樹。 |
綜上我們可以總結出，2-3樹的一些性質；
- 2-3樹所有子葉節點都在同一層
- 1個節點可以有1到2個數據，如果有三個需要調整樹結構
- 1個節點1個數據時，則有兩個子節點
- 1個節點2個數據時，則有三個子節點，且中間子節點是介於兩個節點間的值
2. 數據插入
接下來我們就模擬在二叉搜索樹中退化成鏈表的數據，插入到2-3樹的變化過程，數據包括；1、2、3、4、5、6、7，插入過程圖如下；
以上，就是整個數據在插入過程中，2-3樹的演化過程，接下來我們具體講解每一步的變化；
- α，向節點1插入數據2，此時為了保持平衡，不會新產生分支，只會在一個節點中存放兩個節點。
- β，繼續插入數據3，此時這個節點有三數據，1、2、3，是一個臨時區域。
- γ，把三個數據的節點，中間節點拉起來，調整成樹形結構。
- δ，繼續插入數據4，為了保持樹平衡，會插在節點3的右側。
- ε，繼續插入數據5，插入後
3、4、5共用1個節點，當一個節點上有三個數據時候，則需要進行調整。 - ζ，中間節點4向上⏫調整，調整後，1節點在左、3節點在中間、5節點在右。
- η ，繼續插入數據6，在保持樹平衡的情況下，與節點5公用。
- θ ，繼續插入數據7，插入後，節點7會與當前的節點
5 6共用。此時是一個臨時存放，需要調整。初步調整後，抽出6節點，向上存放，變為2 4 6共用一個節點，這是一個臨時狀態，還需要繼續調整。 - ι，因為根節點有三個數據
2、4、6，則繼續需要把中間節點上移，1、3和5、7則分別成二叉落到節點2、節點6上。
🇬🇷希臘字母：α(阿爾法)、 β(貝塔)、γ(伽馬)、δ(德爾塔)、ε(伊普西隆)、ζ(截塔)、η(艾塔)、θ(西塔)、ι(約塔)
3. 數據刪除
有了上面數據插入的學習，在看數據刪除其實就是一個逆向的過程，在刪除的主要包括這樣兩種情況；
- 刪除了3-節點，也就是包含兩個數據元素的節點，直接刪除即可，不會破壞樹平衡。
- 刪除了2-節點，此時會破壞樹平衡，需要將樹高縮短或者元素合併，恢復樹平衡。
承接上面👆的例子，我們把數據再從7、6、5、4、3、2、1順序刪除，觀察2-3樹的結構變化，如下；
- α，刪除節點7，因為節點7隻有一個數據元素，刪除節點
5、6合併，但此時破壞了2-3樹的平衡性，需要縮短樹高進行調整。 - β，因為刪除節點後，整個樹結構不平衡，所以需要縮短樹高，調整元素。節點
2、4合併，節點1、3分別插入左側和中間。 - γ，刪除節點6，這個節點是3-節點(可以分出3個叉的意思)，刪除後不會破壞樹平衡，保持不變。
- δ，刪除節點5，此時會破壞樹平衡，需要把跟節點4下放，與3合併。
- ε，刪除節點4，這個節點依舊是3-節點，所以不需要改變樹結構。
- ζ，刪除節點3，此時只有1、2節點，需要合併。
- η ，刪除節點2，此時節點依舊是3-節點，所以不需要改變樹結構。
再看一個稍微複雜點2-3樹刪除：
上面👆這張圖，就一個稍微複雜點的2-3平衡樹，樹的刪除過程主要包括；
- 刪除4，其實需要將節點
3、5合併，指向節點2，保持樹平衡。 - 刪除7，節點
8、9合併。 - 刪除14，節點
15上移，恢復成3-叉樹。
🤔如果有時候不好理解刪除，可以試想下，這個要刪除的節點，在插入的時候是一個什麼效果。
4. 數據索引
相比於插入和刪除，索引的過程還是比較簡單的，不需要調整數據結果。基本原則就是；
- 小於當前節點值，左側尋找
- 大於當前節點值，右側尋找
- 一直到找到索引值，停止。
🔍第一層尋找：
🔍第二層尋找：
🔍第三次尋找：
五、總結
- 綜上講解了2-3樹🌲的核心內容，通過本章節的學習，可以了解2-3樹是一種怎樣的數據結構、如何插入數據、刪除數據以及數據的索引，同時要知道這是一種平衡樹的結構，包括2-叉和3-叉節點以及數結構隨着數據的添加刪除調整。
- 2-3樹是紅黑樹的演變前身，通過這一章節的學習就很容易學習紅黑樹的相關知識，在紅黑樹中添加數據進行的渲染、旋轉等來保持樹平衡。紅黑樹接近平衡
- 數據結構方面的知識學習起來，可能會比較🤯燒腦，因為需要思考出那種模型結構和變化的過程，所以會感覺困難。但這個燒腦的過程也是對學習非常有幫助的，可以迅速建設知識凸起，當突破不理解到理解，可以有非常多的收穫。
六、系列推薦
- 面試官都問我啥
- HashMap核心知識，擾動函數、負載因子、擴容鏈表拆分，深度學習
- HashMap數據插入、查找、刪除、遍歷，源碼分析
- 重學 Java 設計模式，內功心法修鍊，22個互聯網真實業務場景實戰
- DDD領域驅動設計實踐，領域層決策規則樹服務設計
