【原】面經(jīng)手冊 · 第5篇《看圖說話，講解2-3平衡樹「紅黑樹的前身」》

小傅哥 2021-12-13

展開全文

在這里插入圖片描述

作者：小傅哥
博客：https://

沉淀、分享、成長，讓自己和他人都能有所收獲！😄

一、前言

講道理5年開發(fā)，沒用過數(shù)據(jù)結(jié)構(gòu)，你只是在做CRUD！

很多時候大部分程序員👨?💻?頭疼于，查詢慢、效率低、一堆的關(guān)聯(lián)SQL，主要原因是在程序設(shè)計上沒有做出很好的數(shù)據(jù)結(jié)構(gòu)。當然也還有一部分是由于老業(yè)務(wù)代碼，或者沒有用到一些大數(shù)據(jù)服務(wù)等。

數(shù)據(jù)結(jié)構(gòu)、算法、設(shè)計模式，是每一個程序員成長過程中的內(nèi)功心法修煉，而你的新技能用的再絢、多線程使的再6、加鎖玩的再牛🐂，也只能說明你這個人身體好，但身體好是不能抗住子彈的。只有身體+心法都好，都能縱橫捭闔。

這一章節(jié)是結(jié)合HashMap的延展，在Jdk1.8中HashMap是使用桶數(shù)組+鏈表和紅黑樹實現(xiàn)，所以順著上一章節(jié)的核心原理和API功能講解后，本來這一章節(jié)想直接進入到紅黑樹，但如果想把紅黑樹學明白，就需要了解他的來龍去脈，也就是它的前身2-3樹🌲。

二、面試題

謝飛機，考你幾個簡單的知識點🦀

飛機，看你簡歷寫了解數(shù)據(jù)結(jié)構(gòu)，可以簡單介紹下2-3樹嗎？
這種樹節(jié)點有什么特點，與你了解其他的樹結(jié)構(gòu)對比下？
你看這個圖，向里面插入和刪除節(jié)點，要怎么操作？

🤥飛機，回去等消息吧！

三、什么是2-3樹

日常的學習和一部分伙伴的面試中，竟然會聽👂到的是；從HashMap中文紅黑樹、從數(shù)據(jù)庫索引為B+Tree，但問2-3樹的情況就不是很多了。

1. 為什么使用樹結(jié)構(gòu)

從最根本的原因來看，使用樹結(jié)構(gòu)就是為了提升整體的效率；插入、刪除、查找(索引)，尤其是索引操作。因為相比于鏈表，一個平衡樹的索引時間復(fù)雜度是O(logn)，而數(shù)組的索引時間復(fù)雜度是O(n)。

從以下的圖上可以對比，兩者的索引耗時情況；

公眾號：bugstack蟲洞棧 & 鏈表與二叉搜索樹(Binary Search Tree)時間復(fù)雜度對比

從上圖可以看到，使用樹結(jié)構(gòu)有效的降低時間復(fù)雜度，提升數(shù)據(jù)索引效率。
另外這個標準的樹結(jié)構(gòu)，是二叉搜索樹(Binary Search Tree)。除此之外樹形結(jié)構(gòu)還有；AVL樹、紅黑樹、2-3樹等

2. 二叉搜索樹退化鏈表

在樹的數(shù)據(jù)結(jié)構(gòu)中，最先有點是二叉查找樹，也就是英文縮寫B(tài)ST樹。在使用數(shù)據(jù)插入的過程中，理想情況下它是一個平衡的二叉樹，但實際上可能會出現(xiàn)二叉樹都一邊倒，讓二叉樹像列表一樣的數(shù)據(jù)結(jié)構(gòu)。從而樹形結(jié)構(gòu)的時間復(fù)雜度也從O(logn)升級到O(n)，如下圖；

公眾號：bugstack蟲洞棧 & 二叉搜索樹退化鏈表

二叉搜索樹的數(shù)據(jù)插入過程是，插入節(jié)點與當前樹節(jié)點做比對，小于在左，大于在右。
隨著數(shù)據(jù)的插入順序不同，就會出現(xiàn)完全不同的數(shù)據(jù)結(jié)構(gòu)?？赡苁且豢闷胶舛鏄?#xff0c;也極有可能退化成鏈表的樹。
當樹結(jié)構(gòu)退化成鏈表以后，整個樹索引的性能也跟著退化成鏈表。

綜上呢，如果我們希望在插入數(shù)據(jù)后又保持樹的特點，O(logn)的索引性能，那么就需要在插入時進行節(jié)點的調(diào)整

