2.7　樹

樹（Tree）是n（n≥0）個結點組成的有限集合。當n=0時，稱為空樹。當n>0時，稱為非空樹。

非空樹的特性如下：

（1）有且僅有一個根（Root）結點。

（2）當n>1時，除根結點以外的其他結點可以分為m（m>0）個互不相交的有限集合S1,S2,S3,...,Sm，每個集合本身也是一棵樹，這些樹稱為根結點的子樹。

從以上非空樹的特性可知，樹結構是一個遞歸的過程。根結點擁有子樹，子樹中的每個結點也可以擁有子樹。如圖2-32所示為一棵普通的樹。

圖2-32　普通樹示意圖

2.7.1　樹結構的相關概念

樹實現有多種，其中有一些通用的概念。

1．結點的度

結點擁有的子樹的數量稱為結點的度。在圖2-32所示的樹中，根結點A的度是2，結點B的度是3，結點C的度是2。

2．結點的關系

結點子樹的根結點稱作該結點的子結點（也可以稱作孩子結點）。相應地，該結點稱作孩子結點的父結點（也可以稱作雙親結點）。在圖2-32所示的樹中，結點B和結點C都是結點A的孩子結點。結點A稱為結點B和結點C的父結點。

同一個父結點的所有子結點之間互相稱作兄弟結點。在圖2-32所示的樹中，結點B和結點C互為兄弟結點。

3．結點的層次

從根結點開始，根結點稱為第1層，根結點的孩子稱為第2層，以此類推。結點的層次如圖2-33所示。

圖2-33　結點的層次示意圖

4．樹的高度

樹中結點的最大層次稱為樹的高度（或者稱為深度）。在圖2-33所示的樹中，樹的高度為4。

5．樹的葉結點

如果一個結點沒有任何子結點，那么稱這個結點為葉結點。在圖2-33所示的樹中，結點D、結點E、結點F、結點H、結點I、結點J都是葉結點。

2.7.2　二叉樹

二叉樹是n（n≥0）個結點組成的有限集合，該集合或者為空集（稱為空二叉樹），或者由一個根結點和兩棵互不相交的子樹組成，這兩棵子樹分別稱為根結點的左子樹和右子樹。二叉樹如圖2-34所示。

圖2-34　二叉樹示意圖

二叉樹的特點如下：

（1）二叉樹中每個結點最多有兩棵子樹，即二叉樹中不存在度大于2的結點。

（2）二叉樹是區分左子樹和右子樹的，左子樹和右子樹不能隨意顛倒。

（3）即使二叉樹中某個結點只有一棵子樹，這棵子樹也是要區分左子樹和右子樹的。

（4）在二叉樹中，第i層最多有2^i-1個結點（i≥1）。

（5）高度為h的二叉樹，最多有2^h-1個結點（h≥1）。

（6）n0=n2+1，其中n0表示度為0的結點數，n2表示度為2的結點數。

2.7.3　斜樹

斜樹的定義是基于二叉樹的，即斜樹仍然是一棵二叉樹。斜樹分為兩種：

（1）左斜樹：是一種所有的結點都只有左子樹的二叉樹或者沒有子樹的一種特殊的二叉樹。

（2）右斜樹：是一種所有的結點都只有右子樹或者沒有子樹的一種特殊的二叉樹。

斜樹如圖2-35所示。

圖2-35　左斜樹和右斜樹示意圖

2.7.4　滿二叉樹

所有結點都存在左子樹和右子樹，并且所有的葉子結點都在同一層上的二叉樹，稱為滿二叉樹。

滿二叉樹的特點如下：

（1）所有的葉子必須出現在最后一層。

（2）非葉子結點的度一定是2。

（3）在同樣高度的二叉樹中，滿二叉樹的總結點數最多，滿二叉樹的葉子結點數最多。

滿二叉樹如圖2-36所示。

圖2-36　滿二叉樹示意圖

2.7.5　完全二叉樹

完全二叉樹是由滿二叉樹引出的。對一棵高度為h，具有n個結點的二叉樹，當且僅當每個結點都與深度為h的滿二叉樹中編號為1～n的結點一一對應時，稱這棵二叉樹為完全二叉樹。

完全二叉樹的特點如下：

（1）葉子結點只能在最后一層或者倒數第二層。

（2）最下層的葉子結點集中在完全二叉樹的左邊。

（3）倒數第二層如果存在葉子結點，那么一定集中在完全二叉樹的右邊。

（4）如果結點的度為1，那么該結點只能有左子樹，沒有右子樹。

（5）同樣結點數目的二叉樹，完全二叉樹高度最小。

（6）滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。

完全二叉樹如圖2-37所示。

圖2-37　完全二叉樹示意圖

2.7.6　二叉樹存儲結構

二叉樹的存儲可以使用順序存儲結構和鏈式存儲結構。

1．二叉樹順序存儲結構

二叉樹的順序存儲結構使用一維數組存儲二叉樹中的結點，并且通過數組下標表示結點在二叉樹中的位置。

對一棵完全二叉樹采用如圖2-38所示的方式進行編號。

圖2-38　完全二叉樹編號示意圖

圖2-38所示的完全二叉樹可以使用圖2-39所示的一維數組存儲。

圖2-39　完全二叉樹順序存儲示意圖

對一棵非完全二叉樹進行編號（圖中虛線框中的結點為不存在的結點），如圖2-40所示。

圖2-40　非完全二叉樹編號示意圖

圖2-40所示的非完全二叉樹順序存儲結構如圖2-41所示。

圖2-41　非完全二叉樹順序存儲示意圖

圖2-41中一維數組空出的位置4、8和9并沒有存儲元素，此時順序存儲結構出現空間浪費。當用順序存儲結構存儲左斜樹或者右斜樹時，將會造成更大的空間浪費。因此，順序存儲結構僅適用于完全二叉樹的存儲。

2．二叉樹鏈式存儲結構

