1.6 樹

樹是一種由有限節點組成的具有層次關系的集合，把它叫作樹是因為它看起來像一棵倒掛的樹，也就是說它是根朝上，葉朝下。每個節點有零個或多個子節點，沒有父節點的節點稱為根節點，除了根節點以外，每個節點都有且僅有一個父節點，并且樹里面沒有環路?？占弦彩菢?，稱為空樹，空樹中沒有節點。

1. 樹的常見術語

父節點：若一個節點含有子節點，則這個節點稱為其子節點的父節點。

子節點：一個節點含有的子樹的根節點稱為該節點的子節點。

葉子節點：沒有子節點的節點稱為葉子節點。

兄弟節點：具有相同父節點的節點互稱為兄弟節點。

節點的度：一個節點含有的子節點的個數稱為該節點的度。

樹的度：一棵樹中，最大節點的度稱為樹的度。

節點的層次：根節點的層次為1，其他節點的層次等于它父節點的層次數加1。

節點的深度：根節點的深度為0，其他節點的深度等于它父節點的深度數加1。

樹的深度：距離根節點最遠的節點的深度即為樹的深度。

節點的高度：所有葉子節點的高度為0，其他節點的高度等于它所有子節點中的最大高度加1。

樹的高度：從根節點到達一個葉子節點的最長路徑長度。

堂兄弟節點：父節點在同一層的節點互為堂兄弟節點。

節點的祖先：從根節點到該節點這條分支上的所有節點。

子孫：以某節點為根的子樹中任一節點都稱為該節點的子孫。

森林：指若干棵互不相交的樹的集合。

樹的種類比較多，我們只介紹一些常見的樹，這里先簡單介紹3種，還有一些會在后面詳細介紹。

二叉樹：每個節點最多含有兩個子樹的樹稱為二叉樹。

完全二叉樹：對于一棵二叉樹，除了最下面一層外，其他各層的節點數目均已達最大值，且最后一層的所有節點從左向右連續地緊密排列，這樣的二叉樹被稱為完全二叉樹。

滿二叉樹：所有葉節點都在同一層的完全二叉樹稱為滿二叉樹，如圖1-24所示，中間的二叉樹，雖然上面各層的節點數目都已達到最大值，但最后一層的節點不是從左往右緊密排列的，所以它不是完全二叉樹。

2. 完全二叉樹的特性

?第i層上的節點數目最多為2^(i-1)。

?度為1的節點僅有1個或0個（葉子節點盡可能往左排）。

?葉子節點的個數=(n+1)/2 (n是二叉樹所有節點的數量)。

如果我們讓完全二叉樹的根節點編號為0，把其他節點從上到下、從左到右逐個編上號，會有下面的對應關系。

3. 滿二叉樹的特性

?共有（2^k）-1個節點（k是總的層數）。

?節點個數一定是奇數。

?第i層有2^(i-1)個節點。

?有(n+1)/2個葉子節點（n是總的節點數量）。

?葉子節點的度都為0，非葉子節點的度都是2，沒有度為1的節點。

1.6.1 二叉搜索樹

二叉搜索樹（Binary Search Tree）也叫作二叉查找樹，它是具有下列性質的一種二叉樹。

?若左子樹不空，則左子樹上所有節點的值都小于根節點的值；

?若右子樹不空，則右子樹上所有節點的值都大于根節點的值；

?任意節點的子樹也都是二叉搜索樹。

二叉搜索樹有一個重要的特性就是它的中序遍歷結果一定是有序的。如圖1-25所示，二叉搜索樹的中序遍歷結果是[1,3,4,6,8,9]。

1. 二叉搜索樹的查找

二叉搜索樹的查找可以通過遞歸的方式，也可以通過while循環的方式，原理都一樣，如圖1-26所示，步驟如下：

?如果當前節點為空，則搜索失敗。

?如果當前節點的值等于要查找的值，則直接返回。

?如果要查找的值比當前節點小，就往當前節點的左子樹找。如果要查找的值比當前節點值大，就往當前節點的右子樹找。

2. 二叉搜索樹的插入

二叉搜索樹插入的時候首先要找到它需要插入的位置，然后插入，如圖1-27所示，步驟如下：

?如果當前節點為空，則直接創建一個新的節點返回。

?如果要插入的值比當前節點小，就往當前節點的左子樹查找插入的位置。

?如果要插入的值比當前節點大，就往當前節點的右子樹查找插入的位置。

以上使用的是遞歸的方式，遞歸將在第5章介紹。如果看不明白，還可以使用非遞歸方式。

3. 二叉搜索樹的刪除

二叉搜索樹的刪除相對來說要麻煩一些，如果刪除的是葉子節點還好，可以直接刪除。如果刪除的節點只有一個子節點，可以讓這個僅有的子節點替代它。如果刪除的節點有兩個子節點，我們就需要考慮刪除當前節點后，子節點該怎樣存放。在講解二叉搜索樹的刪除之前，先來了解一下二叉樹的前驅節點和后繼節點。

