一、 二叉樹
二叉樹是每個節點最多有兩個子樹的樹結構。它有五種基本形態：二叉樹可以是空集；根可以有空的左子樹或右子樹；或者左、右子樹皆為空。如下圖所示
1 二叉樹的五種性質
掌握二叉樹的五種性質，能讓我們在筆試中做題變得遊刃有餘，也就有更多的時間處理其他的題目。其具體的性質看下圖。
2 兩個特別的二叉樹
完全二叉樹:對於深度為K的，有n個結點的二叉樹，當且僅當其每一個結點都與深度為K的滿二叉樹中編號從1至n的結點一一對應時稱之為完全二叉樹。
滿二叉樹:除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹
完全二叉樹和滿二叉樹長啥樣呢？
完全二叉樹與滿二叉樹
3 常見的存儲方法
我們知道數組最大的一個特點就是內存連續，方便隨機訪問，下標通常從0開始。好了，知道這些我們就先看看用數組如何存儲一棵二叉樹。
數組方式
我們瞭解了二叉樹的一點基本概念後，為了表示節點之間的關係，引入鏈表結構，用左右兩個指針分別指向左節點和右節點，這樣就可以串聯整個二叉樹，如下圖所示。
鏈表方式
3 二叉樹的遍歷
先序遍歷:訪問根節點，訪問當前節點的左子樹；若當前節點無左子樹，則訪問當前節點的右子樹；
先序遍歷
中序遍歷訪問當前節點的左子樹；訪問根節點；訪問當前節點的右子樹；
中序遍歷
後序遍歷:從根節點出發，依次遍歷各節點的左右子樹，直到當前節點左右子樹遍歷完成後，才訪問該節點元素。
後序遍歷
層次遍歷:從上往下一層一層遍歷
層次遍歷
二、 二叉排序樹
二叉排序樹（Binary Sort Tree）又稱二叉查找樹、二叉搜索樹。它或者是一棵空樹；或者是具有下列性質的二叉樹：
（1）若左子樹不空，則左子樹上所有結點的值均小於它的根結點的值；
（2）若右子樹不空，則右子樹上所有結點的值均大於它的根結點的值；
（3）左、右子樹也分別為二叉排序樹；
其高度與樹中結點個數n成對數關係，檢索的時間開銷為O(logn)。但是很有可能檢索的時間將變成線性的情況。
三、 哈夫曼樹
哈夫曼樹也叫做最優二叉樹，一種帶權路徑長度最短的二叉樹。那麼什麼是樹的帶權路徑長度，它是樹中所有的葉子節點的權值乘上其根節點的路徑長度。
1 如何構造哈夫曼樹
構造哈夫曼樹
四、 平衡二叉樹
之前我們知道了二叉排序樹出現了線性的情況，所以需要想辦法避免那種情況發生。這樣兩位爺爺發明了平衡二叉排序樹，又叫AVL樹。那麼是怎麼定義的呢？平衡二叉排序樹是一類特殊的二叉排序樹，它或者為空樹，或者其左右子樹都是平衡二叉排序樹，而且其左右的子數高度之差絕對值不超過1.為了保證相對平衡，每次插入元素都會做相應的旋轉，那麼下面來看看這幾種情況。
1 平衡二叉樹與非平衡二叉樹
平衡二叉樹與非平衡二叉樹
2 平衡調整
LL型調整
如下圖，因為在A的左孩子的左孩子插入新的節點，導致A的平衡因子從1變為2，不在滿足根本性質[-1,1]，所以需要通過旋轉。顯然，按照大小關係，結點B應作為新的根結點，其餘兩個節點分別作為左右孩子節點才能平衡，這樣看來，彷彿A結點繞結點B順時針旋轉一樣。
下圖中，當在節點5的左子樹中插入節點的時候而導致不平衡。這種情況調整如下：首先將元素5的左孩子2提升為新的根結點；然後將原來的根結點元素5變為元素2的右孩子；其他各子樹按大小關係連接。
RR型調整
如下圖，因為在元素5的右孩子的右孩子插入新的節點，導致元素5的平衡因子從-1變為-2，不在滿足根本性質[-1,1]，所以需要通過旋轉。顯然，按照大小關係，結點元素7應作為新的根結點，其餘兩個節點分別作為左右孩子節點才能平衡，這樣看來，彷彿節點元素5繞結點元素7逆時針旋轉一樣。
RR型調整的一般形式如下圖所示，表示節點元素4的右子樹5(不一定為空)中插入結點(圖中陰影部分所示)而導致不平衡( h 表示子樹的深度)。這種情況調整如下：
LR調整
由於節點元素5的左孩子的右子樹上插入新節點，導致不平衡。此時元素5的平衡因子由1變為2。第一張圖是LR型的最簡單形式。顯然，按照大小關係，元素3應作為新的根結點，其餘兩個節點分別作為左右孩子節點才能平衡。
由於節點元素6增加一個左孩子，導致元素4變得不平衡。先順時針旋轉元素7再逆時針旋轉4元素達到平衡。
RL調整
當在元素5的右孩子的左子樹增加一個節點7的時候，會造成不平衡的情況。先逆時針旋轉成RR情況，再將元素5順時針旋轉。
第二種情況方法類似，看起來會複雜一點。當在元素7得左孩子6增加左孩子元素5得時候，導致元素4變得不平衡。那麼先順時針調整元素7，再逆時針調整元素4
五、 B樹和B+樹
小夥伴們有沒有想過，為什麼很多數據庫中的索引採用B+樹呢？以及為什麼索引是放在磁盤上。
1 B樹
如果使用二叉樹作為索引的底層實現結構，樹會變得很高，從而增加了磁盤的IO次數，從而影響數據查詢時間。因此為了降低其高度，讓一個節點有多個子節點，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.
中文
- 根節點的兒子數量範圍[2,M]
- 每個中間節點包含 k-1 個關鍵字和 k 個孩子，孩子的數量 = 關鍵字的數量 +1，k 的取值範圍為 [ceil(M/2), M]。
- 葉子節點包括 k-1 個關鍵字（葉子節點沒有孩子），k 的取值範圍為 [ceil(M/2), M]。
- 假設中間節點節點的關鍵字為：Key[1], Key[2], …, Key[k-1]，且關鍵字按照升序排序，即 Key[i]
- 所有葉子節點位於同一層。
舉個例子
上圖為三階圖，查看磁盤3，關鍵字為20，30.三個孩子分別是(18,19),(22,25),(32,36).其中(18,19)小於20，(22,25)在(20,30)之間，(32，36)大於30.
那麼在查找搜索的過程中，是怎樣的訪問過程呢？假設查找元素7
- 與根節點比較，得到指針p1
- 根據p1來到磁盤2，關鍵字為(9,15),發現小於9，得到指針p1
- 根據p1來到磁盤5，關鍵字為(7,8),發現正好有7.
2 B+樹
前文介紹了二分查找方法為O(log2n)，但是會出現深度非常大退化為鏈表，其查找數據的時間複雜度變為O(n)。從而就出現了平衡二叉樹。
B+樹容顏
B+樹性質
- 有m個孩子的節點就有m個關鍵字(孩子數量=關鍵字數)，而在B樹中孩子數量=關鍵字數+1
- 非葉子節點關鍵字也會出現在子節點中，而且子節點中為所有關鍵字的最大或最小非葉子節點只是用來索引，不保存數據的記錄。在B樹中，非葉子節點既保存索引也保存數據記錄。
- 所有關鍵字都存在於葉子節點，葉子節點構成有序鏈表，而且關鍵字按照從大到小或者從小到大順序連接。
優點：
- 因為B+樹中間節點沒有關鍵字，所以同樣大小的磁盤頁可以容納更多的節點元素，也就是說在相同的情況下，B+樹更加的矮胖，這樣的話，IO的次數也就比較少。
- B+樹的查詢相比B樹更加穩定，因為B+樹的查詢是必須到葉子節點，而B樹有可能在中間節點，也可能非中間節點。
- B+樹葉子節點形成了有序鏈表，更加有利於範圍的查詢
那麼其查詢的過程是什麼樣的呢。我們假設查詢元素13
- 首先與根節點的關鍵字(10,18,40)比較，13在10和18之間，此時得到P1指針
- 磁盤2中的關鍵字為(10,12,15),這時15大於13，所有磁盤6
- 關鍵字為(12,13)，找到13
六、 紅黑樹
雖然在大部分情況下，面試中不會讓你寫出來，在面試中還是經常會問原理的內容，所以瞭解瞭解更穩妥(比如c++中的很榮STL底層就是基於它),時間複雜度是O(lgn)。其基本概念如下。
1 紅黑樹的性質
首先紅黑樹的節點要麼是紅色，要麼是黑色。
1 根節點是黑色的
2 每個葉子節點是黑色的且不存儲數據
3 任何相鄰的節點不能同時為紅色
4 每個節點，從該節點到可達的葉子節點的所有路徑，其黑色節點的數目相同。
閱讀更多 JAVA髮量告急 的文章
