樹是數(shù)據(jù)結(jié)構(gòu)里面一個(gè)很重要的內(nèi)容灭将，它的有向無環(huán)圖的結(jié)構(gòu)疼鸟，很適合用來做數(shù)據(jù)排列及檢索，很多數(shù)據(jù)庫的存儲(chǔ)庙曙，都是使用的樹這種數(shù)據(jù)結(jié)構(gòu)來做存儲(chǔ)的空镜。
下面讓我們梳理下樹的幾種分類。鑒于有太多關(guān)于樹的定義文章，本文不會(huì)對每種樹給出定義及詳細(xì)說明吴攒，只會(huì)梳理總結(jié)张抄，關(guān)于各類樹的定義，可參考其他文獻(xiàn)的定義舶斧。
普通二叉樹
樹本身是沒有節(jié)點(diǎn)數(shù)限制的欣鳖，而二叉樹顧名思義察皇，就是每個(gè)節(jié)點(diǎn)最多只有2個(gè)子節(jié)點(diǎn)的樹茴厉，除此之外，沒有其他的限制什荣。
滿二叉樹跟完全二叉樹
在二叉樹的基礎(chǔ)上矾缓，滿二叉樹要求樹的每個(gè)層級高度完全相同，且除了葉子節(jié)點(diǎn)稻爬，樹上其他每個(gè)節(jié)點(diǎn)都必須有2個(gè)子節(jié)點(diǎn)嗜闻。
跟滿二叉樹不同，完全二叉樹在最下層的葉子節(jié)點(diǎn)層可以不滿桅锄，但必須是從左到右依次填充葉子節(jié)點(diǎn)琉雳，不能跳過。
完全二叉樹的創(chuàng)建思路完全按照廣度優(yōu)先遍歷的方式友瘤，從根節(jié)點(diǎn)開始依次創(chuàng)建左右兩個(gè)節(jié)點(diǎn)翠肘，然后把它的左右節(jié)點(diǎn)依次放到隊(duì)列中，之后每次從隊(duì)列中拿出一個(gè)元素辫秧，創(chuàng)建左右節(jié)點(diǎn)束倍，并同時(shí)放入隊(duì)列，如此反復(fù)盟戏。
二叉查找樹（BST樹）
二叉查找樹是一種搜索樹绪妹，在普通二叉樹的基礎(chǔ)上，增加了數(shù)據(jù)比對的過程柿究，從根節(jié)點(diǎn)開始往下比對邮旷，比當(dāng)前節(jié)點(diǎn)數(shù)據(jù)小的，放左邊蝇摸，大的放右邊婶肩。
一般來說，二叉查找樹的查找時(shí)間復(fù)雜度是O(Log2 n)探入，但是在極端情況下狡孔，數(shù)據(jù)會(huì)倒向一側(cè)，導(dǎo)致查找的性能極差蜂嗽，變成遍歷查找苗膝，也就是O(n)。
平衡二叉樹（AVL樹）
平衡二叉樹在二叉查找樹的基礎(chǔ)上添加了數(shù)據(jù)的平衡過程植旧，它要求每一個(gè)節(jié)點(diǎn)辱揭，它的左子樹跟右字?jǐn)?shù)的高度差最多為1層离唐，當(dāng)節(jié)點(diǎn)的變化不符合這個(gè)條件時(shí)，需要通過從本節(jié)點(diǎn)開始问窃，對樹進(jìn)行左旋或者右旋調(diào)整亥鬓，然后逐層往上遞歸，判斷其父節(jié)點(diǎn)是否需要左旋或者右旋域庇，直到整棵平衡二叉樹重新恢復(fù)平衡嵌戈。
基于上述過程，二叉查找樹存在的問題通過構(gòu)建平衡二叉樹能夠得以解決听皿。
平衡二叉樹在增刪改的過程中增加了一些平衡的消耗熟呛，從而達(dá)到樹的穩(wěn)定結(jié)構(gòu)鱼鼓，這對于以增刪改為主的業(yè)務(wù)場景而言是不合適的网持，更適合讀多寫少的場景千劈。
紅黑樹
前面幾種樹課本上基本都深入學(xué)習(xí)過睹逃，但是紅黑樹可能大部分人都聽過拇囊，但是卻沒有深入去學(xué)習(xí)了解校摩。
紅黑樹的性質(zhì)：
1冗荸、節(jié)點(diǎn)是紅色或黑色父阻。
2覆致、根節(jié)點(diǎn)是黑色侄旬。
3、每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色篷朵。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn))
4勾怒、從任一節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。
紅黑樹的算法過程跟平衡二叉樹類似声旺，也是先在對應(yīng)的子節(jié)點(diǎn)插入黑色節(jié)點(diǎn)數(shù)據(jù)笔链，然后逐層往上遞歸判斷是否符合紅黑樹的性質(zhì)，不符合就左旋或者右旋腮猖，但由于它跟平衡二叉樹相比：
- 1鉴扫、紅黑樹沒有那樣嚴(yán)格要求各個(gè)節(jié)點(diǎn)的高度差在1度以內(nèi)，因此它重新旋轉(zhuǎn)平衡過程的性能代價(jià)比平衡二叉樹小澈缺，紅黑樹插入過程最多需要重新平衡旋轉(zhuǎn)3次坪创，而平衡二叉樹不一定。
- 2姐赡、紅黑樹的高度也可能平衡二叉樹更高莱预。但這是可以接受的一種折中方案，畢竟相比極端的二叉查找樹项滑，紅黑樹的穩(wěn)定性還是非常高的依沮，也是 O(Log2 n)。
鑒于平衡二叉樹的要求嚴(yán)格，因此紅黑樹實(shí)際上應(yīng)用場景是遠(yuǎn)廣于平衡二叉樹的危喉。而由于這兩種樹的旋轉(zhuǎn)需求宋渔，因此它們更適合在內(nèi)存的場景使用，比如java的TreeMap辜限。
平衡二叉樹跟紅黑樹的算法時(shí)間復(fù)雜度都是O(Log2 n)皇拣。
哈夫曼樹
哈夫曼樹是一種帶權(quán)重的，路徑長度最短的最優(yōu)二叉樹薄嫡。
哈夫曼樹的定義是：
假設(shè)有n個(gè)權(quán)值氧急，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。 n個(gè)權(quán)值分別設(shè)為 w1岂座、w2态蒂、…、wn费什，則哈夫曼樹的構(gòu)造規(guī)則為：
(1) 將w1、w2手素、…鸳址，wn看成是有n 棵樹的森林(每棵樹僅有一個(gè)結(jié)點(diǎn))；
(2) 在森林中選出兩個(gè)根結(jié)點(diǎn)的權(quán)值最小的樹合并泉懦，作為一棵新樹的左稿黍、右子樹，且新樹的根結(jié)點(diǎn)權(quán)值為其左崩哩、右子樹根結(jié)點(diǎn)權(quán)值之和巡球；
(3) 從森林中刪除選取的兩棵樹，并將新樹加入森林邓嘹；
(4) 重復(fù)(2)酣栈、(3)步，直到森林中只剩一棵樹為止汹押，該樹即為所求得的哈夫曼樹矿筝。
下面讓我們看一顆哈夫曼樹的構(gòu)成。
對于排序后的集合是：2,5,6,8,13,19,25,36 的內(nèi)容棚贾，每次從集合中取出最小的兩個(gè)數(shù)窖维，從葉子節(jié)點(diǎn)開始構(gòu)建，組成一個(gè)包含兩個(gè)節(jié)點(diǎn)以及父節(jié)點(diǎn)的樹（父節(jié)點(diǎn)的值是兩個(gè)數(shù)的相加和）妙痹，再把父節(jié)點(diǎn)放入集合中铸史，重新執(zhí)行構(gòu)建過程，整個(gè)過程集合的變化情況是：
2,5,6,8,13,19,25,36 ->
7(2+5),6,8,13,19,25,36 ->
8,13(6+7),13,19,25,36 ->
13,19,21(8+13),25,36 ->
下一輪的時(shí)候怯伊，由于拿出來的13跟19都小于21琳轿，因此無法加入21所在的樹因此結(jié)果是：
21(8+13),25,32(13+19),36 ->
32(13+19),36,46(21+25) ->
46(21+25),32(32+36) ->
114
最終結(jié)果是：
哈夫曼編碼
哈夫曼樹對數(shù)據(jù)集進(jìn)行編碼的結(jié)果叫做哈夫曼編碼。由于哈夫曼樹帶權(quán)路徑最短的特點(diǎn)，哈夫曼編碼的特點(diǎn)也是對數(shù)據(jù)重新編排利赋，使得整個(gè)用哈夫曼編碼組成的內(nèi)容最短水评。
對上述結(jié)果進(jìn)行哈夫曼編碼的話，是這樣的一個(gè)過程：
從而得出最終編碼結(jié)果媚送，各葉子節(jié)點(diǎn)從左到右分別是：
8 ：000
6：0010
2 ：00110
5：00111
25：01
13：100
19：101
36：11
總結(jié)
本文介紹了二叉樹的幾種常見的類型中燥，包括普通二叉樹、滿二叉樹塘偎、完全二叉樹疗涉、二叉查找樹、平衡二叉樹吟秩、紅黑樹及哈夫曼樹咱扣。
其中：
- 普通二叉樹、滿二叉樹涵防、完全二叉樹是帶有一定基本限制條件的二叉樹闹伪，更多作為定義存在，實(shí)際上直接使用這些樹的應(yīng)用場景較少壮池。
- 二叉查找樹是一種最簡單的能用于索引的樹結(jié)構(gòu)偏瓤，但是性能不穩(wěn)定。
- 平衡二叉樹跟紅黑樹是為了讓二叉查找樹的性能穩(wěn)定而設(shè)計(jì)的樹椰憋，其中厅克，平衡二叉樹限制較多，而紅黑樹在其基礎(chǔ)上做了靈活的變通橙依，使其旋轉(zhuǎn)的代價(jià)較小证舟，同時(shí)性能又比較穩(wěn)定，在工程實(shí)踐中更加適合窗骑。
- 哈夫曼樹是一種加權(quán)的二叉查找樹女责，它的生成特點(diǎn)使其非常適合于對內(nèi)容作編碼優(yōu)化。