使用如圖2-42所示的數據結構表示二叉樹的一個結點。其中，data表示結點的數據域，leftChild表示結點的左子樹的引用，rightChild表示結點的右子樹的引用。

圖2-42　自定義結構表示二叉樹結點

使用圖2-42的數據結構存儲二叉樹，如圖2-43所示。

圖2-43　二叉樹鏈式存儲結構示意圖

2.7.7　二叉樹的遍歷

二叉樹的遍歷指從二叉樹的根結點出發，按照某種次序依次訪問二叉樹中所有結點的過程。

（1）二叉樹前序遍歷

前序遍歷的順序是：首先遍歷根結點，然后遞歸遍歷左子樹，最后遞歸遍歷右子樹。

圖2-38所示的二叉樹前序遍歷結果為：ABDHIEJCFG。

（2）二叉樹中序遍歷

中序遍歷的順序是：首先遞歸遍歷左子樹，然后遍歷根結點，最后遞歸遍歷右子樹。

圖2-38所示的二叉樹中序遍歷結果為：HDIBJEAFCG。

（3）二叉樹后序遍歷

后序遍歷的順序是：首先遞歸遍歷左子樹，然后遞歸遍歷右子樹，最后遍歷根結點。

圖2-38所示的二叉樹后序遍歷結果為：HIDJEBFGCA。

（4）二叉樹層次遍歷

層次遍歷是按照樹的層次自上而下遍歷二叉樹中的所有結點。

圖2-38所示的二叉樹層次遍歷結果為：ABCDEFGHIJ。

2.7.8　二叉排序樹

二叉排序樹又稱二叉查找樹或二叉搜索樹。二叉排序樹是一種特殊的二叉樹，需要滿足以下條件：

（1）如果左子樹非空，那么左子樹上所有結點的值都小于根結點的值。

（2）如果右子樹非空，那么右子樹上所有結點的值都大于根結點的值。

（3）每個結點的左子樹和右子樹都必須是二叉排序樹。

（4）二叉樹的所有結點中沒有值相等的結點。

1．二叉排序樹查找元素

二叉排序樹的查找過程如下：

（1）判斷根結點的值是否等于查找的值，如果相等，就返回，否則執行（2）。

（2）如果查找的值小于結點的值，就遞歸查找左子樹。

（3）如果查找的值大于結點的值，就遞歸查找右子樹。

（4）二叉排序樹中不存在值相等的結點。

在如圖2-44所示的二叉排序樹查找值為4的元素。

圖2-44　二叉排序樹查找元素示意圖

二叉排序樹的查找過程的時間復雜度是O(log₂n)。

2．二叉排序樹添加元素

二叉排序樹添加元素需要經歷查找過程，通過二叉排序樹的查找過程找到待添加元素的合適的位置，以保證添加元素后仍滿足二叉排序樹的要求。

3．二叉排序樹刪除元素

二叉排序樹刪除元素分為3種情況，下面分別介紹。

（1）刪除的結點是葉子結點

在二叉排序樹中刪除葉子結點不會破壞二叉排序樹的結構，可以直接刪除。在圖2-44所示的二叉排序樹中，需要刪除葉子結點1。找到結點1所在的位置，直接刪除。刪除過程如圖2-45所示。

圖2-45　二叉排序樹刪除葉結點示意圖

（2）刪除的結點只有左子樹或者右子樹

在二叉排序樹中刪除的結點僅有左子樹或者右子樹，使用左子樹或者右子樹的根結點替換刪除的結點，刪除指定的結點。

在圖2-44所示的二叉排序樹中，刪除元素5，需要將結點4移動到結點5的位置，然后刪除結點5。刪除過程如圖2-46所示。

圖2-46　二叉排序樹刪除僅有一個子結點的結點示意圖

（3）刪除的結點有左子樹和右子樹

刪除的結點有左子樹和右子樹，刪除該結點后，需要對二叉排序樹進行調整。調整的方式有兩種，下面分別介紹。

【方案1】從刪除的結點的左子樹中，找到左子樹最右邊的結點，即左子樹中最大的結點，替換刪除的結點；然后進行后續的調整。刪除過程如圖2-47所示。

圖2-47　二叉排序樹刪除有左右子結點的結點方案1示意圖

【方案2】從刪除的結點的右子樹中，找到右子樹最左邊的結點，即右子樹中最小的結點，替換刪除的結點；然后進行后續的調整。刪除過程如圖2-48所示。

圖2-48　二叉排序樹刪除有左右子結點的結點方案2示意圖

刪除二叉排序樹的3種情況中，第3種情況可以轉化為前兩種情況。

當找到刪除結點的左子樹中的最大結點或者右子樹中的最小結點后，對刪除的結點進行替換。替換后，替換結點只可能有一棵左子樹，或者沒有子樹，即是葉子結點。

在圖2-47中，用于替換的結點5不可能有右子樹，如果有，就應該是結點5的右子結點替換結點6。

在圖2-48中，用于替換的結點7不可能有左子樹，如果有，就應該是結點7的左子結點替換結點6。

4．二叉排序樹的實現

二叉排序樹的代碼實現如下：

創建二叉排序樹的測試類，驗證二叉排序樹的功能。測試代碼如下：

執行測試代碼，執行結果如下：

    ----------二叉排序樹中序遍歷結果----------
    1 2 3 4 5 6 7 8 9 10
    ----------二叉排序樹先序遍歷結果----------
    6 3 2 1 5 4 8 7 10 9
    ----------二叉排序樹后序遍歷結果----------
    1 2 4 5 3 7 9 10 8 6
    -----二叉排序樹刪除元素8后中序遍歷結果------
    1 2 3 4 5 6 7 9 10

2.7.9　AVL樹

AVL樹本質上是一棵自平衡的二叉排序樹。AVL樹具有以下特點：

（1）AVL樹是一棵空樹或它的左右兩棵子樹的高度差的絕對值不超過1。

