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

一、 二叉樹

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

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

掌握二叉樹的五種性質(zhì)，能讓我們在筆試中做題變得游刃有余，也就有更多的時間處理其他的題目。其具體的性質(zhì)看下圖。

2 兩個特別的二叉樹

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

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

完全二叉樹和滿二叉樹長啥樣呢？

3 常見的存儲方法

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

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

3 二叉樹的遍歷

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

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

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

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

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

二、 二叉排序樹

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

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

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

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

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

三、 哈夫曼樹

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

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

四、 平衡二叉樹

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

1 平衡二叉樹與非平衡二叉樹

2 平衡調(diào)整

LL型調(diào)整

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

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

RR型調(diào)整

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

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

LR調(diào)整

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

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

RL調(diào)整

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

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

五、 B樹和B+樹

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

1 B樹

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

B樹的容顏

一個M階B樹的哪些特性

官方英文

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]

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

• 葉子節(jié)點(diǎn)包括 k-1 個關(guān)鍵字（葉子節(jié)點(diǎn)沒有孩子），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]。此時 k-1 個關(guān)鍵字相當(dāng)于劃分了 k 個范圍，也就是對應(yīng)著 k個指針，即為：P[1], P[2], …, P[k]，其中 P[1] 指向關(guān)鍵字小于 Key[1] 的子樹，P[i] 指向關(guān)鍵字屬于 (Key[i-1], Key[i]) 的子樹，P[k] 指向關(guān)鍵字大于 Key[k-1] 的子樹。

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

舉個例子

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

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

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

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

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

2 B+樹

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

B+樹容顏

B+樹性質(zhì)

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

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

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

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

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

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

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

那么其查詢的過程是什么樣的呢。我們假設(shè)查詢元素13

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

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

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

六、 紅黑樹

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

1 紅黑樹的性質(zhì)

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

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

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

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

4 每個節(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òu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：
長按訂閱更多精彩▼
如有收獲，點(diǎn)個在看，誠摯感謝