40節介紹了HashMap，41節介紹了HashSet，它們的共同實現機制是哈希表，一個共同的限制是沒有順序，我們提到，它們都有一個能保持順序的對應類TreeMap和TreeSet，這兩個類的共同實現基礎是排序二叉樹，為了更好的理解TreeMap/TreeSet，本節我們先來介紹排序二叉樹的一些基本概念和算法。
基本概念
先來說樹的概念，現實中，樹是從下往上長的，樹會分叉，在計算機程序中，一般而言，與現實相反，樹是從上往下長的，也會分叉，有個根節點，每個節點可以有一個或多個孩子節點，沒有孩子節點的節點一般稱為葉子節點。
二叉樹是一個樹，但，每個節點最多有兩個孩子節點，一左一右，左邊的稱為左孩子，右邊的稱為右孩子，我們看兩個例子，如下所示：
這兩棵樹都是二叉樹，左邊的根節點為5，除了葉子節點外，每個節點都有兩個孩子節點，右邊的根節點為7，有的節點有兩個孩子節點，有的只有一個。
樹有一個高度或深度的概念，是從根到葉子節點經過的節點個數的最大值，左邊樹的高度為3，右邊的為5。
排序二叉樹也是二叉樹，但，它沒有重復元素，而且是有序的二叉樹，什麼順序呢？對每個節點而言：
上面的兩顆二叉樹都是排序二叉樹。比如說左邊的樹，根節點為5，左邊的都小於5，右邊的都大於5。再看右邊的樹，根節點為7，左邊的都小於7，右邊的都大於7，在以3為根的左子樹中，其右子樹的值都大於3。
排序二叉樹有什麼優點？如何在樹中進行基本操作如查找、遍歷、插入和刪除呢？我們來看一下基本的算法。
基本算法
查找
排序二叉樹有一個很好的優點，在其中查找一個元素是很方便、也很高效的，基本步驟為：
這個步驟與在數組中進行二分查找或者說折半查找的思路是類似的，如果二叉樹是比較平衡的，類似上圖中左邊的二叉樹，則每次比較都能將比較范圍縮小一半，效率很高。
此外，在排序二叉樹中，可以方便的查找最小最大值，最小值即為最左邊的節點，從根節點一路查找左孩子即可，最大值即為最右邊的節點，從根節點一路查找右孩子即可。
遍歷
排序二叉樹也可以方便的按序遍歷，用遞歸的方式，用如下算法即可按序遍歷：
比如，遍歷訪問下面的二叉樹：
從根節點開始，但先訪問根節點的左子樹，一直到最左邊的節點，所以第一個訪問的是1，1沒有右子樹，返回上一層，訪問3，然後訪問3的右子樹，4沒有左子樹，所以訪問4，然後是4的右子樹6，依次類推，訪問順序就是有序的：1 3 4 6 7 8 9。
不用遞歸的方式，也可以實現按序遍歷，第一個節點為最左邊的節點，從第一個節點開始，依次找後繼節點。給定一個節點，找其後繼節點的算法為：
文字描述比較抽象，我們來看個圖，以上圖為例，每個節點的後繼如下圖綠色箭頭所示：
對每個節點，對照算法，我們再詳細解釋下：
怎麼構建排序二叉樹呢？可以在插入、刪除元素的過程中形成和保持。
插入
在排序二叉樹中，插入元素首先要找插入位置，即新節點的父節點，怎麼找呢？與查找元素類似，從根節點開始往下找，其步驟為：
找到父節點後，即可插入，如果插入元素小於父節點，則作為左孩子插入，否則作為右孩子插入。
我們來看個例子，依次插入7, 3, 4, 1, 9, 6, 8的過程，這個過程如下圖所示：
刪除
從排序二叉樹中刪除一個節點要復雜一些，有三種情況：
我們分別來看下。
如果節點為葉子節點，則很簡單，可以直接刪掉，修改父節點的對應孩子為空即可。
如果節點只有一個孩子節點，則替換待刪節點為孩子節點，或者說，在孩子節點和父節點之間直接建立鏈接。比如說，在下圖中，左邊二叉樹中刪除節點4，就是讓4的父節點3與4的孩子節點6直接建立鏈接。
如果節點有兩個孩子，則首先找該節點的後繼（根據之前介紹的後繼算法，後繼為右子樹中最小的節點，這個後繼一定沒有左孩子），找到後繼後，替換待刪節點為後繼的內容，然後再刪除後繼節點。後繼節點沒有左孩子，這就將兩個孩子的情況轉換為了葉子節點或只有一個孩子的情況。
比如說，在下圖中，從左邊二叉樹中刪除節點3，3有兩個孩子，後繼為4，首先替換3的內容為4，然後再刪除節點4。
平衡的排序二叉樹
從前面的描述中可以看出，排序二叉樹的形狀與插入和刪除的順序密切相關，極端情況下，排序二叉樹可能退化為一個鏈表，比如說，如果插入順序為：1 3 4 6 7 8 9，則排序二叉樹形狀為：
退化為鏈表後，排序二叉樹的優點就都沒有了，即使沒有退化為鏈表，如果排序二叉樹高度不平衡，效率也會變的很低。
平衡具體定義是什麼呢？有一種高度平衡的定義，即任何節點的左右子樹的高度差最多為一。滿足這個平衡定義的排序二叉樹又被稱為AVL樹，這個名字源於它的發明者G.M. Adelson-Velsky 和 E.M. Landis，在他們的算法中，在插入和刪除節點時，通過一次或多次旋轉操作來重新平衡樹。
在TreeMap的實現中，用的並不是AVL樹，而是紅黑樹，與AVL樹類似，紅黑樹也是一種平衡的排序二叉樹，也是在插入和刪除節點時通過旋轉操作來平衡的，但它並不是高度平衡的，而是大致平衡的，所謂大致是指，它確保，對於任意一條從根到葉子節點的路徑，沒有任何一條路徑的長度會比其他路徑長過兩倍。紅黑樹減弱了對平衡的要求，但降低了保持平衡需要的開銷，在實際應用中，統計性能高於AVL樹。
為什麼叫紅黑樹呢？因為它對每個節點進行著色，顏色或黑或紅，並對節點的著色有一些約束，滿足這個約束即可以確保樹是大致平衡的。
對AVL樹和紅黑樹，它們保持平衡的細節都是比較復雜的，我們就不介紹了，我們需要知道的就是，它們都是排序二叉樹，都通過在插入和刪除時執行開銷不大的旋轉操作保持了樹的高度平衡或大致平衡，從而保證了樹的查找效率。
小結
本節介紹了排序二叉樹的基本概念和算法。
排序二叉樹保持了元素的順序，而且是一種綜合效率很高的數據結構，基本的保存、刪除、查找的效率都為O(h)，h為樹的高度，在樹平衡的情況下，h為log2(N)，N為節點數，比如，如果N為1024，則log2(N)為10。
基本的排序二叉樹不能保證樹的平衡，可能退化為一個鏈表，有很多保持樹平衡的算法，AVL樹是第一個，能保證樹的高度平衡，但紅黑樹是實際中使用更為廣泛的，雖然只能保證大致平衡，但降低了維持樹平衡需要的開銷，整體統計效果更好。
與哈希表一樣，樹也是計算機程序中一種重要的數據結構和思維方式。為了能夠快速操作數據，哈希和樹是兩種基本的思維方式，不需要順序，優先考慮哈希，需要順序，考慮樹。除了容器類TreeMap/TreeSet，數據庫中的索引結構也是基於樹的（不過基於B樹，而不是二叉樹），而索引是能夠在大量數據中快速訪問數據的關鍵。
理解了排序二叉樹的基本概念和算法，理解TreeMap和TreeSet就比較容易了，讓我們在接下來的兩節中探討這兩個類。
---------------
未完待續，查看最新文章，敬請關注微信公眾號“老馬說編程”(掃描下方二維碼)，從入門到高級，深入淺出，老馬和你一起探索Java編程及計算機技術的本質。用心原創，保留所有版權。