前驅節點：對一棵二叉樹進行中序遍歷，遍歷后的結果中，當前節點的前一個節點為該節點的前驅節點。

后繼節點：對一棵二叉樹進行中序遍歷，遍歷后的結果中，當前節點的后一個節點為該節點的后繼節點。

如圖1-28所示，二叉樹中節點4的前驅節點是3，后繼節點是5。假設要刪除節點4，有兩種方式。一種方式是讓待刪除節點的右子節點成為它前驅節點的右子節點，這樣待刪除的節點就只有一個子節點了，如圖1-29所示。

還有一種方式是讓待刪除節點的左子節點成為它后繼節點的左子節點，如圖1-30所示。

這里的關鍵是怎樣查找一個節點的前驅節點和后繼節點，有的讀者認為通過打印二叉樹的中序遍歷結果即可找到，但實際上不需要那么麻煩。一個節點的前驅節點是其左子樹中的最大節點，那么這個節點就是其左子樹往右一直走下去的節點。同理，一個節點的后繼節點就是其右子樹的最小節點，這個節點就是其右子樹往左一直走下去的節點。

找到要刪除節點的前驅節點或者后繼節點，就可以將其刪除了，刪除的步驟如下，假設刪除的節點是p：

?如果p是葉子節點，則直接刪除。

?如果p不是葉子節點，并且p僅有一個子節點，只需要讓p的父節點變成p的子節點的父節點即可，也可以理解為讓p的子節點替換p的位置。

?如果p有兩個子節點，就像上面講的，有兩種方式。一種方式是讓p的右子節點成為它前驅節點的右子節點。還有一種方式是讓p的左子節點成為它后繼節點的左子節點，兩種方式可以隨便選一個。

注意：刪除節點一般有兩種實現方式，一種就是上面講的，但這種方式有個缺點，就是會嚴重破壞樹的平衡性。還有一種方式就是移形換位，不把待刪除的節點刪除，而是用它的前驅或者后繼節點的值來替換它，然后把這個前驅或后繼節點刪除，后面講AVL樹和紅黑樹的時候會用這種方式。

1.6.2 AVL樹

對于有n個元素的二叉搜索樹，它的平均查找時間復雜度是O(logn)，但如果創建二叉搜索樹的時候插入的是一組升序或者降序的數值，就會導致二叉搜索樹始終偏向一方，變成類似鏈表的形狀，查找時間復雜度變成了O(n)，如圖1-31所示。

有沒有一種方式不讓它變成這種形狀呢？實際上是有的，這就是本節要講的AVL樹（Adelson-Velsky and Landis Tree），AVL樹得名于它的發明者G.M.Adelson-Velsky和Evgenii Landis。在AVL樹中，任何節點的兩個子樹高度差小于等于1，所以它也被稱為高度平衡樹，增加和刪除操作需要通過一次或多次旋轉來重新平衡這棵樹，我們先來看一下AVL樹的節點類。

為了方便計算，我們在節點類中添加一個變量height，它表示當前節點的高度，默認葉子節點高度為1。如果沒有這個變量，每次獲取節點高度的時候，都需要重新計算一遍，增加了時間復雜度，而有了這個變量以后，每次使用的時候直接從節點中取即可。

在AVL樹中，每個節點左子樹與右子樹的高度差稱為節點的平衡因子，任一節點的平衡因子只能是-1、0和1，如果一個節點的平衡因子絕對值大于1，表示這棵二叉搜索樹失去了平衡，不再是AVL樹。

1. AVL樹的插入

AVL其實就是一棵二叉搜索樹，它的查找和前面講的二叉搜索樹的查找是一樣的，查找操作就不介紹了，來看一下它的插入操作。AVL樹的插入操作和二叉搜索樹的插入操作類似，也是先找到待插入的位置，然后插入，因為AVL樹是高度平衡的二叉搜索樹，所以插入之后還需要進行調整，防止出現偏向一邊的情況。

AVL樹插入的時候為了保證樹的平衡，會進行旋轉，所以根節點不是固定的，每次插入的時候都需要更新根節點，所以插入的核心代碼是add函數，我們看到它使用的是遞歸的實現方式，遞歸在這里非常重要，它最后一行的balanceTree函數是對樹進行調整，也就是說它是自下往上一直到根節點，只要遇到不平衡的節點都會調整，我們暫時還沒講到遞歸，如果看不懂也沒關系，只需要知道有這個過程就行。AVL樹的節點在插入的時候會有4種情況，我們來分別看一下（小括號內數字表示左右子節點的高度差）。

情況一：LL類型

這種情況直接對不平衡的節點右旋即可，如圖1-32所示。

情況二：LR類型

