1、 樹
1.1 算法樹與現實樹的區別
1.2 樹相關概念
1.3 樹的類型
2、 二叉樹
2.1 滿二叉樹（full binary tree）
2.2 完全二叉樹（complete binary tree）
2.3 二叉查找樹（BST）
2.4 平衡二叉樹（AVL樹）
2.5 Huffman編碼樹
2.6 紅黑樹
3、 B樹（多路搜索樹）
3.1 2-3樹
3.2 B+樹
1、 算法概述
樹：tree，數據結構和算法中的樹，是一種非線性的數據結構，它是由n(n>=1)個有限節點組成的一種具有層次關係的集合，之所以稱之為樹，是因為它長得像一顆倒過來的樹。
1.1 算法樹與現實樹的區別
現實的樹結構：
算法中的樹結構（將實物樹上下顛倒過來）：
1.2 樹相關概念：
- 樹的結點（node）：包含一個數據元素及若干指向子樹的分支；
- 孩子結點（child node）：結點的子樹的根稱為該結點的孩子；
- 雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；
- 兄弟結點：同一雙親的孩子結點； 堂兄結點：同一層上結點；
- 祖先結點: 從根到該結點的所經分支上的所有結點
- 子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫
- 結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；
- 樹的深度：樹中最大的結點層
- 結點的度：結點子樹的個數
- 樹的度： 樹中最大的結點度。
- 葉子結點：也叫終端結點，是度為 0 的結點；
- 分枝結點：度不為0的結點；
- 路徑：如果一棵樹有一串結點n1，n2，...，nk，且ni是ni+1的父結點（1<=i
1.3 樹的類型：
- 無序樹：樹中的任意節點的子節點之間沒有順序關係，也稱自由樹；
- 有序樹：樹中的任意節點的子節點之間有順序關係。
2. 二叉樹
在計算機科學中，二叉樹（binary tree）是每個結點（node）最多有兩個子樹的樹結構。
二叉樹的不同類型：
- 滿二叉樹（full binary tree）
- 完全二叉樹（complete binary tree）
- 二叉查找樹（BST）
- 平衡二叉樹（AVL樹）
- Huffman編碼樹
- 紅黑樹
2.1 滿二叉樹（full binary tree）
除最後一層無任何子節點外，每一層上的所有節點都有兩個子節點，最後一層都是葉子節點。滿足下列性質：
1）一顆樹深度為h，最大層數為k，深度與最大層數相同，k=h；
2）葉子節點數（最後一層）為2k−1；
3）第 i 層的節點數是：2i−1；
4）總節點數是：2k−1，且總節點數一定是奇數。
2.2 完全二叉樹（complete binary tree）
若設二叉樹的深度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第 h 層所有的結點都連續集中在最左邊，這就是完全二叉樹。滿足下列性質：
1）只允許最後一層有空缺結點且空缺在右邊，即葉子節點只能在層次最大的兩層上出現；
2）對任一節點，如果其右子樹的深度為j，則其左子樹的深度必為j或j+1。 即度為1的點只有1個或0個；
3）除最後一層，第 i 層的節點數是：2i−1；
4）有n個節點的完全二叉樹，其深度為：log2n+1或為log2n+1；
5）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。
2.3 二叉查找樹（BST）
又稱二叉查找樹（Binary Search Tree, BST）、二叉排序樹（Binary Sort Tree）。它是一顆空樹或是滿足下列性質的二叉樹：
1）若左子樹不空，則左子樹上所有節點的值均小於或等於它的根節點的值；
2）若右子樹不空，則右子樹上所有節點的值均大於或等於它的根節點的值；
3）左、右子樹也分別為二叉排序樹。
2.4 平衡二叉樹（AVL樹）
又被稱為AVL樹，它是一顆空樹或左右兩個子樹的高度差的絕對值不超過 1，並且左右兩個子樹都是一棵平衡二叉樹。
2.5 Huffman編碼樹
Huffman編碼樹（Huffman coding tree），簡稱Huffman樹，是一棵滿二叉樹，其每個葉結點對應一個字母，葉結點的權重為對應字母的出現頻率。
Huffman樹具有最小外部路徑權重（minimum external path weight），即對於給定的葉結點集合，具有最小加權路徑長度。一個葉結點的加權路徑長度（weighted path length）定義為權乘以深度。
2.6 紅黑樹
是每個節點都帶有顏色屬性（顏色為紅色或黑色）的自平衡二叉查找樹，滿足下列性質：
1）節點是紅色或黑色；
2）根節點是黑色；
3）所有葉子節點都是黑色；
4）每個紅色節點必須有兩個黑色的子節點。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點。)
5）從任一節點到其每個葉子的所有簡單路徑都包含相同數目的黑色節點。
3. B樹（多路搜索樹）
b樹（balance tree）和b+樹應用在數據庫索引，可以認為是m叉的多路平衡查找樹。
一個M階的b樹具有如下幾個特徵：
- 定義任意非葉子結點最多隻有M個兒子，且M>2；
- 根結點的兒子數為[2, M]；
- 除根結點以外的非葉子結點的兒子數為[M/2, M]，向上取整；
- 非葉子結點的關鍵字個數=兒子數-1；
- 所有葉子結點位於同一層；
- k個關鍵字把節點拆成k+1段，分別指向k+1個兒子，同時滿足查找樹的大小關係。
3.1 2-3樹
2-3樹是一個三階B樹。
B樹插入是2-3樹插入的推廣：
- 第一步是找到應當包含待插入關鍵碼的葉結點，並檢查是否有空間；
- 如果該結點中有地方，則插入關鍵碼，否則把結點分裂成兩個結點，並把中間的關鍵碼提升到父結點；
- 如果父結點也滿了，就再分裂父結點，並再次提升中間的關鍵碼。插入過程保證所有結點至少半滿。
3.2 B+樹
B+樹只在葉結點存儲記錄，內部結點存儲關鍵碼值，用於引導檢索，並把每個關鍵碼與一個指向子女結點的指針關聯起來。
B+樹的葉結點一般鏈接起來，形成一個雙鏈表，這樣通過訪問鏈表中的所有葉結點，就可以按排序的次序遍歷全部記錄。
閱讀更多 編程家園 的文章
