此動(dòng)畫(huà)內(nèi)容為本文目錄，時(shí)常一分鐘，覺(jué)得太花時(shí)間可以跳過(guò)。本來(lái)一個(gè)思維導(dǎo)圖可以搞定。但這一次嘗試下這種方式，先放松放松。

一、 二叉樹(shù)

二叉樹(shù)是每個(gè)節(jié)點(diǎn)最多有兩個(gè)子樹(shù)的樹(shù)結(jié)構(gòu)。它有五種基本形態(tài)：二叉樹(shù)可以是空集；根可以有空的左子樹(shù)或右子樹(shù)；或者左、右子樹(shù)皆為空。如下圖所示

1 二叉樹(shù)的五種性質(zhì)

掌握二叉樹(shù)的五種性質(zhì)，能讓我們?cè)?span style="color: rgb(255, 104, 39);">筆試中做題變得游刃有余，也就有更多的時(shí)間處理其他的題目。其具體的性質(zhì)看下圖。

2 兩個(gè)特別的二叉樹(shù)

完全二叉樹(shù):對(duì)于深度為K的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每一個(gè)結(jié)點(diǎn)都與深度為K的滿二叉樹(shù)中編號(hào)從1至n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)稱之為完全二叉樹(shù)。

滿二叉樹(shù):除了葉結(jié)點(diǎn)外每一個(gè)結(jié)點(diǎn)都有左右子葉且葉子結(jié)點(diǎn)都處在最底層的二叉樹(shù)

完全二叉樹(shù)和滿二叉樹(shù)長(zhǎng)啥樣呢？

3 常見(jiàn)的存儲(chǔ)方法

我們知道數(shù)組最大的一個(gè)特點(diǎn)就是內(nèi)存連續(xù)，方便隨機(jī)訪問(wèn)，下標(biāo)通常從0開(kāi)始。好了，知道這些我們就先看看用數(shù)組如何存儲(chǔ)一棵二叉樹(shù)。

我們了解了二叉樹(shù)的一點(diǎn)基本概念后，為了表示節(jié)點(diǎn)之間的關(guān)系，引入鏈表結(jié)構(gòu)，用左右兩個(gè)指針?lè)謩e指向左節(jié)點(diǎn)和右節(jié)點(diǎn)，這樣就可以串聯(lián)整個(gè)二叉樹(shù)，如下圖所示。

3 二叉樹(shù)的遍歷

先序遍歷:訪問(wèn)根節(jié)點(diǎn)，訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)；若當(dāng)前節(jié)點(diǎn)無(wú)左子樹(shù)，則訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子樹(shù)；

中序遍歷訪問(wèn)當(dāng)前節(jié)點(diǎn)的左子樹(shù)；訪問(wèn)根節(jié)點(diǎn)；訪問(wèn)當(dāng)前節(jié)點(diǎn)的右子樹(shù)；

后序遍歷:從根節(jié)點(diǎn)出發(fā)，依次遍歷各節(jié)點(diǎn)的左右子樹(shù)，直到當(dāng)前節(jié)點(diǎn)左右子樹(shù)遍歷完成后，才訪問(wèn)該節(jié)點(diǎn)元素。

層次遍歷:從上往下一層一層遍歷

說(shuō)實(shí)話，寫的花里胡哨，但是您看到這里不容易了，可以聽(tīng)聽(tīng)音樂(lè)，謝謝您的查看！

二、 二叉排序樹(shù)

二叉排序樹(shù)（Binary Sort Tree）又稱二叉查找樹(shù)、二叉搜索樹(shù)。它或者是一棵空樹(shù)；或者是具有下列性質(zhì)的二叉樹(shù)：

（1）若左子樹(shù)不空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；

（2）若右子樹(shù)不空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；

（3）左、右子樹(shù)也分別為二叉排序樹(shù)；

其高度與樹(shù)中結(jié)點(diǎn)個(gè)數(shù)n成對(duì)數(shù)關(guān)系，檢索的時(shí)間開(kāi)銷為O(logn)。但是很有可能檢索的時(shí)間將變成線性的情況。