這種情況需要對不平衡節點的左子節點左旋，然后就會變成LL類型，接著對不平衡節點右旋，如圖1-33所示。

情況三：RR類型

這種情況直接對不平衡節點左旋，如圖1-34所示。

情況四：RL類型

這種情況需要對不平衡節點的右子節點右旋，然后就會變成RR類型，接著對不平衡節點左旋，如圖1-35所示。

我們來整理一下：

到底是哪種類型，只需要計算每個節點的左右子樹高度差即可判斷，如果當前節點的左子樹高度與右子樹高度的差超過1，基本上可以判定是L（?）類型，那么？究竟是L還是R，還需要繼續判斷，判斷方式直接看一下代碼即可。

無論是左旋還是右旋，都會導致不平衡節點的高度發生改變，所以旋轉之后還需要更新不平衡節點的高度，我們來看一下其他函數的代碼。

再來看一下節點的左旋和右旋，先來看一下左旋，如圖1-36所示，雖然它已經平衡了，但它并不影響我們對樹旋轉的研究。左旋是逆時針旋轉兩個節點，使不平衡節點被其右子節點取代，而該節點成為其右子節點的左子節點。左旋會導致不平衡節點以及它的右子節點高度發生變化，所以旋轉之后它們的高度需要更新一下。

再來看一下右旋，如圖1-37所示。右旋是順時針旋轉兩個節點，使不平衡節點被其左子節點取代，而該節點成為其左子節點的右子節點。關于左旋和右旋的代碼，大家可以直接通過圖來理解，這里就不再逐步分析。

2. AVL樹的刪除

AVL樹的刪除，如果刪除的是葉子節點或只有一個子節點的節點，則直接刪除，否則使用移形換位法，用它的前驅節點或者后繼節點替換它，然后刪除它的前驅節點或者后繼節點。我們看一下代碼，注意刪除的時候可能會出現不平衡，所以最后還需要進行調整。

我們回過頭來看一下balanceTree這個函數，其中有下面兩行代碼。

旋轉的時候其實就是哪邊低先往哪邊旋轉，但如果兩邊子樹高度都一樣呢？如圖1-38所示。

我們看到節點12出現了不平衡，而節點16的兩個子樹高度都是一樣的，是按照RR處理還是按照RL處理呢？實際上嘗試著旋轉一下就知道，按照RR處理才能保證平衡。有的讀者可能會說這個圖是不可能存在的，因為它早已經出現了不平衡。實際上如果添加節點的時候，這個圖是不會存在的，但刪除的時候就不一定了，比如9還有一個節點，但我們把它刪除了。

1.6.3 紅黑樹

AVL樹是高度平衡的二叉搜索樹，使用它主要是為了方便查找，以及減少查詢次數，但如果添加和刪除的次數比較多的時候，使用它顯然就不合適了，因為它頻繁地旋轉，增加了算法的時間復雜度，這個時候就可以使用另外一種樹——紅黑樹，紅黑樹也會旋轉，但不會像AVL樹那么頻繁。紅黑樹有5個重要的性質。

（1）節點是紅色或黑色。

（2）根節點是黑色。

（3）所有葉子都是黑色（葉子是null節點）。

（4）從根節點到所有的葉子節點的路徑上不能有兩個連續的紅色節點。

（5）從任一節點到其每個葉子的路徑都包含相同數目的黑色節點。

其中如果不理解第3條，基本上是搞不懂紅黑樹的，這里的葉子不是二叉樹中定義的葉子節點，而是一種空的節點，它告訴我們任一節點如果只有一個子節點，那么該節點也是有兩條路徑的，這樣就限制了另一條路徑的長度。其實也在變相告訴我們紅黑樹中如果一個節點只有一個子節點，那么這個子節點必定是葉子節點，并且是紅色的，結合第4和第5條就明白了。

紅黑樹中根到葉子的所有路徑中，最長路徑不會超過最短路徑的兩倍。可以反證一下，假設超過兩倍會怎樣？比如最短路徑長度是a，最長路徑長度是2a+1。根據性質4，路徑上不能有兩個連續的紅色節點，即便最短路徑上全部是黑色節點，那么在最長路徑上也會有a+1個紅色節點，因為根節點是黑色的，也就是說在剩下的a-1個黑色節點之間插入a+1個紅色的節點，并且紅色節點不能有連續的，無論如何也是做不到的，所以最長路徑不可能超過最短路徑的兩倍。

1. 紅黑樹的插入

紅黑樹也是一棵二叉搜索樹，它的查找、插入和刪除可以參照前面講的二叉搜索樹和AVL樹，不過在插入和刪除之后，有可能打破樹的平衡，所以在插入和刪除之后，還需要進行調整，先來看一下紅黑樹插入的調整。

