1. AVL樹（平衡二叉樹）
2. 紅黑樹
3. B(+)樹
4. Trie樹（字典樹）
1. AVL樹（平衡二叉樹）
任何一個節點的左子支高度與右子支高度之差的絕對值不超過1的平衡二叉樹。
AVL樹特性 ：
- 一般是用平衡因子差值決定並通過旋轉來實現，左右子樹樹高差不超過1。
- 與紅黑樹比較它是嚴格的平衡二叉樹，平衡條件非常嚴格（樹高差只有1），只要插入或刪除不滿足上面的條件就要通過旋轉來保持平衡。
- 由於旋轉是非常耗費時間的。我們可以推出AVL樹適合用於插入刪除次數比較少，但查找多的情況。
AVL樹應用場景：
應用相對其他數據結構比較少。windows對進程地址空間的管理用到了AVL樹。
2. 紅黑樹
平衡二叉樹，通過對任何一條從根到葉子的簡單路徑上各個節點的顏色進行約束，確保沒有一條路徑會比其他路徑長2倍，因而是近似平衡的。
紅黑樹特性 ：
- 相對於嚴格要求平衡的AVL樹來說，它的旋轉保持平衡次數較少。
- 用於搜索時，插入刪除次數多的情況下我們就用紅黑樹來取代AVL。
紅黑樹應用場景（比較廣泛）：
- 廣泛用在C++的STL中。map和set都是用紅黑樹實現的。
- 著名的linux進程調度Completely Fair Scheduler,用紅黑樹管理進程控制塊。
- epoll在內核中的實現，用紅黑樹管理事件塊
- nginx中，用紅黑樹管理timer等
- Java的TreeMap實現，Java8的HashMap實現；
3. B(+)樹
B樹（Balance tree）和B+樹應用在數據庫索引，可以認為是m叉的多路平衡查找樹。
B樹，B+樹的特性 ：
- 它們特點是一樣的，是多路查找樹，一般用於數據庫中做索引，因為它們分支多層數少，因為磁盤IO是非常耗時的，而像大量數據存儲在磁盤中所以我們要有效的減少磁盤IO次數避免磁盤頻繁的查找。
- B+樹是B樹的變種樹，有n棵子樹的節點中含有n個關鍵字，每個關鍵字不保存數據，只用來索引，數據都保存在葉子節點。是為文件系統而生的。
B+樹（相對於B樹）的優點：
- B+樹相對B樹磁盤讀寫代價更低：因為B+樹非葉子結點只存儲鍵值，單個節點佔空間小，索引塊能夠存儲更多的節點，從磁盤讀索引時所需的索引塊更少，所以索引查找時I/O次數較B-Tree索引少，效率更高。
- 而且，B+Tree在葉子節點存放的記錄以鏈表的形式鏈接，範圍查找或遍歷效率更高。
B(+)樹應用場景：
- Mysql InnoDB用的就是B+Tree索引。
4. Trie樹（字典樹，單詞查找樹）
又名單詞查找樹，一種樹形結構，常用來操作字符串。
Trie樹的特性 ：
- 它是不同字符串的相同前綴只保存一份。相對直接保存字符串肯定是節省空間的，但是它保存大量字符串時會很耗費內存（是內存）。
- 類似的有：前綴樹(prefix tree)，後綴樹(suffix tree)，radix tree(patricia tree, compactprefix tree)，crit-bit tree（解決耗費內存問題），以及前面說的double array trie。
前綴樹&後綴樹的區別
- 前綴樹：字符串快速檢索，字符串排序，最長公共前綴，自動匹配前綴顯示後綴。
- 後綴樹：查找字符串s1在s2中，字符串s1在s2中出現的次數，字符串s1,s2最長公共部分，最長迴文串。
Trie樹應用場景：
trie 樹的一個典型應用是前綴匹配，比如下面這個很常見的場景，在我們輸入時，搜索引擎會給予提示。
分享到:
閱讀更多 架構師訓練營 的文章