3. 2-3樹解決平衡問題

2-3樹是什么結(jié)構(gòu)，它怎么解決平衡問題的。帶著問題我們繼續(xù)🤔。

2-3樹是一種非常巧妙的結(jié)構(gòu)，在保持樹結(jié)構(gòu)的基礎(chǔ)上，它允許在一個節(jié)點中可以有兩個元素，等元素數(shù)量等于3個時候再進行調(diào)整。通過這種方式呢，來保證整個二叉搜索樹的平衡性。

這樣說可能還沒有感覺，來看下圖；

公眾號：bugstack蟲洞棧 & 2-3樹解決平穩(wěn)問題

左側(cè)是二叉搜索樹，右側(cè)是2-3平衡樹，分別插入節(jié)點4、5，觀察樹形結(jié)構(gòu)變化。
二叉搜索樹開始出現(xiàn)偏移，節(jié)點一遍倒。
2-3樹通過一個節(jié)點中存放2到3個元素，來調(diào)整樹形結(jié)構(gòu)，保持平衡。所謂的保持平衡就是從根節(jié)點，到每一個最底部的自己點，鏈路長度一致。

2-3樹已經(jīng)可以解決平衡問題那么，數(shù)據(jù)是怎么存放和調(diào)整的呢，接下來我們開始分析。

四、2-3樹使用

1. 樹結(jié)構(gòu)定義和特點性質(zhì)

2-3樹，讀法；二三樹，特性如下；

序號	描述	示意圖
1	2-，1個數(shù)據(jù)節(jié)點2個樹杈
2	3-，2個數(shù)據(jù)節(jié)點3個樹杈
3	三叉與兩叉的不同點在于，除了兩邊的節(jié)點，中間件還有一個節(jié)點。這個節(jié)點是介于2、4之間的值。
4	當隨著插入數(shù)據(jù)，會出現(xiàn)臨時的一個節(jié)點中，有三個元素。這時會被調(diào)整成一個二叉樹。

綜上我們可以總結(jié)出，2-3樹的一些性質(zhì)；

2-3樹所有子葉節(jié)點都在同一層
1個節(jié)點可以有1到2個數(shù)據(jù)，如果有三個需要調(diào)整樹結(jié)構(gòu)
1個節(jié)點1個數(shù)據(jù)時，則有兩個子節(jié)點
1個節(jié)點2個數(shù)據(jù)時，則有三個子節(jié)點，且中間子節(jié)點是介于兩個節(jié)點間的值

2. 數(shù)據(jù)插入

接下來我們就模擬在二叉搜索樹中退化成鏈表的數(shù)據(jù)，插入到2-3樹的變化過程，數(shù)據(jù)包括；1、2、3、4、5、6、7，插入過程圖如下；

公眾號：bugstack蟲洞棧 & 數(shù)據(jù)插入過程圖

以上，就是整個數(shù)據(jù)在插入過程中，2-3樹的演化過程，接下來我們具體講解每一步的變化；

α，向節(jié)點1插入數(shù)據(jù)2，此時為了保持平衡，不會新產(chǎn)生分支，只會在一個節(jié)點中存放兩個節(jié)點。
β，繼續(xù)插入數(shù)據(jù)3，此時這個節(jié)點有三數(shù)據(jù)，1、2、3，是一個臨時區(qū)域。
γ，把三個數(shù)據(jù)的節(jié)點，中間節(jié)點拉起來，調(diào)整成樹形結(jié)構(gòu)。
δ，繼續(xù)插入數(shù)據(jù)4，為了保持樹平衡，會插在節(jié)點3的右側(cè)。
ε，繼續(xù)插入數(shù)據(jù)5，插入后3、4、5共用1個節(jié)點，當一個節(jié)點上有三個數(shù)據(jù)時候，則需要進行調(diào)整。
ζ，中間節(jié)點4向上?調(diào)整，調(diào)整后，1節(jié)點在左、3節(jié)點在中間、5節(jié)點在右。
η ，繼續(xù)插入數(shù)據(jù)6，在保持樹平衡的情況下，與節(jié)點5公用。
θ ，繼續(xù)插入數(shù)據(jù)7，插入后，節(jié)點7會與當前的節(jié)點 5 6 共用。此時是一個臨時存放，需要調(diào)整。初步調(diào)整后，抽出6節(jié)點，向上存放，變?yōu)?code>2 4 6共用一個節(jié)點，這是一個臨時狀態(tài)，還需要繼續(xù)調(diào)整。
ι，因為根節(jié)點有三個數(shù)據(jù)2、4、6，則繼續(xù)需要把中間節(jié)點上移，1、3和5、7 則分別成二叉落到節(jié)點2、節(jié)點6上。