如果插入的是黑色節點，根據紅黑樹的性質5，肯定會破壞這一規則，所以這里插入的節點都是紅色的。但插入紅色節點有可能會破壞性質4，也有可能不會。如果沒有破壞就不需要調整，如果破壞我們再調整。下面來分別討論插入遇到的幾種情況，為了方便描述，把父節點的父節點稱為爺爺節點，和父節點有共同父節點的稱為叔叔節點。插入之后主要涉及涂色和旋轉，這里只討論插入節點的父節點是它爺爺的左子節點的情況，如果是右子節點就不再介紹，因為原理都一樣，只是左旋和右旋的區別。

（1）如果插入的是根節點。

如果插入的是根節點，直接把它涂黑，然后返回即可。

（2）如果插入節點的父節點是黑色。

如果插入節點的父節點是黑色，但插入的節點是紅色，沒有破壞任何一條性質，不需要做任何調整。

（3）如果插入節點的父節點是紅色，叔叔節點也是紅色。

因為插入的節點是紅色，而父節點也是紅色，所以破壞了性質4，需要把父節點涂成黑色。因為父節點之前是紅色的，所以它肯定不是根節點，所以插入的節點肯定有爺爺節點，并且爺爺節點一定是黑色的。把父節點涂成黑色之后，經過父節點的這條路徑就多了一個黑色節點，根據性質5，需要把爺爺節點涂成紅色，但這樣叔叔節點這條路徑上少了一個黑色節點，所以還需要把叔叔節點涂成黑色。如果爺爺節點是根節點，還需要把它涂成黑色（根節點是黑色的），否則爺爺的父節點如果也是紅色，就破壞了性質4，需要繼續往上判斷，如圖1-39所示。

總結：把父節點和叔叔節點涂成黑色，把爺爺節點涂成紅色，繼續往上判斷爺爺節點。

（4）如果插入節點的父節點是紅色，叔叔節點是黑色，當前節點是父節點的左子節點。

這種情況下也是先把父節點涂成黑色，因為父節點變成黑色的之后，經過父節點的這條路徑上多了一個黑色節點，所以還需要把爺爺節點涂成紅色。那么這里有個疑問，叔叔節點該怎樣處理？有的讀者可能會說像前面介紹的情況（如果插入節點的父節點是紅色，叔叔節點也是紅色）那樣把叔叔節點也涂成黑色就可以了。其實這樣是不行的，主要有兩點，第一：如果叔叔節點是空的怎么辦，因為根據性質3，空節點也是黑色的，所以這樣就沒法涂了。第二：如果叔叔節點不是空的，那么它就是從前面介紹的情況（如果插入節點的父節點是紅色，叔叔節點也是紅色）轉換過來的（涂完之后會繼續往上判斷），這種情況下其本來就是黑色的，再把它涂成黑色相當于沒涂。既然不能改變叔叔節點的顏色，那么叔叔節點這條路徑就比父節點這條路徑少了一個黑色節點（因為爺爺節點變紅了，叔叔節點這條路徑就少了一個黑色的），唯一的解決方式就是對爺爺節點進行右旋，讓父節點成為這棵子樹的根節點，那么這個父節點黑色的個數就可以被它的兩棵子樹共享了，如圖1-40所示。

總結：父節點涂黑，爺爺節點涂紅，對爺爺節點右旋，因為父節點已經變黑了，就不再繼續判斷。

（5）如果插入節點的父節點是紅色，叔叔節點是黑色，當前節點是父節點的右子節點。

這種情況下和“如果插入節點的父節點是紅色，叔叔節點是黑色，當前節點是父節點的左子節點”中講的類似，如果對爺爺節點右旋，會導致一條路徑缺少了一個黑色節點，如圖1-41所示。注意這里大家可能會有疑惑，插入的X節點怎么會有子節點？實際上這里的X節點有可能是插入的，也有可能是（如果插入節點的父節點是紅色，叔叔節點也是紅色）往上調整得到的，所以要放在一起看。

很明顯直接對爺爺節點旋轉是不行的，那么該怎么辦呢？其實可以對X的父節點進行左旋，就變成“如果插入節點的父節點是紅色，叔叔節點是黑色，當前節點是父節點的左子節點”中介紹的那樣了，后面按照“如果插入節點的父節點是紅色，叔叔節點是黑色，當前節點是父節點的左子節點”中的那樣處理即可，如圖1-42所示。

總結：讓X節點指向父節點，對X節點左旋，后面參照“如果插入節點的父節點是紅色，叔叔節點是黑色，當前節點是父節點的左子節點”。

（6）如果插入節點的父節點是紅色，父節點是爺爺節點的右子節點。

這里也分幾種情況，和上面類似，只不過是左旋和右旋的區別，這里就不再介紹。最后來看一下代碼。

2. 紅黑樹的刪除

刪除操作可以參考AVL樹的刪除，我們也可以看一下，這是紅黑樹TreeMap中的源碼。

