treemap 的實作就是紅黑樹資料結構，也就說是一棵自平衡的排序二叉樹，這樣就可以保證當需要快速檢索指定節點。
的關系
為了讓大家了解 treemap 和 treeset 之間的關系，下面先看 treeset 類的部分源代碼：
從上面代碼可以看出，treeset 的 ① 号、② 号構造器的都是建立一個 treemap 作為實際存儲 set 元素的容器，而另外 2 個構造器則分别依賴于 ① 号和 ② 号構造器，由此可見，treeset 底層實際使用的存儲容器就是 treemap。
與 hashset 完全類似的是，treeset 裡絕大部分方法都是直接調用 treemap 的方法來實作的，這一點讀者可以自行參閱 treeset 的源代碼，此處就不再給出了。
對于 treemap 而言，它采用一種被稱為“紅黑樹”的排序二叉樹來儲存 map 中每個 entry —— 每個 entry 都被當成“紅黑樹”的一個節點對待。例如對于如下程式而言：
當程式執行 map.put("ccc" , 89.0); 時，系統将直接把 "ccc"-89.0 這個 entry 放入 map 中，這個 entry 就是該“紅黑樹”的根節點。接着程式執行 map.put("aaa" , 80.0); 時，程式會将 "aaa"-80.0 作為新節點添加到已有的紅黑樹中。
以後每向 treemap 中放入一個 key-value 對，系統都需要将該 entry 當成一個新節點，添加成已有紅黑樹中，通過這種方式就可保證 treemap 中所有 key 總是由小到大地排列。例如我們輸出上面程式，将看到如下結果（所有 key 由小到大地排列）：
<a target="_blank"></a>
紅黑樹是一種自平衡排序二叉樹，樹中每個節點的值，都大于或等于在它的左子樹中的所有節點的值，并且小于或等于在它的右子樹中的所有節點的值，這確定紅黑樹運作時可以快速地在樹中查找和定位的所需節點。
對于 treemap 而言，由于它底層采用一棵“紅黑樹”來儲存集合中的 entry，這意味這 treemap 添加元素、取出元素的性能都比 hashmap 低：當 treemap 添加元素時，需要通過循環找到新增 entry 的插入位置，是以比較耗性能；當從 treemap 中取出元素時，需要通過循環才能找到合适的 entry，也比較耗性能。但 treemap、treeset 比 hashmap、hashset 的優勢在于：treemap 中的所有 entry 總是按 key 根據指定排序規則保持有序狀态，treeset
中所有元素總是根據指定排序規則保持有序狀态。
為了了解 treemap 的底層實作，必須先介紹排序二叉樹和紅黑樹這兩種資料結構。其中紅黑樹又是一種特殊的排序二叉樹。
排序二叉樹是一種特殊結構的二叉樹，可以非常友善地對樹中所有節點進行排序和檢索。
排序二叉樹要麼是一棵空二叉樹，要麼是具有下列性質的二叉樹：
若它的左子樹不空，則左子樹上所有節點的值均小于它的根節點的值；
若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；
它的左、右子樹也分别為排序二叉樹。
圖 1 顯示了一棵排序二叉樹：
對排序二叉樹，若按中序周遊就可以得到由小到大的有序序列。如圖 1 所示二叉樹，中序周遊得：
建立排序二叉樹的步驟，也就是不斷地向排序二叉樹添加節點的過程，向排序二叉樹添加節點的步驟如下：
以根節點目前節點開始搜尋。
拿新節點的值和目前節點的值比較。
如果新節點的值更大，則以目前節點的右子節點作為新的目前節點；如果新節點的值更小，則以目前節點的左子節點作為新的目前節點。
重複 2、3 兩個步驟，直到搜尋到合适的葉子節點為止。
将新節點添加為第 4 步找到的葉子節點的子節點；如果新節點更大，則添加為右子節點；否則添加為左子節點。
掌握上面理論之後，下面我們來分析 treemap 添加節點（treemap 中使用 entry 内部類代表節點）的實作，treemap 集合的 put(k key, v value) 方法實作了将 entry 放入排序二叉樹中，下面是該方法的源代碼：
上面程式中粗體字代碼就是實作“排序二叉樹”的關鍵算法，每當程式希望添加新節點時：系統總是從樹的根節點開始比較 —— 即将根節點當成目前節點，如果新增節點大于目前節點、并且目前節點的右子節點存在，則以右子節點作為目前節點；如果新增節點小于目前節點、并且目前節點的左子節點存在，則以左子節點作為目前節點；如果新增節點等于目前節點，則用新增節點覆寫目前節點，并結束循環 —— 直到找到某個節點的左、右子節點不存在，将新節點添加該節點的子節點 —— 如果新節點比該節點大，則添加為右子節點；如果新節點比該節點小，則添加為左子節點。
當程式從排序二叉樹中删除一個節點之後，為了讓它依然保持為排序二叉樹，程式必須對該排序二叉樹進行維護。維護可分為如下幾種情況：
（1）被删除的節點是葉子節點，則隻需将它從其父節點中删除即可。
（2）被删除節點 p 隻有左子樹，将 p 的左子樹 pl 添加成 p 的父節點的左子樹即可；被删除節點 p 隻有右子樹，将 p 的右子樹 pr 添加成 p 的父節點的右子樹即可。
（3）若被删除節點 p 的左、右子樹均非空，有兩種做法：
将 pl 設為 p 的父節點 q 的左或右子節點（取決于 p 是其父節點 q 的左、右子節點），将 pr 設為 p 節點的中序前趨節點 s 的右子節點（s 是 pl 最右下的節點，也就是 pl 子樹中最大的節點）。
以 p 節點的中序前趨或後繼替代 p 所指節點，然後再從原排序二叉樹中删去中序前趨或後繼節點即可。（也就是用大于 p 的最小節點或小于 p 的最大節點代替 p 節點即可）。
圖 2 顯示了被删除節點隻有左子樹的示意圖：
圖 3 顯示了被删除節點隻有右子樹的示意圖：
圖 4 顯示了被删除節點既有左子節點，又有右子節點的情形，此時我們采用到是第一種方式進行維護：
圖 5 顯示了被删除節點既有左子樹，又有右子樹的情形，此時我們采用到是第二種方式進行維護：
treemap 删除節點采用圖 5 所示右邊的情形進行維護——也就是用被删除節點的右子樹中最小節點與被删節點交換的方式進行維護。
treemap 删除節點的方法由如下方法實作：
排序二叉樹雖然可以快速檢索，但在最壞的情況下：如果插入的節點集本身就是有序的，要麼是由小到大排列，要麼是由大到小排列，那麼最後得到的排序二叉樹将變成連結清單：所有節點隻有左節點（如果插入節點集本身是大到小排列）；或所有節點隻有右節點（如果插入節點集本身是小到大排列）。在這種情況下，排序二叉樹就變成了普通連結清單，其檢索效率就會很差。
為了改變排序二叉樹存在的不足，rudolf bayer 與 1972 年發明了另一種改進後的排序二叉樹：紅黑樹，他将這種排序二叉樹稱為“對稱二叉 b 樹”，而紅黑樹這個名字則由 leo j. guibas 和 robert sedgewick 于 1978 年首次提出。
紅黑樹是一個更高效的檢索二叉樹，是以常常用來實作關聯數組。典型地，jdk 提供的集合類 treemap 本身就是一個紅黑樹的實作。
紅黑樹在原有的排序二叉樹增加了如下幾個要求：
上面的性質 3 中指定紅黑樹的每個葉子節點都是空節點，而且并葉子節點都是黑色。但 java 實作的紅黑樹将使用 null 來代表空節點，是以周遊紅黑樹時将看不到黑色的葉子節點，反而看到每個葉子節點都是紅色的。
性質 1：每個節點要麼是紅色，要麼是黑色。
性質 2：根節點永遠是黑色的。
性質 3：所有的葉節點都是空節點（即 null），并且是黑色的。
性質 4：每個紅色節點的兩個子節點都是黑色。（從每個葉子到根的路徑上不會有兩個連續的紅色節點）
性質 5：從任一節點到其子樹中每個葉子節點的路徑都包含相同數量的黑色節點。
java 中實作的紅黑樹可能有如圖 6 所示結構：
備注：本文中所有關于紅黑樹中的示意圖采用白色代表紅色。黑色節點還是采用了黑色表示。
根據性質 5：紅黑樹從根節點到每個葉子節點的路徑都包含相同數量的黑色節點，是以從根節點到葉子節點的路徑中包含的黑色節點數被稱為樹的“黑色高度（black-height）”。
性質 4 則保證了從根節點到葉子節點的最長路徑的長度不會超過任何其他路徑的兩倍。假如有一棵黑色高度為 3 的紅黑樹：從根節點到葉節點的最短路徑長度是 2，該路徑上全是黑色節點（黑節點 - 黑節點 - 黑節點）。最長路徑也隻可能為 4，在每個黑色節點之間插入一個紅色節點（黑節點 - 紅節點 - 黑節點 - 紅節點 - 黑節點），性質 4 保證絕不可能插入更多的紅色節點。由此可見，紅黑樹中最長路徑就是一條紅黑交替的路徑。
紅黑樹并不是真正的平衡二叉樹，但在實際應用中，紅黑樹的統計性能要高于平衡二叉樹，但極端性能略差。
由此我們可以得出結論：對于給定的黑色高度為 n 的紅黑樹，從根到葉子節點的最短路徑長度為 n-1，最長路徑長度為 2 * (n-1)。
提示：排序二叉樹的深度直接影響了檢索的性能，正如前面指出，當插入節點本身就是由小到大排列時，排序二叉樹将變成一個連結清單，這種排序二叉樹的檢索性能最低：n 個節點的二叉樹深度就是 n-1。
紅黑樹通過上面這種限制來保證它大緻是平衡的——因為紅黑樹的高度不會無限增高，這樣保證紅黑樹在最壞情況下都是高效的，不會出現普通排序二叉樹的情況。
由于紅黑樹隻是一個特殊的排序二叉樹，是以對紅黑樹上的隻讀操作與普通排序二叉樹上的隻讀操作完全相同，隻是紅黑樹保持了大緻平衡，是以檢索性能比排序二叉樹要好很多。
但在紅黑樹上進行插入操作和删除操作會導緻樹不再符合紅黑樹的特征，是以插入操作和删除操作都需要進行一定的維護，以保證插入節點、删除節點後的樹依然是紅黑樹。
上面 <code>put(k key, v value) 方法中①</code><code>号代碼處使用</code><code>fixafterinsertion(e) 方法來修複紅黑樹——是以每次插入節點後必須進行簡單修複，使該排序二叉樹滿足紅黑樹的要求。</code>
插入操作按如下步驟進行：
（1）以排序二叉樹的方法插入新節點，并将它設為紅色。
（2）進行顔色調換和樹旋轉。
在插入操作中，紅黑樹的性質 1 和性質 3 兩個永遠不會發生改變，是以無需考慮紅黑樹的這兩個特性。
這種顔色調用和樹旋轉就比較複雜了，下面将分情況進行介紹。在介紹中，我們把新插入的節點定義為 n 節點，n 節點的父節點定義為 p 節點，p 節點的兄弟節點定義為 u 節點，p 節點父節點定義為 g 節點。
下面分成不同情形來分析插入操作
情形 1：新節點 n 是樹的根節點，沒有父節點
在這種情形下，直接将它設定為黑色以滿足性質 2。
情形 2：新節點的父節點 p 是黑色
在這種情況下，新插入的節點是紅色的，是以依然滿足性質 4。而且因為新節點 n 有兩個黑色葉子節點；但是由于新節點 n 是紅色，通過它的每個子節點的路徑依然保持相同的黑色節點數，是以依然滿足性質 5。
情形 3：如果父節點 p 和父節點的兄弟節點 u 都是紅色
在這種情況下，程式應該将 p 節點、u 節點都設定為黑色，并将 p 節點的父節點設為紅色（用來保持性質 5）。現在新節點 n 有了一個黑色的父節點 p。由于從 p 節點、u 節點到根節點的任何路徑都必須通過 g 節點，在這些路徑上的黑節點數目沒有改變（原來有葉子和 g 節點兩個黑色節點，現在有葉子和 p 兩個黑色節點）。
經過上面處理後，紅色的 g 節點的父節點也有可能是紅色的，這就違反了性質 4，是以還需要對 g 節點遞歸地進行整個過程（把 g 當成是新插入的節點進行處理即可）。
圖 7 顯示了這種處理過程：
備注：雖然圖 11.28 繪制的是新節點 n 作為父節點 p 左子節點的情形，其實新節點 n 作為父節點 p 右子節點的情況與圖 11.28 完全相同。
情形 4：父節點 p 是紅色、而其兄弟節點 u 是黑色或缺少；且新節點 n 是父節點 p 的右子節點，而父節點 p 又是其父節點 g 的左子節點。
在這種情形下，我們進行一次左旋轉對新節點和其父節點進行，接着按情形 5 處理以前的父節點 p（也就是把 p 當成新插入的節點即可）。這導緻某些路徑通過它們以前不通過的新節點 n 或父節點 p 的其中之一，但是這兩個節點都是紅色的，是以不會影響性質 5。
圖 8 顯示了對情形 4 的處理：
備注：圖 11.29 中 p 節點是 g 節點的左子節點，如果 p 節點是其父節點 g 節點的右子節點，那麼上 面的處理情況應該左、右對調一下。
情形 5：父節點 p 是紅色、而其兄弟節點 u 是黑色或缺少；且新節點 n 是其父節點的左子節點，而父節點 p 又是其父節點 g 的左子節點。
在這種情形下，需要對節點 g 的一次右旋轉，在旋轉産生的樹中，以前的父節點 p 現在是新節點 n 和節點 g 的父節點。由于以前的節點 g 是黑色，否則父節點 p 就不可能是紅色，我們切換以前的父節點 p 和節點 g 的顔色，使之滿足性質 4，性質 5 也仍然保持滿足，因為通過這三個節點中任何一個的所有路徑以前都通過節點 g，現在它們都通過以前的父節點 p。在各自的情形下，這都是三個節點中唯一的黑色節點。
圖 9 顯示了情形 5 的處理過程：
備注：圖 11.30 中 p 節點是 g 節點的左子節點，如果 p 節點是其父節點 g 節點的右子節點，那麼上面的處理情況應該左、右對調一下。
treemap 為插入節點後的修複操作由 fixafterinsertion(entry<k,v> x) 方法提供，該方法的源代碼如下：
與添加節點之後的修複類似的是，treemap 删除節點之後也需要進行類似的修複操作，通過這種修複來保證該排序二叉樹依然滿足紅黑樹特征。大家可以參考插入節點之後的修複來分析删除之後的修複。treemap 在删除之後的修複操作由 fixafterdeletion(entry<k,v> x) 方法提供，該方法源代碼如下：
當 treemap 根據 key 來取出 value 時，treemap 對應的方法如下：
從上面程式的粗體字代碼可以看出，get(object key) 方法實質是由于 getentry() 方法實作的，這個 getentry() 方法的代碼如下：
上面的 getentry(object obj) 方法也是充分利用排序二叉樹的特征來搜尋目标 entry，程式依然從二叉樹的根節點開始，如果被搜尋節點大于目前節點，程式向“右子樹”搜尋；如果被搜尋節點小于目前節點，程式向“左子樹”搜尋；如果相等，那就是找到了指定節點。
當 treemap 裡的 comparator != null 即表明該 treemap 采用了定制排序，在采用定制排序的方式下，treemap 采用 getentryusingcomparator(key) 方法來根據 key 擷取 entry。下面是該方法的代碼：
其實 getentry、getentryusingcomparator 兩個方法的實作思路完全類似，隻是前者對自然排序的 treemap 擷取有效，後者對定制排序的 treemap 有效。
通過上面源代碼的分析不難看出，treemap 這個工具類的實作其實很簡單。或者說：從内部結構來看，treemap 本質上就是一棵“紅黑樹”，而 treemap 的每個 entry 就是該紅黑樹的一個節點。