（2）AVL樹每個結點的左右兩棵子樹都是一棵平衡二叉樹。

平衡二叉樹和非平衡二叉樹對比如圖2-49所示。

圖2-49　平衡二叉樹和非平衡二叉樹對比示意圖

AVL樹中有一個重要的概念叫作平衡因子。平衡因子指左子樹與右子樹高度差的絕對值。計算公式如下：

平衡因子=|左子樹高度-右子樹高度|

AVL樹的平衡因子的取值范圍是：-1≤平衡因子≤1。

普通的二叉排序樹在一些極端的情況下可能會退化成鏈式結構，例如圖2-50所示的結點1～5組成的二叉排序樹。

圖2-50　退化成鏈式結構的二叉排序樹示意圖

當二叉排序樹退化成為鏈表時，此時訪問其中的元素的時間復雜度從O(log₂n)退化為O(n)。即便是在構建二叉排序樹時盡量避免如圖2-50所示的情況，但是隨著在使用過程中不斷地對二叉排序樹進行添加和刪除操作，還是會造成二叉排序樹向左傾斜或者向右傾斜，造成二叉排序樹的平衡性被破壞。

1．AVL樹的基本操作

AVL樹的插入和刪除可能會破壞AVL樹的平衡性。在插入或刪除元素后，從變更的結點開始向根結點回溯，遇到的第一個不平衡的結點稱為“最低失衡根結點”。從最低失衡根結點向下分析，不平衡的情況可以分為4種情況：

（1）導致失衡的結點出現在最低失衡根結點的左子樹的左子樹中。

（2）導致失衡的結點出現在最低失衡根結點的左子樹的右子樹中。

（3）導致失衡的結點出現在最低失衡根結點的右子樹的右子樹中。

（4）導致失衡的結點出現在最低失衡根結點的右子樹的左子樹中。

分析解決不平衡的情況之前，先介紹兩種調整AVL樹使之平衡的基本操作。

①左旋轉

當向AVL樹插入元素后，右子樹的高度減去左子樹的高度大于1，此時發生左旋轉，即AVL樹向左旋轉，如圖2-51所示。

圖2-51　左旋轉示意圖

②右旋轉

當向AVL樹插入元素后，左子樹的高度減去右子樹的高度大于1，此時發生右旋轉，即AVL樹向右旋轉，如圖2-52所示。

圖2-52　右旋轉示意圖

下面分別對各種不平衡的情況進行分析。

（1）LL情況旋轉

LL（Left-Left）旋轉即導致失衡的結點出現在最低失衡根結點的左子樹的左子樹中而發生結點旋轉的情況。旋轉方式是找到最低失衡根結點，將最低失衡根結點右旋轉，如圖2-53所示。

圖2-53　導致失衡的結點出現在最低失衡根結點的左子樹的左子樹中示意圖

如圖2-53所示，最低失衡根結點是結點5，失衡是因為結點1的存在，而結點1位于結點5左子樹的左子樹中，需要一次右旋轉即可達到平衡。具體的方法是：LL旋轉的對象是最低失衡根結點（結點5），找到結點5的左孩子（結點3），將結點3的右孩子結點4變成結點5的左孩子，最后將結點5變成結點3的右孩子，調整后的AVL樹如圖2-54所示。

圖2-54　LL情況旋轉示意圖

（2）LR情況旋轉

LR（Left-Right）旋轉即導致失衡的結點出現在最低失衡根結點的左子樹的右子樹中而發生旋轉的情況。旋轉方式是找到最低失衡根結點，先對最低失衡根結點的左孩子進行左旋轉，然后對最低失衡根結點進行右旋轉，如圖2-55所示。

圖2-55　導致失衡的結點出現在最低失衡根結點的左子樹的右子樹中示意圖

圖2-55的情況的調整過程：首先對最低失衡根結點5的左孩子結點2進行左旋轉，然后對最低失衡根結點5進行右旋轉。調整過程如圖2-56所示。

圖2-56　LR情況旋轉示意圖

（3）RR情況旋轉

RR（Right-Right）旋轉即導致失衡的結點出現在最低失衡根結點的右子樹的右子樹中而發生旋轉的情況。旋轉方式是找到最低失衡根結點，將最低失衡根結點左旋轉，如圖2-57所示。

圖2-57　導致失衡的結點出現在最低失衡根結點的右子樹的右子樹中示意圖

如圖2-57所示，最低失衡根結點是結點2，失衡是結點6導致的，而結點6位于結點2右子樹的右子樹，需要一次左旋轉即可達到平衡。旋轉的對象是最低失衡根結點（結點2），找到結點2的右孩子結點4，將結點4的左孩子結點3變成結點2的右孩子，最后將結點2變成結點4的左孩子，旋轉后的結果如圖5-58所示。

圖2-58　RR情況旋轉示意圖

（4）RL情況旋轉

RL（Right-Left）旋轉即導致失衡的結點出現在最低失衡根結點的右子樹的左子樹中而發生旋轉的情況。旋轉方式是找到最低失衡根結點，先對最低失衡根結點的右孩子進行右旋轉，然后對最低失衡根結點進行左旋轉，如圖2-59所示。

圖2-59　導致失衡的結點出現在最低失衡根結點的右子樹的左子樹中示意圖

圖2-59的情況的調整過程：首先對最低失衡根結點2的右孩子結點5進行右旋轉，然后對最低失衡根結點2進行左旋轉。調整過程如圖2-60所示。

圖2-60　RL情況旋轉示意圖

2．AVL樹的實現

AVL樹的代碼實現如下：

創建AVL樹的測試類，驗證AVL樹的功能。在測試代碼中，通過數組中的1～16共16個數字創建了一個如圖2-61所示的AVL樹。

圖2-61　測試類創建的AVL樹示意圖

AVL樹的測試類代碼如下：