如果p有兩個子節點，刪除的時候不是直接刪除p節點，而是用p的后繼節點來替換p節點，然后刪除p的后繼節點。所以刪除的節點要么是葉子節點，要么只有一個子節點，不可能有兩個子節點。我們看到上面的代碼中，如果p（這里的p已經被替換了）是葉子節點，并且是黑色，則先調整p節點，然后刪除，如果不是葉子節點，則先刪除p節點，然后調整replacement，為什么不是調整完之后再刪除呢？這是因為刪除調整的節點必須是黑色的，如果p不是葉子節點，它就只能有一個子節點replacement，根據紅黑樹性質，這個子節點必定是紅色的，如果先把p節點刪除，調整replacement節點的時候，直接把它變成黑色，不需要做任何其他變色和旋轉操作，簡單省事。

fixAfterDeletion函數到底是調整p節點還是調整p的子節點，我們不需要管，只需要記住在調整的這個節點的路徑上少了一個黑色節點即可，大家可以自己看，這里就不逐步分析了。

1.6.4 字典樹

字典樹又稱為Trie樹、單詞查找樹、前綴樹，也是一種樹狀結構，它主要利用字符串的公共前綴來減少查詢次數，最大限度地減少字符串比較，比如要查找一個字符串是否存在，或者是否存在×××開頭的字符串。假設字符串只包含小寫字母，那么可以把字典樹看作是一棵（每個節點最多有26個子節點的）樹。字典樹中的根節點是不存儲數據的，除了根節點以外，每個節點代表一個字符，從根節點到某一節點，將路徑上經過的字符連接起來，為該節點對應的字符串。比如有wang、yi、bo、yibo等字符串，只需要把它添加到字典樹中，然后在每個字符串末尾標記為一個完整的字符串即可，如圖1-43所示。

比如查找wan，因為字母n在字典樹中沒有標記，所以wan不是一個完整的字符串。在字典樹中每個節點只需要兩個變量，一個是記錄子節點的數組，另一個是標記從根節點到當前節點為止，是否是一個完整的字符串。

這里我們規定只查詢小寫字母，當然如果包含其他字母，可以使用Map。

字典樹的常見操作包括插入和查詢，一般查詢是否是一個完整的字符串，或者查詢是否有某個字符串的前綴，或者查詢字符串的數量，或者查詢某個字符串前綴的數量，但也有刪除，刪除比較少見。這里不講那么復雜，只講簡單的插入、字符串查詢和前綴查詢。對于其他的操作，還需要在每個節點添加一個變量，計算當前節點出現的次數即可。對于刪除來說，必須先判斷要刪除的字符串存在，才能執行刪除操作。

1. 字典樹的插入

先來看一下字典樹的插入，它的原理就是沿著一條路徑往下插入字符，如果路徑上對應的節點存在，就繼續往下判斷下一個字符，如果不存在，就創建對應的節點，當字符串插入完之后，把它標記為完整的字符串，也就是說，從根節點到我們標記的那個字符連接起來就是一個完整的字符串，如圖1-44所示。

2. 字典樹的查詢

這里有兩種查詢，一種是查詢前綴是否存在，另一種是查詢字符串是否存在，原理比較簡單，我們直接看一下代碼。

1.6.5 哈夫曼樹

哈夫曼樹（Huffman Tree），也叫作霍夫曼樹，或者赫夫曼樹，又稱為最優樹，學習哈夫曼樹之前，先了解幾個概念。

路徑：從任一個節點往下到達其他節點之間的通路。

路徑長度：路徑中線段的個數。

節點的權：節點的值。

節點的帶權路徑長度：從根節點到該節點之間的路徑長度與該節點的權的乘積。

樹的帶權路徑長度：所有葉子節點的帶權路徑長度之和。

在講解哈夫曼樹之前，來看這樣一個問題，我們都知道現在有個詞叫作大數據殺熟，也就是說用戶在某一個平臺消費越多，折扣就越少，消費越少折扣越多，而平臺根據消費情況，把用戶分成5個等級，等級從高到低分別為：貴賓卡＞豪卡＞金卡＞銀卡＞銅卡。也就是說用戶消費越低等級就越高，優惠力度就越大。

每次消費的時候，平臺會根據用戶以往的消費金額來判斷是什么級別的用戶，然后給用戶什么樣的優惠額度，如圖1-45所示，每次都這樣查詢。后來平臺發現用戶的消費金額小于1000的只有1%，如果每次先判斷是否小于1000，很明顯大多數情況下是無效的。為了減少判斷次數，最有效的查詢方式就是用戶最多的離根節點越近。假設消費金額在5000～20000的有40%，消費金額在20000～50000的有45%，這兩類用戶占85%了，這種情況下可以像圖1-46中這樣查詢。

