二叉排序樹學習筆記

二叉排序樹（Binary Sort Tree）又稱二叉查找樹（Binary Search Tree）。

AVL樹：在計算機科學中，AVL樹是最先發明的自平衡二叉查找樹。在AVL樹中任何節點的兩個子樹的高度最大差別為一，所以它也被稱為高度平衡樹。AVL樹在節點增刪後不再滿足AVL樹條件，則需要“旋轉”以重新構造自身。

紅黑樹：RB樹。每個節點都帶有顏色屬性的二叉查找樹。在二叉查找樹強制一般要求以外，對於任何有效的紅黑樹我們增加了如下的額外要求:

• 節點是紅色或黑色。
• 根節點是黑色。
• 每個葉節點（NIL節點，空節點）是黑色的。
• 每個紅色節點的兩個子節點都是黑色。(從每個葉子到根的所有路徑上不能有兩個連續的紅色節點)
• 從任一節點到其每個葉子的所有路徑都包含相同數目的黑色節點。

下圖就是一棵紅黑樹：

AVL是嚴格平衡樹，因此在增加或者刪除節點的時候，根據不同情況，旋轉的次數比紅黑樹要多；
紅黑是弱平衡的，用非嚴格的平衡來換取增刪節點時候旋轉次數的降低；
所以簡單說，搜索的次數遠遠大於插入和刪除，那麼選擇AVL樹，如果搜索，插入刪除次數幾乎差不多，應該選擇RB樹。

可以看到，這三者查找的時間復雜度O(log2N)與樹的深度相關，那麼降低樹的深度自然會提高查找效率 。

但是在大規模數據存儲中，使用二叉查找樹實現索引查詢，元素數量是非常大的，這樣就導致二叉查找樹結構樹的深度過大，進而造成磁盤I/O讀寫過於頻繁，導致查詢效率低下，那麼如何減少樹的深度，一個基本的想法就是：采用多叉樹結構。這樣我們就提出了一個新的查找樹結構——多路查找樹。根據平衡二叉樹的啟發，自然就想到平衡多路查找樹結構。

B-tree：一種平衡多路搜索樹（並不是二叉的）。B-tree樹即B樹， B即Balanced ，平衡的意思。

B+-tree：B+的搜索與B-樹也基本相同，區別是B+樹所有關鍵字都在葉子結點出現，因此只有達到葉子結點才命中（B-樹可以在非葉子結點命中）。B+樹葉子節點鏈表中的關鍵字是有序的，且所有葉子結點都有一個鏈指針指向下一個葉子節點，這個特性使得B+樹對范圍查找的效率比B樹高的多，比如對已經建立索引的數據庫記錄，查找10<=id<=20，那麼只要通過根節點搜索到id=10的葉節點，之後只要根據葉節點的鏈表找到第一個大於20的就行了，比B-樹在查找10到20內的每一個時每次都從根節點出發查找提高了不少效率。

B*-tree：在B+樹基礎上，為非葉子結點也增加鏈表指針，將結點的最低利用率從1/2提高到2/3。

Huffman tree：又稱最優樹。對應的有哈夫曼編碼，其主要應用在數據壓縮，加密解密等場合。

上述只是常見但很小一部分樹，最後附圖一幅：