三、 哈夫曼樹(shù)

哈夫曼樹(shù)也叫做最優(yōu)二叉樹(shù)，一種帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。那么什么是樹(shù)的帶權(quán)路徑長(zhǎng)度，它是樹(shù)中所有的葉子節(jié)點(diǎn)的權(quán)值乘上其根節(jié)點(diǎn)的路徑長(zhǎng)度。

1 如何構(gòu)造哈夫曼樹(shù)

四、 平衡二叉樹(shù)

之前我們知道了二叉排序樹(shù)出現(xiàn)了線性的情況，所以需要想辦法避免那種情況發(fā)生。這樣兩位爺爺發(fā)明了平衡二叉排序樹(shù)，又叫AVL樹(shù)。那么是怎么定義的呢？平衡二叉排序樹(shù)是一類特殊的二叉排序樹(shù)，它或者為空樹(shù)，或者其左右子樹(shù)都是平衡二叉排序樹(shù)，而且其左右的子數(shù)高度之差絕對(duì)值不超過(guò)1.為了保證相對(duì)平衡，每次插入元素都會(huì)做相應(yīng)的旋轉(zhuǎn)，那么下面來(lái)看看這幾種情況。

1 平衡二叉樹(shù)與非平衡二叉樹(shù)

2 平衡調(diào)整

LL型調(diào)整

如下圖，因?yàn)樵贏的左孩子的左孩子插入新的節(jié)點(diǎn)，導(dǎo)致A的平衡因子從1變?yōu)?，不在滿足根本性質(zhì)[-1,1]，所以需要通過(guò)旋轉(zhuǎn)。顯然，按照大小關(guān)系，結(jié)點(diǎn)B應(yīng)作為新的根結(jié)點(diǎn)，其余兩個(gè)節(jié)點(diǎn)分別作為左右孩子節(jié)點(diǎn)才能平衡，這樣看來(lái)，仿佛A結(jié)點(diǎn)繞結(jié)點(diǎn)B順時(shí)針旋轉(zhuǎn)一樣。

下圖中，當(dāng)在節(jié)點(diǎn)5的左子樹(shù)中插入節(jié)點(diǎn)的時(shí)候而導(dǎo)致不平衡。這種情況調(diào)整如下：首先將元素5的左孩子2提升為新的根結(jié)點(diǎn)；然后將原來(lái)的根結(jié)點(diǎn)元素5變?yōu)樵?的右孩子；其他各子樹(shù)按大小關(guān)系連接。

RR型調(diào)整

如下圖，因?yàn)樵谠?的右孩子的右孩子插入新的節(jié)點(diǎn)，導(dǎo)致元素5的平衡因子從-1變?yōu)?2，不在滿足根本性質(zhì)[-1,1]，所以需要通過(guò)旋轉(zhuǎn)。顯然，按照大小關(guān)系，結(jié)點(diǎn)元素7應(yīng)作為新的根結(jié)點(diǎn)，其余兩個(gè)節(jié)點(diǎn)分別作為左右孩子節(jié)點(diǎn)才能平衡，這樣看來(lái)，仿佛節(jié)點(diǎn)元素5繞結(jié)點(diǎn)元素7逆時(shí)針旋轉(zhuǎn)一樣。

RR型調(diào)整的一般形式如下圖所示，表示節(jié)點(diǎn)元素4的右子樹(shù)5(不一定為空)中插入結(jié)點(diǎn)(圖中陰影部分所示)而導(dǎo)致不平衡( h 表示子樹(shù)的深度)。這種情況調(diào)整如下：

LR調(diào)整

由于節(jié)點(diǎn)元素5的左孩子的右子樹(shù)上插入新節(jié)點(diǎn)，導(dǎo)致不平衡。此時(shí)元素5的平衡因子由1變?yōu)?。第一張圖是LR型的最簡(jiǎn)單形式。顯然，按照大小關(guān)系，元素3應(yīng)作為新的根結(jié)點(diǎn)，其余兩個(gè)節(jié)點(diǎn)分別作為左右孩子節(jié)點(diǎn)才能平衡。