這里的百分比就相當于葉子節點的權值，假設用它構造一棵二叉樹，這棵二叉樹可以有多種，其中帶權路徑長度最小的就是最優樹，也就是哈夫曼樹。哈夫曼樹就是給定n個權值作為葉子節點，構造一棵二叉樹，使該樹的帶權路徑長度達到最小。樹的帶權路徑長度WPL(Weighted Path Length of Tree)可以記為WPL=(W1?L1+W2?L2+W3?L3+…+Wn?Ln)，其中W？表示節點的權值，L？表示從根節點到該節點的路徑長度。要想讓WP L最小，權值最大的節點要離根節點最近。如圖1-47所示，圖中展示的是用權值9，3，2，8構造的兩棵樹。

1. 哈夫曼樹的構造

哈夫曼樹的構造原則是權值越大離根節點越近，權值越小離根節點越遠。哈夫曼樹的構造使用的是貪心算法，如圖1-48所示，它的步驟如下：

（1）用給定的n個權值創建n棵只有一個節點的樹，把它們添加到集合S中。

（2）每次從集合S中取出兩棵權值最小的子樹，組成一棵新的二叉樹，該樹的權值為它的兩個子樹的權值之和，然后把這棵樹添加到集合S中。

（3）重復步驟（2），直到集合中只有一棵樹為止，這棵樹就是哈夫曼樹。

因為每次都是選擇兩棵子樹合并成一棵，所以哈夫曼樹只有度為0和2的節點，沒有度為1的節點，也就是說哈夫曼樹中每個節點要么沒有子節點，要么有兩個子節點，不可能只有一個子節點。一棵有n個葉子節點的哈夫曼樹總共有2?n-1個節點。每次從集合中取出權值最小的兩棵樹，可以使用最小堆，來看一下代碼。

2. 哈夫曼編碼

哈夫曼樹的最大用處就是哈夫曼編碼，它是一種用于無損數據壓縮的權編碼算法。比起定長的ASCII編碼來說，哈夫曼編碼能節省很多空間，尤其是對于重復率比較高的字符數據。比如一個字符串有67個字母，其中有50個字母a，2個字母b，5個字母c，10個字母d。如果使用定長的比特來表示它們，那么每個字母至少需要2個比特，總共需要67?2=134個比特。

來看一下使用哈夫曼編碼需要多少比特?？粗靶枰獦嫿ü蚵鼧洌總€字母的個數相當于該字母的權值，如圖1-49所示，構建之后規定哈夫曼樹中左分支為0，右分支為1，從根節點到每個葉節點路徑上由0和1組成的序列，就是該葉子節點對應字符的編碼。比如a是根節點的右分支，所以它是1，c從根節點往下是左左右，所以是001，可以這樣表示。

通過計算發現它們需要的比特是91，比定長的比特134少，節省了不少空間。值得一提的是，在一個哈夫曼樹編碼中，不會出現某個編碼是另一個編碼的前綴。什么意思呢？比如選擇001表示a，00表示b，1表示3，當出現001的時候它是表示a還是表示bc？我們沒法確定，但哈夫曼編碼不會出現這種情況，因為在哈夫曼樹中，每個字母對應的節點都是葉子節點，而它們對應的二進制碼是由根節點到各自節點的路徑所決定的，正因為它們都是葉子節點，所以每個節點的路徑不可能是其他節點路徑的前綴。來看一下哈夫曼樹的節點類。

來看一下哈夫曼樹的創建，和前面講的類似，只不過這里多了統計字符串頻率的步驟。

接著來看哈夫曼樹的編碼和解碼。

關于哈夫曼樹的解碼筆者列出了兩種方式，大家選擇其中的一種即可，我們來測試一下。

看一下運行結果：

1.6.6 線段樹

假設需要頻繁求數組的區間和，可能會想到樹狀數組，或者是前綴和，如果是求區間的最大值或者區間最小值呢？很明顯，使用樹狀數組或者前綴和是無能為力了，但可以使用另外一種數據結構——線段樹。

線段樹是一棵平衡的二叉搜索樹，它將每個長度大于1的區間劃分為左右兩個區間遞歸求解。如果整個區間的長度為n，則線段樹有n個葉子節點，每個葉子節點代表一個單位區間，每個內部節點可以直接獲取區間的值（最大值、最小值、區間和等）。線段樹是建立在線段的基礎上，每個節點都代表了一條線段[a,b]，在葉子節點中a==b，對于非葉子節點，它的左子節點區間為[a,(a+b)/2]，右子節點區間為[(a+b)/2+1,b]。在前面講樹狀數組的時候，提到了樹狀數組可以進行區間的修改及查詢，但樹狀數組主要用于區間的求和，功能比較單一，而線段樹不但能用于區間的求和，還能用于區間求最大值、最小值、最大公約數等。

