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

平衡樹：對(duì)一棵查找樹（search tree）進(jìn)行查詢/新增/刪除 等動(dòng)作, 所花的時(shí)間與樹的高度h 成比例, 并不與樹的容量 n 成比例。如果可以讓樹維持矮矮胖胖的好身材, 也就是讓h維持在O(lg n)左右, 完成上述工作就很省時(shí)間。能夠一直維持好身材, 不因新增刪除而長(zhǎng)歪的搜尋樹, 叫做balanced search tree（平衡樹）。（摘自百度百科《平衡樹》）

AVL樹：在計(jì)算機(jī)科學(xué)中，AVL樹是最先發(fā)明的自平衡二叉查找樹。在AVL樹中任何節(jié)點(diǎn)的兩個(gè)子樹的高度最大差別為1，所以它也被稱為高度平衡樹。AVL樹在節(jié)點(diǎn)增刪后不再滿足AVL樹條件時(shí)，需要“旋轉(zhuǎn)”以重新構(gòu)造自身。具體可參看 徹底搞懂AVL樹 。

紅黑樹：RB樹。每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹，可看作2-3樹的一種表現(xiàn)形式。在二叉查找樹強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹我們?cè)黾恿巳缦碌念~外要求:

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

下圖就是一棵紅黑樹：

AVL是嚴(yán)格平衡樹，因此在增加或者刪除節(jié)點(diǎn)的時(shí)候，根據(jù)不同情況，旋轉(zhuǎn)的次數(shù)比紅黑樹要多；
紅黑是弱平衡的，用非嚴(yán)格的平衡來(lái)?yè)Q取增刪節(jié)點(diǎn)時(shí)候旋轉(zhuǎn)次數(shù)的降低；
所以簡(jiǎn)單說(shuō)，搜索的次數(shù)遠(yuǎn)遠(yuǎn)大于插入和刪除，那么選擇AVL樹，如果搜索，插入刪除次數(shù)幾乎差不多，應(yīng)該選擇RB樹。

可以看到，這三者查找的時(shí)間復(fù)雜度O(log2N)與樹的深度相關(guān)，那么降低樹的深度自然會(huì)提高查找效率 。

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

B+-tree：B+的搜索與B-樹也基本相同，區(qū)別是B+樹所有關(guān)鍵字都在葉子結(jié)點(diǎn)出現(xiàn)，因此只有達(dá)到葉子結(jié)點(diǎn)才命中（B-樹可以在非葉子結(jié)點(diǎn)命中）。B+樹葉子節(jié)點(diǎn)鏈表中的關(guān)鍵字是有序的，且所有葉子結(jié)點(diǎn)都有一個(gè)鏈指針指向下一個(gè)葉子節(jié)點(diǎn)，這個(gè)特性使得B+樹對(duì)范圍查找的效率比B樹高的多，比如對(duì)已經(jīng)建立索引的數(shù)據(jù)庫(kù)記錄，查找10<=id<=20，那么只要通過(guò)根節(jié)點(diǎn)搜索到id=10的葉節(jié)點(diǎn)，之后只要根據(jù)葉節(jié)點(diǎn)的鏈表找到第一個(gè)大于20的就行了，比B-樹在查找10到20內(nèi)的每一個(gè)時(shí)每次都從根節(jié)點(diǎn)出發(fā)查找提高了不少效率。

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

在當(dāng)前數(shù)據(jù)庫(kù)和文件系統(tǒng)的實(shí)現(xiàn)上，B系列樹與磁盤運(yùn)作方式密切相關(guān)，涉及到節(jié)點(diǎn)與邏輯頁(yè)的關(guān)系及其它概念。

2-3樹、紅黑樹、B樹的具體介紹可參看 淺談算法和數(shù)據(jù)結(jié)構(gòu): 九 平衡查找樹之紅黑樹 所在系列博文。

Huffman tree：又稱最優(yōu)樹。對(duì)應(yīng)的有哈夫曼編碼，其主要應(yīng)用在數(shù)據(jù)壓縮，加密解密等場(chǎng)合。

上述只是常見(jiàn)但很小一部分樹，最后附圖一幅：

參考資料：

數(shù)據(jù)結(jié)構(gòu)中常見(jiàn)的樹（BST二叉搜索樹、AVL平衡二叉樹、RBT紅黑樹、B-樹、B+樹、B*樹）

B樹、B+樹與B*樹簡(jiǎn)介

ZIP壓縮算法詳細(xì)分析及解壓實(shí)例解釋

跳表SkipList的原理和實(shí)現(xiàn)