執行測試代碼，執行結果如下：

    ----------中序遍歷AVL樹----------
    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
    ----------先序遍歷AVL樹----------
    7 4 2 1 3 6 5 13 11 9 8 10 12 15 14 16
    ----------后序遍歷AVL樹----------
    1 3 2 5 6 4 8 10 9 12 11 14 16 15 13 7
    --------在AVL樹查找元素12--------
    12
    --------在AVL樹查找元素20--------
    -1
    --------在AVL樹刪除元素12--------
    --------刪除元素12后遍歷AVL樹--------
    ----------中序遍歷AVL樹----------
    1 2 3 4 5 6 7 8 9 10 11 13 14 15 16
    ----------先序遍歷AVL樹----------
    7 4 2 1 3 6 5 13 10 9 8 11 15 14 16
    ----------后序遍歷AVL樹----------
    1 3 2 5 6 4 8 9 11 10 14 16 15 13 7

2.7.10　2-3-4樹

2-3-4樹是一棵單個結點可以存儲多個元素值的完美平衡（Perfect Balance）的查找樹。所謂完美平衡，指的是從2-3-4樹的根結點到每個葉子結點的路徑的高度都是相等的。2-3-4樹是一種進階的二叉樹，是一種自平衡的數據結構，它可以保證O(log₂n)的時間內完成查找、插入和刪除操作。2-3-4樹具有以下性質：

（1）每個結點可以存儲1個、2個或者3個元素值，相應的稱這些結點為2（孩子）結點、3（孩子）結點、4（孩子）結點。

（2）根結點到所有的葉子結點的路徑長度相等。

（3）每個結點的元素值從左到右保持了從大到小的順序。兩個元素值之間的子樹中所有結點的元素值一定大于其父結點的左邊的元素值，小于其父結點的右邊的元素值。

（4）2結點的左子樹上的所有元素值小于其父結點的元素值。2結點右子樹上的所有元素值大于其父結點的元素值。

（5）3結點的左子樹的所有元素值小于其父結點最小的元素值。3結點中間子樹的所有元素值大于其父結點最小的元素值，小于其父結點最大的元素值。3結點的右子樹上的所有元素值大于其父結點的最大元素值。同理，4結點也滿足這樣的性質。

2-3-4樹示意圖如圖2-62所示。

圖2-62　2-3-4樹示意圖

1．2-3-4樹的查找元素

2-3-4樹查找元素的過程與二叉排序樹類似，首先比較查找的元素值與根結點的大小，如果元素值不存在于根結點中，就選擇元素值所在的子樹，遞歸上述過程，直至找到元素。2-3-4樹的查找過程如圖2-63所示。

圖2-63　2-3-4樹查找元素示意圖

2．2-3-4樹添加元素

2-3-4樹添加元素的步驟如下：

（1）如果2-3-4樹中已存在當前插入的key，就會插入失敗，否則通過查找過程找到合適的位置，在葉子結點中進行插入操作。

（2）如果待插入的結點不是4結點，那么直接在該結點插入新元素即可。

（3）如果待插入的結點是4結點，那么應該先分裂該結點再插入。一個4結點可以分裂成一個根結點和兩個子結點（這3個結點各含一個元素值），然后在子結點中插入，可以把分裂形成的根結點中的元素值看成向上層結點插入的一個元素值。

（4）重復第2步和第3步，直至2-3-4樹達到完美平衡。

下面分別對2-3-4樹的各種插入情況進行分析。

（1）向一個2結點插入元素

直接將2結點變成一個3結點即可。例如向圖2-63所示的2-3-4樹中插入元素12，插入結果如圖2-64所示。插入元素12，將2結點【15】變成一個3結點。

圖2-64　2-3-4樹2結點插入元素示意圖

（2）向一個3結點插入元素

將3結點變成一個4結點即可。例如向圖2-63所示的2-3-4樹中插入元素20，插入結果如圖2-65所示。插入元素20，將3結點【17，19】變成一個4結點。

圖2-65　2-3-4樹3結點插入元素示意圖

（3）向一個4結點插入元素

4結點已經是最大的結點了，無法再插入元素。首先將4結點分裂成一個根結點和兩個2子結點，向父結點中插入這個剛剛分裂出來的根結點。如果父結點也是一個4結點，就遞歸父結點的父結點直至2-3-4樹達到平衡。例如向圖2-65所示的2-3-4樹中插入元素18，則插入過程可以分解為以下兩個步驟。

（1）將4結點【17，19，20】分裂成3個2結點。分裂過程如圖2-66所示。

圖2-66　2-3-4樹4結點分裂示意圖

（2）將元素18插入2-3-4樹中，調整2-3-4樹使之達到平衡。

在如圖2-65所示的2-3-4樹中，4結點【17，19，20】的父結點【10，16，21】也是一個4結點，當4結點【17，19，20】分裂后，結點19會進入父結點【10，16，21】，因此父結點也需要進行圖2-66所示的分裂。

向圖2-65所示的2-3-4中插入元素18的詳細過程如下：

首先通過2-3-4樹的查找過程找到元素18合適的位置，如圖2-67所示。

圖2-67　查找元素18合適的位置示意圖

4結點【17，19，20】進行分裂，元素19會進入父結點中，分裂結果如圖2-68所示。

圖2-68　4結點【17，19，20】分裂示意圖

由于元素19的進入造成4結點【10，16，21】進行分裂，分裂結果如圖2-69所示。

圖2-69　4結點【10，16，21】分裂示意圖

達到圖2-69所示的狀態后，2-3-4樹已經達到完美平衡，不需要再進行調整，此次插入元素18結束。

（4）帶有預分裂的插入

上述的向4結點插入元素的操作在某些情況下需要不斷回溯來調整樹的結構以達到平衡。為了消除回溯過程，在插入操作過程中可以采取預分裂的操作，即在插入操作搜索過程中，遇到4結點就分裂（分裂后形成的根結點的元素要上移，與父結點中的元素合并），這樣可以保證查找到需要插入的結點時可以直接插入（該結點一定不是4結點）。