能用于線段樹的兩個子節點的結果必須能合并，比如求和以及求最大值等，區間和=左子節點和+右子節點和，區間最大值=max(左子節點的最大值，右子節點的最大值)。如果不能合并，是沒法使用線段樹的，比如求眾數，左子節點的眾數和右子節點的眾數可能不是一個，沒法合并。這里以求“區間和”為例來介紹線段樹，求區間的最大值和最小值原理基本一樣，這里不再介紹。假設有一個長度為10的數組[1,2,3,4,5,6,7,8,9,10]，通過它來構建線段樹，如圖1-50所示。

我們看到葉子節點存儲的是原數組中的值，非葉子節點存儲的是區間的和。在線段樹中，如果父節點的下標是i，它的左右兩個子節點的下標分別為i?2+1和i?2+2。線段樹中有兩個數組，一個是原數組，一個是線段樹數組。

1. 構建線段樹

線段樹是一棵平衡的二叉搜索樹，構建的時候可以使用遞歸的方式。

2. 單點查詢

單點查詢是從線段樹的根節點開始往下查詢，直到葉子節點，最后葉子節點的值就是我們要查找的結果。

3. 單點修改

單點修改和單點查詢類似，它是先找到葉子節點，然后進行修改，修改完之后，父節點的值也會發生變動，所以還需要往上推，更改父節點的值，一直到根節點，如圖1-51所示。

我們看到子節點的值改了，父節點的值也要跟著改變。

4. 區間查詢

區間查詢會有下面4種情況。如果查找區間非常大，包含了節點區間，直接返回當前節點值即可。如果查找區間只在左子樹，就在左子樹查找；如果查找區間只在右子樹，就在右子樹查找，否則左右兩棵子樹都要查，如圖1-52所示。

假設查找[2,5]區間的和，查找步驟如圖1-53所示。

5. 區間修改

區間修改可以參考單點修改，一直往下找到葉子節點，把它的值修改一下，然后還要一直往上修改父節點值。區間修改不同于單點修改的地方在于（區間修改）可能兩個子節點都要修改，就像區間查詢一樣。

6. 懶標記

我們看到區間修改的時候，會把每一個葉子節點都進行修改，然后往上更新父節點，但實際上可以不這樣做，如果某棵子樹的值全部要修改，只需要更改這棵子樹的根節點即可，給它加個標記，然后這棵子樹的子節點都不需要修改了。就像過年別人給你壓歲錢一樣，這筆錢不是直接給你，而是先給你的家長，然后你的家長再給你。由于給的人太多（類似于區間的頻繁修改），你的家長說這筆錢就不逐一發給你們了，放我這保管，需要的時候再給你們。

假設需要給區間[3,9]中的所有元素加上10，當我們找到需要更新的節點區間[3,4]和[5,9]的時候，只需要修改它們的值就可以了，然后給它加個懶標記值，它們的子節點就不再修改了，但它們的父節點還是要更新，如圖1-54所示。

假如需要查詢區間[3,7]，首先它會在[0,4]和[5,9]兩個子節點中查找，節點[0,4]又會在節點[3,4]查找，而[3,7]區間包含[3,4]區間，可以直接返回區間[3,4]的值。而[3,7]區間不全部包含[5,9]區間，所以會到節點[5,9]的子節點去找，因為節點[5,9]有懶標記，所以在到子節點查找之前，懶標記必須下發到子節點，代碼中因此多了一個懶標記數組lazy。

我們來看一下懶標記下發的代碼，這里是區間求和，所以需要對左右子節點的個數進行累加，如果是求最大值就不需要。

再來看一下有懶標記的區間更新，當區間被完全覆蓋的時候，就不再往下走了，直接在當前節點上改，然后加上懶標記值。

再來看一下有懶標記的區間查詢。

7. 動態開點

線段樹雖然是一棵平衡的二叉搜索樹，但創建的時候并沒有看到它的節點類，因為我們使用的是純數組trees，類似于堆，但又不同于堆，因為堆可以看作是一棵完全二叉樹，但線段樹不是。這就導致了trees的長度是原數組長度的4倍，其中有很多空間是沒有存儲的。有的讀者可能會說，既然沒有存儲，為何還要申請那么大的空間，這里就來講一下線段樹數組trees為何要申請4倍空間。比如用長度為n的數組來創建線段樹，那么線段樹中肯定有n個葉子節點，并且還有n-1個祖先節點（n不等于1，否則沒有祖先節點），對于線段樹的最后一行不一定都是完全填滿的，最后一行的節點前面必須要有空間填充，極端情況下是2?(n-2)個節點，所以總共需要4?n-5個節點，如圖1-55所示。

既然使用純數組會造成空間的極大浪費，可以使用另外一種方式，為每個節點創建一個實體類，這樣最后一層就不需要填充了。但這樣還不夠，還可以繼續優化，如果某些節點暫時沒用到，就不需要創建，只有在需要的時候才會創建，也就是動態創建節點，我們稱為動態開點。只有在數據量比較大，但查詢比較少的情況下，動態開點才能發揮更大作用，我們先來看一下節點類。