由于節(jié)點(diǎn)元素6增加一個(gè)左孩子，導(dǎo)致元素4變得不平衡。先順時(shí)針旋轉(zhuǎn)元素7再逆時(shí)針旋轉(zhuǎn)4元素達(dá)到平衡。

RL調(diào)整

當(dāng)在元素5的右孩子的左子樹(shù)增加一個(gè)節(jié)點(diǎn)7的時(shí)候，會(huì)造成不平衡的情況。先逆時(shí)針旋轉(zhuǎn)成RR情況，再將元素5順時(shí)針旋轉(zhuǎn)。

第二種情況方法類似，看起來(lái)會(huì)復(fù)雜一點(diǎn)。當(dāng)在元素7得左孩子6增加左孩子元素5得時(shí)候，導(dǎo)致元素4變得不平衡。那么先順時(shí)針調(diào)整元素7，再逆時(shí)針調(diào)整元素4

五、 B樹(shù)和B+樹(shù)

小伙伴們有沒(méi)有想過(guò)，為什么很多數(shù)據(jù)庫(kù)中的索引采用B+樹(shù)呢？以及為什么索引是放在磁盤上。

1 B樹(shù)

如果使用二叉樹(shù)作為索引的底層實(shí)現(xiàn)結(jié)構(gòu)，樹(shù)會(huì)變得很高，從而增加了磁盤的IO次數(shù)，從而影響數(shù)據(jù)查詢時(shí)間。因此為了降低其高度，讓一個(gè)節(jié)點(diǎn)有多個(gè)子節(jié)點(diǎn)，B樹(shù)就誕生了。

B樹(shù)的容顏

一個(gè)M階B樹(shù)的哪些特性

官方英文

1、Every node has at most m children.

2、Every non-leaf node (except root) has at least [m/2] child nodes.

3、The root has at least two children if it is not a leaf node.

4、A non-leaf node with k children contains k ? 1 keys.

5、All leaves appear in the same level.

中文

• 根節(jié)點(diǎn)的兒子數(shù)量范圍[2,M]

• 每個(gè)中間節(jié)點(diǎn)包含 k-1 個(gè)關(guān)鍵字和 k 個(gè)孩子，孩子的數(shù)量 = 關(guān)鍵字的數(shù)量 +1，k 的取值范圍為 [ceil(M/2), M]。

• 葉子節(jié)點(diǎn)包括 k-1 個(gè)關(guān)鍵字（葉子節(jié)點(diǎn)沒(méi)有孩子），k 的取值范圍為 [ceil(M/2), M]。

• 假設(shè)中間節(jié)點(diǎn)節(jié)點(diǎn)的關(guān)鍵字為：Key[1], Key[2], …, Key[k-1]，且關(guān)鍵字按照升序排序，即 Key[i]<Key[i+1]。此時(shí) k-1 個(gè)關(guān)鍵字相當(dāng)于劃分了 k 個(gè)范圍，也就是對(duì)應(yīng)著 k個(gè)指針，即為：P[1], P[2], …, P[k]，其中 P[1] 指向關(guān)鍵字小于 Key[1] 的子樹(shù)，P[i] 指向關(guān)鍵字屬于 (Key[i-1], Key[i]) 的子樹(shù)，P[k] 指向關(guān)鍵字大于 Key[k-1] 的子樹(shù)。

• 所有葉子節(jié)點(diǎn)位于同一層。

舉個(gè)例子

上圖為三階圖，查看磁盤3，關(guān)鍵字為20，30.三個(gè)孩子分別是(18,19),(22,25),(32,36).其中(18,19)小于20，(22,25)在(20,30)之間，(32，36)大于30.

那么在查找搜索的過(guò)程中，是怎樣的訪問(wèn)過(guò)程呢？假設(shè)查找元素7

• 與根節(jié)點(diǎn)比較，得到指針p1

• 根據(jù)p1來(lái)到磁盤2，關(guān)鍵字為(9,15),發(fā)現(xiàn)小于9，得到指針p1

• 根據(jù)p1來(lái)到磁盤5，關(guān)鍵字為(7,8),發(fā)現(xiàn)正好有7.

