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

一、二叉樹

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

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

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

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

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

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

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

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

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

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

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)元素。

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

二、二叉排序樹

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

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

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

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

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

三、哈夫曼樹

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

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

四、平衡二叉樹

之前我們知道了二叉排序樹出現(xiàn)了線性的情況，所以需要想辦法避免那種情況發(fā)生。這樣兩位爺爺發(fā)明了平衡二叉排序樹，又叫AVL樹。那么是怎么定義的呢？平衡二叉排序樹是一類特殊的二叉排序樹，它或者為空樹，或者其左右子樹都是平衡二叉排序樹，而且其左右的子數(shù)高度之差絕對(duì)值不超過1.為了保證相對(duì)平衡，每次插入元素都會(huì)做相應(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)，其余兩個(gè)節(jié)點(diǎn)分別作為左右孩子節(jié)點(diǎn)才能平衡，這樣看來，仿佛A結(jié)點(diǎn)繞結(jié)點(diǎn)B順時(shí)針旋轉(zhuǎn)一樣。

下圖中，當(dāng)在節(jié)點(diǎn)5的左子樹中插入節(jié)點(diǎn)的時(shí)候而導(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)，其余兩個(gè)節(jié)點(diǎn)分別作為左右孩子節(jié)點(diǎn)才能平衡，這樣看來，仿佛節(jié)點(diǎn)元素5繞結(jié)點(diǎn)元素7逆時(shí)針旋轉(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)致不平衡。此時(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的右孩子的左子樹增加一個(gè)節(jié)點(diǎn)7的時(shí)候，會(huì)造成不平衡的情況。先逆時(shí)針旋轉(zhuǎn)成RR情況，再將元素5順時(shí)針旋轉(zhuǎn)。

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

五、 B樹和B+樹

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

1 B樹

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

B樹的容顏

一個(gè)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]
每個(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)沒有孩子），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]
所有葉子節(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.

那么在查找搜索的過程中，是怎樣的訪問過程呢？假設(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)，但是會(huì)出現(xiàn)深度非常大退化為鏈表，其查找數(shù)據(jù)的時(shí)間復(fù)雜度變?yōu)镺(n)。從而就出現(xiàn)了平衡二叉樹。

B+樹容顏

B+樹性質(zhì)

有m個(gè)孩子的節(jié)點(diǎn)就有m個(gè)關(guān)鍵字(孩子數(shù)量=關(guān)鍵字?jǐn)?shù))，而在B樹中孩子數(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)只是用來索引，不保存數(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)鍵字，所以同樣大小的磁盤頁(yè)可以容納更多的節(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è)查詢?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

六、紅黑樹

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

1 紅黑樹的性質(zhì)

首先紅黑樹的節(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

拜托，別問我什么各種Tree了，干就完事！

一、 二叉樹