在圖2-65所示的2-3-4樹中，當查找元素18的存儲位置時，遇到4結點【10，16，21】進行預分裂，如圖2-70所示。

圖2-70　4結點【10，16，21】預分裂示意圖

在圖2-70所示的2-3-4樹中，繼續向下查找元素18的存儲位置，當遇到4結點【17，19，20】時進行預分裂，如圖2-71所示。

圖2-71　4結點【17，19，20】預分裂示意圖

此時尋找到結點17可以存儲元素18，直接將元素18插入即可。插入后的結果見圖2-69。

3．2-3-4樹刪除元素

2-3-4樹刪除元素的步驟如下：

（1）如果刪除的元素不存在于2-3-4樹中，就會刪除失敗。

（2）刪除的元素不存在于葉子結點，用后繼結點替代刪除的結點。

（3）刪除的元素位于葉子結點，如果葉子結點不是2結點，那么直接刪除元素即可。如果刪除的元素是2結點，那么刪除該結點后需要進行如下調整：

①如果兄弟結點不是2結點，就將父結點中的一個元素值下移到該結點，兄弟結點中的一個元素值上移到父結點。

②如果兄弟結點是2結點，父結點是3結點或者4結點，父結點中的元素值就與兄弟結點中的元素值合并。

③如果兄弟結點是2結點，父結點是2結點，父結點中的元素值就與兄弟結點中的元素值合并，形成一個新的3結點，以新的3結點作為當前結點，重復①和②的步驟進行調整。

以圖2-62為例，刪除元素55的過程如下：

首先通過2-3-4樹的查找過程找到元素55所在的結點位置，刪除結點55，如圖2-72所示。

圖2-72　查找并刪除元素55示意圖

由于刪除的結點位于葉子結點，滿足第（3）點的第③小點，需要將父結點和兄弟結點合并，如圖2-73所示。

圖2-73　父結點60和兄弟結點70合并示意圖

調整后的結點【60，70】的兄弟結點和父結點都是2結點，繼續合并兄弟結點和父結點，如圖2-74所示。

圖2-74　父結點75和兄弟結點88合并示意圖

調整后的結點【75，88】的父結點和兄弟結點都是2結點，繼續合并父結點和兄弟結點，如圖2-75所示。

圖2-75　父結點50和兄弟結點23合并示意圖

從2-3-4樹刪除和調整結點的過程可知，如果2-3-4樹的刪除導致了根結點參與合并， 2-3-4樹的高度就會降低一層。例如上述刪除元素55的過程中，2-3-4樹的高度從4降到了3。

與2-3-4樹插入元素的過程相對應的，2-3-4樹可以使用預合并的刪除操作避免刪除過程中的回溯。在搜索過程中（除根結點，因為根結點沒有兄弟結點和父結點），遇到當前結點是2結點，如果兄弟結點也是2結點就合并（該結點的父結點中的元素值下移，與自身和兄弟結點合并）；如果兄弟結點不是2結點，那么父結點的元素值下移，兄弟結點中的元素值上移。這樣可以保證，找到需要刪除的元素值所在的結點時可以直接刪除（要刪除的元素值所在的結點一定不是2結點）。

在圖2-62所示的2-3-4樹中，當查找元素55的存儲位置時，遇到2結點75，其兄弟結點也是2結點，需要預合并，如圖2-76所示。

圖2-76　查找到2結點75示意圖

對2結點75及其兄弟結點23和父結點50進行預合并，預合并結果如圖2-77所示。

圖2-77　2結點23、2結點50和2結點75預合并示意圖

繼續向下搜索，找到2結點60，其兄弟結點【35，48】是3結點，父結點中的元素值下移，兄弟結點中的元素值上移，如圖2-78所示。值得注意的是，除了這種調整方式以外，還可以將父結點的元素值75與結點88合并，這兩種方式都可以使2-3-4樹達到平衡。

圖2-78　父結點元素值50下移，兄弟結點元素值48上移示意圖

找到元素55所在的結點后，結點55是一個2結點，其兄弟結點是2結點，父結點【50，60】中的元素值下移，與結點55和結點70進行預合并，合并結果如圖2-79所示。

圖2-79　父結點元素值60與兄弟結點55和兄弟結點70預合并示意圖

刪除結點55后的結果如圖2-80所示。

圖2-80　刪除結點55后2-3-4樹示意圖

下面分析2-3-4樹的執行效率。

（1）2-3-4樹高度的最壞情況（全是2結點），相當于演變成了平衡二叉樹，其查詢的時間復雜度為O(log₂n)。

（2）2-3-4樹高度的最好情況（全是4結點），O(log₄n )= 1/2 O(log₂n)（但這種情況是不可能出現的，因為4結點的父結點或者子結點不能是4結點）。

（3）對于100萬個結點，2-3-4樹的高度為10～20。

（4）對于10億的結點，2-3-4樹的高度為15～30。

由此來看，2-3-4樹的效率比平衡二叉樹要好，但是問題在于2-3-4樹并不好實現。

首先，需要用3種不同類型的結點代表2結點、3結點和4結點。

其次，在插入結點時，可能需要進行大量的切分4結點的工作，也可能需要頻繁地在3種結點之間進行轉換。

為了更好地利用2-3-4樹平衡高度的特點，同時又便于實現，于是誕生了紅黑樹。

2.7.11　紅黑樹

紅黑樹是與2-3-4樹一一對應的樹形結構，由于大部分編程語言直接實現2-3-4樹很煩瑣，因此一般是通過紅黑樹來實現2-3-4樹的。紅黑樹同樣可以保證在O(log₂n)時間內完成查找、插入和刪除操作。

紅黑樹是每個結點都帶有紅色或黑色屬性的平衡二叉排序樹。紅黑樹除了滿足一般二叉排序樹的要求外，紅黑樹還需要滿足以下要求：