🇬🇷希臘字母：α(阿爾法)、 β(貝塔)、γ(伽馬)、δ(德爾塔)、ε(伊普西隆)、ζ(截塔)、η(艾塔)、θ(西塔)、ι(約塔)

3. 數(shù)據(jù)刪除

有了上面數(shù)據(jù)插入的學習，在看數(shù)據(jù)刪除其實就是一個逆向的過程，在刪除的主要包括這樣兩種情況；

刪除了3-節(jié)點，也就是包含兩個數(shù)據(jù)元素的節(jié)點，直接刪除即可，不會破壞樹平衡。
刪除了2-節(jié)點，此時會破壞樹平衡，需要將樹高縮短或者元素合并，恢復(fù)樹平衡。

承接上面👆的例子，我們把數(shù)據(jù)再從7、6、5、4、3、2、1順序刪除，觀察2-3樹的結(jié)構(gòu)變化，如下；

公眾號：bugstack蟲洞棧 & 數(shù)據(jù)刪除過程圖

α，刪除節(jié)點7，因為節(jié)點7只有一個數(shù)據(jù)元素，刪除節(jié)點5、6合并，但此時破壞了2-3樹的平衡性，需要縮短樹高進行調(diào)整。
β，因為刪除節(jié)點后，整個樹結(jié)構(gòu)不平衡，所以需要縮短樹高，調(diào)整元素。節(jié)點2、4合并，節(jié)點1、3分別插入左側(cè)和中間。
γ，刪除節(jié)點6，這個節(jié)點是3-節(jié)點(可以分出3個叉的意思)，刪除后不會破壞樹平衡，保持不變。
δ，刪除節(jié)點5，此時會破壞樹平衡，需要把跟節(jié)點4下放，與3合并。
ε，刪除節(jié)點4，這個節(jié)點依舊是3-節(jié)點，所以不需要改變樹結(jié)構(gòu)。
ζ，刪除節(jié)點3，此時只有1、2節(jié)點，需要合并。
η ，刪除節(jié)點2，此時節(jié)點依舊是3-節(jié)點，所以不需要改變樹結(jié)構(gòu)。

再看一個稍微復(fù)雜點2-3樹刪除：

公眾號：bugstack蟲洞棧 & 復(fù)雜樹刪除過程

上面👆這張圖，就一個稍微復(fù)雜點的2-3平衡樹，樹的刪除過程主要包括；

刪除4，其實需要將節(jié)點3、5合并，指向節(jié)點2，保持樹平衡。
刪除7，節(jié)點8、9合并。
刪除14，節(jié)點15上移，恢復(fù)成3-叉樹。

🤔如果有時候不好理解刪除，可以試想下，這個要刪除的節(jié)點，在插入的時候是一個什么效果。

4. 數(shù)據(jù)索引

相比于插入和刪除，索引的過程還是比較簡單的，不需要調(diào)整數(shù)據(jù)結(jié)果。基本原則就是；

小于當前節(jié)點值，左側(cè)尋找
大于當前節(jié)點值，右側(cè)尋找
一直到找到索引值，停止。

🔍第一層尋找：

🔍第二層尋找：

🔍第三次尋找：

五、總結(jié)

綜上講解了2-3樹🌲的核心內(nèi)容，通過本章節(jié)的學習，可以了解2-3樹是一種怎樣的數(shù)據(jù)結(jié)構(gòu)、如何插入數(shù)據(jù)、刪除數(shù)據(jù)以及數(shù)據(jù)的索引，同時要知道這是一種平衡樹的結(jié)構(gòu)，包括2-叉和3-叉節(jié)點以及數(shù)結(jié)構(gòu)隨著數(shù)據(jù)的添加刪除調(diào)整。
2-3樹是紅黑樹的演變前身，通過這一章節(jié)的學習就很容易學習紅黑樹的相關(guān)知識，在紅黑樹中添加數(shù)據(jù)進行的渲染、旋轉(zhuǎn)等來保持樹平衡。紅黑樹接近平衡
數(shù)據(jù)結(jié)構(gòu)方面的知識學習起來，可能會比較🤯燒腦，因為需要思考出那種模型結(jié)構(gòu)和變化的過程，所以會感覺困難。但這個燒腦的過程也是對學習非常有幫助的，可以迅速建設(shè)知識凸起，當突破不理解到理解，可以有非常多的收獲。