2 B+樹(shù)

前文介紹了二分查找方法為O(log2n)，但是會(huì)出現(xiàn)深度非常大退化為鏈表，其查找數(shù)據(jù)的時(shí)間復(fù)雜度變?yōu)镺(n)。從而就出現(xiàn)了平衡二叉樹(shù)。

B+樹(shù)容顏

B+樹(shù)性質(zhì)

• 有m個(gè)孩子的節(jié)點(diǎn)就有m個(gè)關(guān)鍵字(孩子數(shù)量=關(guān)鍵字?jǐn)?shù))，而在B樹(shù)中孩子數(shù)量=關(guān)鍵字?jǐn)?shù)+1

• 非葉子節(jié)點(diǎn)關(guān)鍵字也會(huì)出現(xiàn)在子節(jié)點(diǎn)中，而且子節(jié)點(diǎn)中為所有關(guān)鍵字的最大或最小
  非葉子節(jié)點(diǎn)只是用來(lái)索引，不保存數(shù)據(jù)的記錄。在B樹(shù)中，非葉子節(jié)點(diǎn)既保存索引也保存數(shù)據(jù)記錄。

• 所有關(guān)鍵字都存在于葉子節(jié)點(diǎn)，葉子節(jié)點(diǎn)構(gòu)成有序鏈表，而且關(guān)鍵字按照從大到小或者從小到大順序連接。

優(yōu)點(diǎn)：

• 因?yàn)锽+樹(shù)中間節(jié)點(diǎn)沒(méi)有關(guān)鍵字，所以同樣大小的磁盤頁(yè)可以容納更多的節(jié)點(diǎn)元素，也就是說(shuō)在相同的情況下，B+樹(shù)更加的矮胖，這樣的話，IO的次數(shù)也就比較少。

• B+樹(shù)的查詢相比B樹(shù)更加穩(wěn)定，因?yàn)锽+樹(shù)的查詢是必須到葉子節(jié)點(diǎn)，而B(niǎo)樹(shù)有可能在中間節(jié)點(diǎn)，也可能非中間節(jié)點(diǎn)。

• B+樹(shù)葉子節(jié)點(diǎn)形成了有序鏈表，更加有利于范圍的查詢

那么其查詢的過(guò)程是什么樣的呢。我們假設(shè)查詢?cè)?3

• 首先與根節(jié)點(diǎn)的關(guān)鍵字(10,18,40)比較，13在10和18之間，此時(shí)得到P1指針

• 磁盤2中的關(guān)鍵字為(10,12,15),這時(shí)15大于13，所有磁盤6

• 關(guān)鍵字為(12,13)，找到13

六、 紅黑樹(shù)

雖然在大部分情況下，面試中不會(huì)讓你寫出來(lái)，在面試中還是經(jīng)常會(huì)問(wèn)原理的內(nèi)容，所以了解了解更穩(wěn)妥(比如c++中的很榮STL底層就是基于它),時(shí)間復(fù)雜度是O(lgn)。其基本概念如下。

1 紅黑樹(shù)的性質(zhì)

首先紅黑樹(shù)的節(jié)點(diǎn)要么是紅色，要么是黑色。

1 根節(jié)點(diǎn)是黑色的

2 每個(gè)葉子節(jié)點(diǎn)是黑色的且不存儲(chǔ)數(shù)據(jù)

3 任何相鄰的節(jié)點(diǎn)不能同時(shí)為紅色

4 每個(gè)節(jié)點(diǎn)，從該節(jié)點(diǎn)到可達(dá)的葉子節(jié)點(diǎn)的所有路徑，其黑色節(jié)點(diǎn)的數(shù)目相同。

參考連接

https://blog.csdn.net/isunbin/article/details/81707606

https://www.javatpoint.com/b-plus-tree

https://time.geekbang.org/column/intro/100029501

https://www.cnblogs.com/geektcp/p/9992213.html

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒(méi)關(guān)注的小伙伴，可以長(zhǎng)按關(guān)注一下：
長(zhǎng)按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠(chéng)摯感謝