（1）每個結點必須帶有顏色，紅色或者黑色。

（2）根結點一定是黑色。

（3）每個葉子結點都帶有兩個空的黑色子結點（NIL結點，又稱為黑色哨兵）。

（4）每個紅色結點的兩個子結點都是黑色結點，即從根結點到葉子結點的所有路徑上，不存在兩個連續的紅色結點。

（5）從任一結點到其所能到達的葉子結點的所有路徑含有相同數量的黑色結點。

紅黑樹是一個基本平衡的二叉排序樹，紅黑樹并沒有像AVL樹一樣保持絕對平衡，但是同樣數量的結點組成的紅黑樹比AVL樹少了很多旋轉操作，且紅黑樹的刪除效率比AVL樹更高。

紅黑樹與2-3-4樹的等價關系如下：

（1）3結點與紅黑樹的對應關系

2-3-4樹的一個3結點可以使用紅黑樹的一個紅色結點加一個黑色結點表示。如圖2-81所示是紅黑樹表示的2-3-4樹的一個3結點。

圖2-81　2-3-4樹3結點與紅黑樹對應關系示意圖

（2）4結點與紅黑樹的對應關系

2-3-4樹的一個4結點可以使用紅黑樹的兩個紅色結點加一個黑色結點表示。如圖2-82所示是紅黑樹表示的2-3-4樹的一個4結點。

圖2-82　2-3-4樹4結點與紅黑樹對應關系示意圖

一棵完整的2-3-4樹對應的紅黑樹如圖2-83所示。

圖2-83　2-3-4樹與紅黑樹對應關系示意圖

根據圖2-83所示的紅黑樹，參照上述紅黑樹的5個特性進行分析。

（1）紅黑樹中每個結點都有顏色，結點的顏色只能為紅色或者黑色。

（2）紅黑樹的根結點是黑色結點。如圖2-83所示的結點8為黑色。

（3）紅黑樹的每個葉子結點帶有兩個空的黑色子結點，如圖2-83所示的NIL結點。

（4）紅黑樹的每個紅色結點的兩個子結點都是黑色結點。

（5）紅黑樹的根結點到每個黑色子結點NIL的路徑上包含的黑色結點數目都是3個。

因此，圖2-83中的紅黑樹就是一棵標準的紅黑樹。

一棵紅黑樹對應一棵唯一形態的2-3-4樹，但是一棵2-3-4樹可以對應多種形態的紅黑樹，原因在于2-3-4樹的3結點對應兩種不同形態的紅黑樹，如圖2-81所示。

紅黑樹的查找操作與二叉排序樹類似。下面將重點分析紅黑樹添加元素操作和刪除元素操作。

1．紅黑樹添加元素

紅黑樹添加元素的過程如下：

（1）如果紅黑樹中已存在待插入的值，那么插入操作失敗，否則一定是在葉子結點進行插入操作，執行步驟（2）。

（2）插入一個新結點后，將該結點涂紅（涂紅操作，從2-3-4樹的角度來看，就是向上層結點進位一個元素值），由于插入操作可能破壞了紅黑樹的平衡性，因此需要不斷回溯，進行調整。調整過程就是顏色變換和旋轉操作，而這些操作都可以結合2-3-4樹來理解。

插入新結點時，可以分為以下幾種情況：

（1）父結點是黑色結點

如果父結點是黑色結點，插入新結點后，給結點涂紅色即可，如圖2-84所示。

圖2-84　插入結點的父結點是黑色示意圖

圖2-84中箭頭指向的結點表示插入的位置，圖中的虛線表示可以有該結點，也可以沒有該結點，如果有，那么該結點一定是紅色的。這種插入場景還有可能存在另一種對稱的情況，即在父結點的右子樹上插入，操作方式是一樣的，由于不涉及旋轉操作，因此不再贅述。

這個操作相當于在2-3-4樹中插入的葉子結點是2結點（紅黑樹中的黑色父結點沒有子結點）或者3結點（紅黑樹中的黑色父結點有一個紅色子結點），此時不會造成2-3-4樹結點分裂，因此此時的紅黑樹不需要進行調整。

（2）父結點是紅色的且叔叔結點是黑色的

這種情況需要對當前的紅黑樹進行相應的調整，以使紅黑樹恢復平衡。這種情況相當于2-3-4樹中，容納進位的父結點為3結點，還有空間可以容納新的元素值，所以到這里就不用繼續回溯了。

這種情況分別有以下4種形態：

①不平衡的紅色結點是左子樹中紅色父結點的左孩子，如圖2-85所示。

圖2-85　紅色結點是左子樹中紅色父結點的左孩子示意圖

②不平衡的紅色結點是左子樹中紅色父結點的右孩子，如圖2-86所示。

當出現圖2-86的形態時，需要進行一次左旋轉，左旋轉后轉化為圖2-85所示的形態，繼續進行后續的調整。

圖2-86　紅色結點是左子樹中紅色父結點的右孩子示意圖

以上兩種形態還有其對應的鏡像形態，即發生在右子樹上。

③不平衡的紅色結點是右子樹中紅色父結點的右孩子，如圖2-87所示。

圖2-87　紅色結點是右子樹中紅色父結點的右孩子示意圖

④不平衡的紅色結點是右子樹中紅色父結點的左孩子，如圖2-88所示。

圖2-88　紅色結點是右子樹中紅色父結點的左孩子示意圖

當出現圖2-88的形態時，需要進行一次右旋轉，右旋轉后轉化為圖2-87所示的形態，繼續進行后續的調整。

（3）父結點是紅色的且叔叔結點是紅色的

這種情況相當于2-3-4樹中，向上進位的父結點為4結點，所以先分裂，再插入新的元素并繼續回溯，把分裂出的父結點看成向更上一層進位的結點繼續回溯。