代碼和前面使用數組的原理一樣，這里就不再寫了。只不過在下推pushDown的時候，如果子節點沒有創建，需要先創建子節點，用下面的代碼來測試一下。

運行結果如下：

如圖1-56所示，也就是說創建的時候只會創建根節點，查詢的時候會把從根節點到當前節點路徑上的節點全部創建出來。大家也可以嘗試用非遞歸的方式寫一下線段樹。

1.6.7 笛卡兒樹

笛卡兒樹不是特別常見的數據結構，如果熟練掌握它，對刷題也是非常有幫助的。比如有這樣一道題，給定n個非負整數，用來表示柱狀圖中各個柱子的高度。每個柱子彼此相鄰，且寬度為1。求在該柱狀圖中，能夠勾勒出來的矩形的最大面積，如圖1-57所示。

此題除了使用單調棧以外，還可以使用笛卡兒樹。講此題之前來看一下什么叫作笛卡兒樹。笛卡兒樹是一種二叉樹，它的每個節點有兩個值（x，y），其中一個滿足二叉搜索樹，一個滿足堆。也就是說笛卡兒樹同時具有二叉搜索樹和堆的兩種特性。假設每個節點的兩個值分別是元素的下標和元素的值，使用的是最小堆，笛卡兒樹的構建如下：

（1）用數組中的第一個元素創建根節點。

（2）遍歷數組中剩下的元素，如果當前元素比根節點小，讓根節點成為當前節點的左子節點，然后當前節點成為根節點。

（3）如果當前節點比根節點大，就從根節點沿著最右邊這條路徑往右走，直到找到比當前節點大的節點node，也可能沒找到。如果找到，就讓當前節點替換node節點的位置，讓node節點變成當前節點的左子節點。如果沒找到，就讓當前節點成為最后查找的那個節點的右子節點。

（4）重復上面步驟（2）、（3），直到元素全部遍歷完成。

我們來分析一下上面的步驟，首先是第（2）步，如果新節點比根節點小，根據最小堆（元素的值滿足最小堆）的性質，那么新節點一定是根節點的父節點。又因為根節點的下標比新節點小，根據二叉搜索樹（元素的下標滿足二叉搜索樹）的性質，根節點只能是新節點的左子樹。再來看第（3）步，如果新節點比根節點大，那么新節點只能往右邊查找，如果往左邊就不滿足二叉搜索樹的性質了。如果比右子節點還大，就繼續往右，所以只要比右子節點大，就會一直往右。如果比右子節點小，根據最小堆的性質，新節點就會成為這個右子節點的父節點，根據二叉搜索樹的性質，這個右子節點要成為新節點的左子節點（因為右子節點的下標比新節點?。?，如圖1-58所示。

我們看到笛卡兒樹的一個重要特性就是求一個元素的左右延伸區間。比如數字3，在笛卡兒樹中節點3往左一直延伸的數字是5，往右一直延伸的數字是9，也就是說在原數組中從5到9之間的數字都是大于3的（不包含自己）。笛卡兒樹還有一個非常重要的特性就是如果求一個區間[a,b]中的最小值，只需要找到a、b節點的最近公共祖先節點即可。比如找6和8之間的最小值，因為它們最近公共祖先節點的值是3，所以在原數組中6和8的最小值就是3。如果想求區間最大值呢？只需要在構建笛卡兒樹的時候使用最大堆即可。我們看一下笛卡兒樹的節點類。

再來看一下笛卡兒樹的構建，構建的時候我們需要使用一個單調棧（從棧頂到棧底是遞減的，棧底存儲的是根節點）來存儲最右邊這條路徑的節點，這條路徑從上到下是遞增的，每次查找的時候從下往上進行查找，也就是從棧頂元素開始比較，比新節點大的都要出棧，最后要記得把新節點入棧。

我們再來看一下開始講的那道題，把它轉換為笛卡兒樹，前面說過笛卡兒樹的一個重要特性就是求一個元素的左右延伸區間，我們只要計算每一個節點的左右延伸長度，然后計算它的面積即可，左右延伸的長度就是矩形的寬，當前節點的值就是矩形的高。怎樣求左右延伸的長度呢？其實仔細觀察就會發現，這個長度就是以當前節點為子樹的節點個數。通過后序遍歷的方式從下往上遍歷每一個節點，就可以計算每一棵子樹中節點的個數，最后看一下代碼。

1.6.8 其他樹

關于樹的種類非常多，除了書中介紹的以外，還有很多，比如B樹、2-3樹、四叉樹、八叉樹，散列樹、伸展樹、Treap樹等。剩下的就不在書中逐一介紹了，如果大家有興趣，可以自己研究。