數據結構-樹的基本概念
數據結構-樹的基本概念
1.樹 ： 一般以鏈表的方式存儲。
（1）樹可以發散為生活中的各種可能。比如機器人要實現圍棋，需要列出各種可能。
（2）樹的遍歷方式：
深度優先: 使用遞歸實現 – 最先根節點，然後所有左邊再所有右邊。
前序：根->左->右
中序：左->根->右
後序：左->右->根
廣度優先：使用隊列實現 – 最先根節點，然後一層一層擴散；
優先順序優先：使用於現實中的業務場景。應用在推薦演算法、深度學習等。
優缺點：
深度優先：不全部保留結點，佔用空間少；有回溯操作(即有入棧、出棧操作)，運行速度慢。
廣度優先：保留全部結點，佔用空間大； 無回溯操作(即無入棧、出棧操作)，運行速度快。
（3）概念：
度數：每個節點所有子樹的個數
層數
高度：樹的最大層數。
森林：移去根節點就是森林
2.二叉樹：最多只有兩個子節點（度數<=2）
2.1 由於N叉樹N越大浪費的指針的比例越大，所以一般使用二叉樹。
n叉樹有m個節點，那麼空指針： n * m -(m-1) = m(n-1) +1 ，浪費率為 (m(n-1) +1)/(m*n) = 1 – 1/n + 1/mn 約等於 1- 1/n
比如：n = 2 需要指針約1/2
n = 3 需要指針約2/3
n = 4 需要指針約3/4
2.2 高度為h的二叉樹最大總節點數為 2^h-1
層數為K的節點數最多為2^(k-1)，即2的(k-1)次方
2.3 滿二叉樹：節點個數都滿了。高度為h，那麼樹的總節點數為 2^h – 1
完全二叉樹：和滿二叉樹的區別 – 最後一層可以不滿，但是必須滿足順序- 先有左節點才能有右節點。
嚴格二叉樹：非葉子節點必須有左右。
斜二叉樹（一根棍子）：沒有左節點的叫右斜二叉樹；沒有右節點的叫左斜二叉樹
2.4 二叉樹的存儲：一般採用鏈表。
（1）數組存儲：當成滿二叉樹處理，使用索引值表示節點。
數組存儲的劣勢：增刪數據麻煩、接近滿二叉樹才能節省空間。
註：完全二叉樹也比較適合用數組存儲，能緩解浪費空間的問題。但是仍然要考慮場景是否需要頻繁插入和刪除。
（2）鏈表存儲：節點增刪容易，缺點是難以找到父節點，除非在每一個節點中增加一個父欄位。
2.5 線索二叉樹：n節點的二叉樹會有n-1個鏈接，剩下n+1個空鏈接，可以讓它分別指向前一個節點和後一個節點。
線索化的過程就是遍歷二叉樹的過程。在遍歷的過程中，檢查當前結點的左、右指針域是否為空，若為空，將它們改為指向前驅結點或後繼結點的線索。
當線索化二叉樹以後，遍歷二叉樹的時間複雜度雖然仍然是O(n)，但常數因子要比演算法小（速度更快），且不需要使用堆棧處理。
因此如果程式中所用的二叉樹需要經常遍歷或查找結點在遍歷所得的線性序列的前驅和後繼，則應採用線索鏈表作為二叉樹的存儲結構。
2.6 霍夫曼樹（優化二叉樹）：根據數據出現的頻率來構建二叉樹，可以用於數據壓縮。
3.樹-二叉搜索樹Binary Search Tree（排序二叉樹、有序二叉樹、二叉查找樹）
ps：因為普通的二叉樹遍歷複雜度是O(n)，和鏈表一樣。所以要更規範的二叉樹。
特點：左子樹的所有節點均小於它的根節點
右子樹的所有節點均小大它的根節點
左右子樹也分別為二叉搜索樹。（這就是重複性）
中序遍歷：屬於升序遍歷
查詢：O(log2 n)
插入：O(log2 n) – 查詢比鏈表的O(n)有很大優勢。
刪除：O(log2 n)
查找到相關節點：如果是葉子節點，直接刪除；
如果不是葉子節點，那麼刪除後，原來的位置從右邊選擇最小的節點來代替。
缺點：左邊節點都被刪完了，那麼可能變成所有節點組成一條直線（相當於鏈表）。
4.樹-平衡二叉樹 (Balanced Binary Tree) – 又稱AVL樹(AVL是發明者的名字)：性能保證的前提
背景：二叉樹刪除節點，極端情況下會變成一條線（相當於鏈表），這樣查詢複雜度和鏈表一樣為O(n)
平衡二叉樹是採用二分法思維把數據按規則組裝成一個樹形結構的數據，保證數據平衡的情況下查找數據的速度近於二分法查找
操作：每次插入或刪除時，都要處理成平衡的。
（1）平衡因子：左子樹比 – 右子樹的高度：保持在[1 0 -1]之間。
葉子節點為0.
（2）旋轉操作：新增或刪除後調整
左旋：針對右右子樹
右旋：針對左左子樹
左右旋：針對左右子樹
右左旋：針對右左子樹
帶子樹的旋轉：
不足：需要額外存儲資訊、且調整次數比較頻繁。
5.樹-近似平衡二叉樹 – 紅黑樹: 能保證左右子樹的高度差小於兩倍。
5.1 背景：解決平衡二叉樹調整次數太頻繁的問題。
（1）根節點是黑色
（2）每個葉子節點都是黑的（NIL節點）
（3）不能有相鄰的兩個紅色節點
（4）任意一個節點到每個葉子的所有路徑都包含相同數目的黑色節點。
以上條件可以證明出：能保證左右子樹的高度差小於兩倍
5.2 優勢：查找、刪除、插入紅黑樹比AVL更快。
存儲的記憶體的資訊也比AVL少。
場景：用在高級語言的庫中，比如set集合
6. B樹（又稱B-tree樹或B-樹）
一棵m階的B樹滿足下列條件（m階表示節點最大有m個子樹）
樹中每個結點至多有m個孩子。
除根結點和葉子結點外，其它每個結點至少有m/2個孩子。
根結點至少有2個孩子（如果B樹只有一個結點除外）。
所有葉結點在同一層，B樹的葉結點可以看成一種外部節點，不包含任何資訊。
有k個關鍵字(關鍵字按遞增次序排列)的非葉結點恰好有k+1個孩子。
關鍵字數量x要滿足：
根節點 1 <= x <= m-1
非根節點 Math.ceil(m/2) – 1 <= x <= m-1
子樹數量（孩子）要y要滿足：
每個節點的子節點個數y = x + 1
根節點： 2<=子節點個數y <= m
非根節點：Math.ceil(m/2) <= y <= m
m = 3 時，2<= y <= 3 因此3階B樹稱為(2,3)樹或2-3樹
m = 4 時，2<= y <= 4 因此4階B樹稱為(2,4)樹2-3-4樹
m = 5 時，3<= y <= 5 因此5階B樹稱為(3,5)樹
m = 6 時，3<= y <= 6 因此6階B樹稱為(3,6)樹
7. B+樹
葉子節點是雙向鏈表，數據從小到大排列。
多餘一頁的數據也要進行多次I/0
對於非主鍵索引：先查詢非主鍵索引的B+樹得到主鍵ID，再根據主鍵ID查詢主鍵的B+樹。
8. B*樹
B*樹是B+樹的變種，相對於B+樹他們的不同之處如下：
（1）首先是關鍵字個數限制問題，B+樹初始化的關鍵字初始化個數是cei(m/2)，b*樹的初始化個數為（cei(2/3*m)）
（2）B+樹節點滿時就會分裂，而B*樹節點滿時會檢查兄弟節點是否滿（因為每個節點都有指向兄弟的指針）
如果兄弟節點未滿則向兄弟節點轉移關鍵字，如果兄弟節點已滿，則從當前節點和兄弟節點各拿出1/3的數據創建一個新的節點出來；
優勢：在B+樹的基礎上因其初始化的容量變大，使得節點空間使用率更高，而又存有兄弟節點的指針，
可以向兄弟節點轉移關鍵字的特性使得B*樹額分解次數變得更少；
8. LSM樹（Log Structured Merge Tree，結構化合併樹）
LSM樹和B+樹相比，LSM樹犧牲了部分讀性能，用來大幅提高寫性能。
可以用跳錶實現LSM的記憶體部分
9. 散列表：單記錄查詢性能最好的。