這種情況分別有以下4種形態：

①不平衡的紅色結點是左子樹中紅色父結點的左孩子，如圖2-89所示。

圖2-89　紅色結點是左子樹中紅色父結點的左孩子示意圖

②不平衡的紅色結點是左子樹中紅色父結點的右孩子，如圖2-90所示。

圖2-90　紅色結點是左子樹中紅色父結點的右孩子示意圖

以下兩種形態是與上面兩種形態對應的鏡像形態，即發生在右子樹上。因不涉及旋轉操作，可以復用以上兩種形態的代碼實現，所以不進行區分。

③不平衡的紅色結點是右子樹中紅色父結點的右孩子。

④不平衡的紅色結點是右子樹中紅色父結點的左孩子。

2．紅黑樹刪除元素

紅黑樹刪除操作的過程如下：

（1）如果在紅黑樹中不存在要刪除的元素值，就會刪除失敗，否則執行（2）。

（2）如果刪除的結點不是葉子結點，就用刪除結點的后繼結點替換，顏色不需要改變。

刪除結點可以分為以下幾種情況：

（1）要刪除的結點為紅色葉子結點

如果要刪除的結點為紅色葉子結點，那么直接刪除該結點即可，如圖2-91所示。

圖2-91　刪除紅色葉子結點示意圖

（2）要刪除的結點是一個黑色結點且只有一個孩子結點

如果要刪除的結點只有一個孩子結點，那么這個孩子結點一定是紅色結點。刪除此結點后，孩子結點上移并涂黑色。這種情況如圖2-92和圖2-93所示。

圖2-92　刪除黑色結點擁有紅色左孩子示意圖

圖2-93　刪除黑色結點擁有紅色右孩子示意圖

（3）要刪除的結點是一個黑色葉子結點

刪除黑色葉子結點后需要對紅黑樹進行調整，使之重新達到平衡。調整的情況分為以下a、b、c和d所示的4種。其中未著色的結點可以為紅色或黑色。

1）刪除的結點的兄弟結點為黑色結點且侄子結點為紅色，這種情況分為以下1、2、3和4這四種不同的情況。

①刪除的黑色葉子結點是父結點的右子結點，且其兄弟結點為黑色結點，且左侄子結點為紅色的情況。刪除黑色葉子結點10的調整過程如圖2-94所示。

圖2-94　刪除右子結點10，兄弟結點4為黑色的，左侄子結點2為紅色的示意圖

②刪除的黑色葉子結點是父結點的右子結點，且其兄弟結點為黑色結點，且右侄子結點為紅色的情況。刪除黑色葉子結點10的調整過程如圖2-95所示。

圖2-95　刪除右子結點10，兄弟結點4為黑色的，右侄子結點6為紅色的示意圖

③刪除的黑色葉子結點是父結點的左子結點，且其兄弟結點為黑色結點，且右侄子結點為紅色的情況。刪除黑色葉子結點4的調整過程如圖2-96所示。

圖2-96　刪除左子結點4，兄弟結點10為黑色的，右侄子結點12為紅色的示意圖

④刪除的黑色葉子結點是父結點的左子結點，且其兄弟結點為黑色結點，且左侄子結點為紅色的情況。刪除黑色葉子結點4的調整過程如圖2-97所示。

圖2-97　刪除左子結點4，兄弟結點10為黑色的，左侄子結點9為紅色的示意圖

2）刪除的結點的兄弟結點為黑色結點，且侄子結點為黑色結點，且父結點是紅色結點（侄子結點只能是NIL結點，因為刪除的結點是葉子結點）。刪除結點4的調整過程如圖2-98所示。刪除結點10與刪除結點4類似，刪除結點10的過程不再贅述。

圖2-98　刪除黑色結點4，兄弟結點10為黑色的，父結點8為紅色的示意圖

3）刪除的結點的兄弟結點、侄子結點、父結點都是黑色結點（侄子結點只能是NIL結點，因為刪除的結點是葉子結點）。刪除結點4的調整過程如圖2-99所示。刪除結點10與刪除結點4類似，刪除結點10的過程不再贅述。

圖2-99　刪除黑色結點10，兄弟結點4為黑色的，父結點8為黑色的示意圖

4）刪除的結點的兄弟結點是紅色結點，父結點是黑色結點。對結點4的調整過程如圖2-100所示，旋轉完成后轉換成了③中的情況。

圖2-100　調整黑色結點4，兄弟結點10為紅色的，父結點8為黑色的

3．紅黑樹的實現

紅黑樹的代碼實現如下：

在測試類中創建了一顆紅黑樹，如圖2-101所示。

圖2-101　在測試類中創建的紅黑樹示意圖

刪除元素60后的紅黑樹如圖2-102所示。

圖2-102　在測試類中創建的紅黑樹刪除元素60后示意圖

紅黑樹測試類代碼如下：

執行測試代碼，執行結果如下：

    ----------紅黑樹中序遍歷結果----------
    0:紅色  5:黑色  10:紅色  20:黑色  30:黑色  40:黑色  50:紅色  60:紅色  70:黑色
    ----------紅黑樹中序遍歷結果----------
    0:紅色  5:黑色  10:紅色  20:黑色  30:黑色  40:黑色  50:紅色  70:黑色

2.7.12　哈夫曼樹

哈夫曼樹（Huffman Tree）又稱最優二叉樹，是一種帶權路徑長度最短的樹。

1．哈夫曼樹的由來

假設有這樣一個場景：某學校期末考試成績分為5個等級，分別是：成績大于等于90分的為A，成績大于等于80分且小于90分的為B，成績大于等于70分且小于80分的為C，成績大于等于60分且小于70分的為D，成績未達到60分的為E。

上述場景可以使用一棵二叉樹來表示，如圖2-103所示。

圖2-103　二叉樹表示學生成績示意圖

假設該校有10 000名學生，成績分布情況為：5%的學生取得成績E，15%的學生取得成績D，40%的學生取得成績C，30%的學生取得成績B，10%的學生取得成績A。因此，在10 000個學生的樣本中，在圖2-103所示的二叉樹中，查詢每個學生的成績需要查詢的次數如下：

    （5%×1 + 15%×2 + 40%×3 + 30%×4 + 10%×4）× 10000 = 31500次

將圖2-103所示的二叉樹調整為圖2-104所示的二叉樹，重新計算查詢次數。

圖2-104　學生成績二叉樹修正示意圖

在圖2-104所示的二叉樹中，查詢每個學生的成績需要查詢的次數如下：

    （5%×3 + 15%×3 + 40%×2 + 30%×2 + 10×2）× 10000 = 22000次

由以上計算結果可知，哈夫曼樹就是這樣一種效率最高的判別樹。

2．哈夫曼樹的特性

若給二叉樹中的結點賦予一個有意義的數值，則這個數值稱為該結點的權。從根結點到該結點的路徑長度與該結點的權的乘積稱為結點的帶權路徑長度。

樹的帶權路徑長度規定為所有葉子結點的帶權路徑長度之和，記為WPL。

在權為w1,w2,…,wn的N個葉子結點組成的所有二叉樹中，帶權路徑長度WPL最小的二叉樹稱為哈夫曼樹或最優二叉樹。

哈夫曼樹具有以下特性：

（1）滿二叉樹不一定是哈夫曼樹。

（2）哈夫曼樹中權越大的葉子離根越近。

（3）相同帶權結點生成的哈夫曼樹不唯一。

（4）哈夫曼樹的結點的度數為0或2，沒有度為1的結點。

（5）包含n個葉子結點的哈夫曼樹中共有2n–1個結點。

（6）包含n棵樹的森林要經過n–1次合并才能形成哈夫曼樹，共產生n–1個新結點。

3．哈夫曼樹的構建

下面通過權值集合{7,19,2,6,32,3,21,10}闡述哈夫曼樹的構造過程。

（1）根據權值集合構建N棵二叉樹的集合，其中每棵二叉樹只有一個結點，如圖2-105所示。

圖2-105　構建哈夫曼樹步驟（1）示意圖

（2）在步驟（1）中選擇兩棵根結點權值最小的二叉樹作為左右子樹，構造一顆新的二叉樹，將新的二叉樹的根結點的權值設置為左右子樹根結點的權值之和，將左右子樹從二叉樹集合中刪除，新的二叉樹加入二叉樹集合。合并根結點為2和3的兩棵二叉樹，如圖2-106所示。

圖2-106　構建哈夫曼樹步驟（2）示意圖

（3）重復步驟（2），在圖2-106所示的二叉樹集合中，合并根結點為5和6的這兩棵二叉樹，如圖2-107所示。

圖2-107　構建哈夫曼樹步驟（3）示意圖

（4）合并根結點為7和10的這兩棵二叉樹，如圖2-108所示。

圖2-108　構建哈夫曼樹步驟（4）示意圖

（5）合并根結點為11和17的這兩棵二叉樹，如圖2-109所示。

圖2-109　構建哈夫曼樹步驟（5）示意圖

（6）合并根結點為19和21的這兩棵二叉樹，如圖2-110所示。

（7）合并根結點為28和32的這兩棵二叉樹，如圖2-111所示。

圖2-110　構建哈夫曼樹步驟（6）示意圖

圖2-111　構建哈夫曼樹步驟（7）示意圖

（8）合并根結點為40和60的這兩棵二叉樹，如圖2-112所示。

圖2-112　構建哈夫曼樹步驟（8）示意圖

4．哈夫曼編碼

哈夫曼樹的應用很廣，哈夫曼編碼就是哈夫曼樹在電信通信中的應用之一。哈夫曼樹廣泛地用于數據文件壓縮，其壓縮率通常為20%～90%。在電信通信業務中，通常用二進制編碼來表示字母或其他字符，并用這樣的編碼來表示字符序列。

下面通過案例說明使用哈夫曼樹設計哈夫曼編碼的過程。

如需傳送的電文為“ABACCDA”，即：A、B、C、D的頻率（權值）分別為0.43、0.14、0.29、0.14，嘗試構造電文的哈夫曼編碼。

以電文中的字符作為葉子結點構造哈夫曼樹。然后將哈夫曼樹中的結點引向其左孩子的分支標記“0”，引向其右孩子的分支標記“1”，每個字符的編碼即為從根到每個葉子的路徑上得到的0、1序列。電文為“ABACCDA”生成的哈夫曼樹如圖2-113所示。

圖2-113　電文生成的哈夫曼樹示意圖

5．哈夫曼樹的實現

在構造哈夫曼樹的過程中，每次調整都是合并權重值最小的兩個結點。因此，在本書的哈夫曼樹的實現過程中，使用繼承Comparable接口的Node結點，方便對結點進行排序，讀者亦可選擇其他算法代替。

創建哈夫曼樹的測試類，用于驗證哈夫曼樹的功能：

測試類中維護了一棵如圖2-114所示的哈夫曼樹。

圖2-114　電文生成的哈夫曼樹示意圖

執行測試代碼，執行結果如下：

    ----------哈夫曼樹中序遍歷----------
    1 3 2 6 3 15 4 9 5
    ----------哈夫曼編碼結果----------
    1被編碼成000
    2被編碼成001
    3被編碼成01
    4被編碼成10
    5被編碼成11

2.7.13　樹常見面試考點

（1）二叉樹的概念。

（2）二叉樹的存儲。

（3）二叉樹的遍歷。

·　前序遍歷。

·　中序遍歷。

·　后序遍歷。

·　層次遍歷。

（4）二叉排序樹的實現及其優缺點。

（5）AVL樹的優缺點。

（6）紅黑樹的原理及JDK對紅黑樹的應用。

（7）哈夫曼的編碼及解碼。