瘋狂Java學習筆記（40）----------TreeMap和TreeSet

瘋狂Java學習筆記（40）----------TreeMap和TreeSet

看這篇博客前，我覺得很有必要先看下我之前的幾篇博客

Red-Black Trees（紅黑樹）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（TreeMap底層的實現就是用的紅黑樹數據結構）

探索equals()和hashCode()方法? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?（TreeMap/TreeSet實現使用到的核心方法）

java中的HashTable,HashMap和HashSet? ? ? （同為java集合類，對比下他們的區別）

java中Map,List與Set的區別? ? ? ? ? ? ? ? ? ? ? ? ?（TreeMap/TreeSet最主要的區別就是分別實現了Map和Set接口）

TreeMap 和 TreeSet 是 Java Collection Framework 的兩個重要成員，其中 TreeMap 是 Map 接口的常用實現類，而? TreeSet 是 Set 接口的常用實現類。雖然?TreeMap?和?TreeSet?實現的接口規范不同，但 TreeSet 底層是通過 TreeMap 來實現的（如同HashSet底層是是通過HashMap來實現的一樣），因此二者的實現方式完全一樣。而 TreeMap 的實現就是紅黑樹算法。

1. TreeSet和TreeMap的關系

-----------------------------------------------------

與HashSet完全類似，TreeSet里面絕大部分方法都市直接調用TreeMap方法來實現的。

相同點：

TreeMap和TreeSet都是有序的集合，也就是說他們存儲的值都是拍好序的。

TreeMap和TreeSet都是非同步集合，因此他們不能在多線程之間共享，不過可以使用方法Collections.synchroinzedMap()來實現同步

運行速度都要比Hash集合慢，他們內部對元素的操作時間復雜度為O(logN)，而HashMap/HashSet則為O(1)。

不同點：

最主要的區別就是TreeSet和TreeMap非別實現Set和Map接口

TreeSet只存儲一個對象，而TreeMap存儲兩個對象Key和Value（僅僅key對象有序）

TreeSet中不能有重復對象，而TreeMap中可以存在

理解了這些之后我們發現其實兩者底層的實現方法還是一致的，所以下面我們只需要分析TreeMap,基本上就弄懂了TreeSet。

2. TreeSet實現原理

-------------------------------------------------------

public class TreeMapTest {

public static void main(String[] args) {

TreeMap map = new TreeMap();

map.put("ccc" , 89.0);

map.put("aaa" , 80.0);

map.put("zzz" , 80.0);

map.put("bbb" , 89.0);

System.out.println(map);

}

}

當程序執行 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 由小到大地排列）：

{aaa=80.0, bbb=89.0, ccc=89.0, zzz=80.0}

TreeMap的添加節點（put()方法）

對于 TreeMap 而言，由于它底層采用一棵“紅黑樹”來保存集合中的 Entry，這意味這 TreeMap 添加元素、取出元素的性能都比 HashMap 低（紅黑樹和Hash數據結構上的區別）：當 TreeMap 添加元素時，需要通過循環找到新增 Entry 的插入位置，因此比較耗性能；當從 TreeMap 中取出元素時，需要通過循環才能找到合適的 Entry，也比較耗性能。但 TreeMap、TreeSet 比 HashMap、HashSet 的優勢在于：TreeMap 中的所有 Entry 總是按 key 根據指定排序規則保持有序狀態，TreeSet 中所有元素總是根據指定排序規則保持有序狀態。

為了很好的理解TreeMap你必須先理解紅黑樹，然而紅黑樹又是一種特殊的二叉查找樹，所以你必須先看兩篇博客

Binary search tree（二叉查找樹）

Red-Black Trees（紅黑樹）

因為我這兩篇博客已經講了很多相關知識，所以這里就不列出來了。

掌握紅黑樹數據結構的理論之后，我們來分析TreeMap添加節點（TreeMap 中使用 Entry 內部類代表節點）的實現，TreeMap 集合的 put(K key, V value) 方法實現了將 Entry 放入排序二叉樹中，下面是該方法的源代碼：

public V put(K key, V value)

{

// 先以 t 保存鏈表的 root 節點

Entry t = root;

// 如果 t==null，表明是一個空鏈表，即該 TreeMap 里沒有任何 Entry

if (t == null)

{

// 將新的 key-value 創建一個 Entry，并將該 Entry 作為 root

root = new Entry(key, value, null);

// 設置該 Map 集合的 size 為 1，代表包含一個 Entry

size = 1;

// 記錄修改次數為 1

modCount++;

return null;

}

int cmp;

Entry parent;

Comparator cpr = comparator;

// 如果比較器 cpr 不為 null，即表明采用定制排序

if (cpr != null)

{

do {

// 使用 parent 上次循環后的 t 所引用的 Entry

parent = t;

// 拿新插入 key 和 t 的 key 進行比較

cmp = cpr.compare(key, t.key);

// 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點

if (cmp < 0)

t = t.left;

// 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點

else if (cmp > 0)

t = t.right;

// 如果兩個 key 相等，新的 value 覆蓋原有的 value，

// 并返回原有的 value

else

return t.setValue(value);

} while (t != null);

}

else

{

if (key == null)

throw new NullPointerException();

Comparable k = (Comparable) key;

do {

// 使用 parent 上次循環后的 t 所引用的 Entry

parent = t;

// 拿新插入 key 和 t 的 key 進行比較

cmp = k.compareTo(t.key);

// 如果新插入的 key 小于 t 的 key，t 等于 t 的左邊節點

if (cmp < 0)

t = t.left;

// 如果新插入的 key 大于 t 的 key，t 等于 t 的右邊節點

else if (cmp > 0)

t = t.right;

// 如果兩個 key 相等，新的 value 覆蓋原有的 value，

// 并返回原有的 value

else

return t.setValue(value);

} while (t != null);

}

// 將新插入的節點作為 parent 節點的子節點

Entry e = new Entry(key, value, parent);

// 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的左子節點

if (cmp < 0)

parent.left = e;

// 如果新插入 key 小于 parent 的 key，則 e 作為 parent 的右子節點

else

parent.right = e;

// 修復紅黑樹

fixAfterInsertion(e); // ①

size++;

modCount++;

return null;

}

上面這段代碼看起來復雜其實不然，本質上就是紅黑樹德元素插入操作的代碼。看下面紅黑樹插入操作的偽代碼

對比下兩個你會發現其實就是一樣的，所以如果你這里不理解的話，要先回去看下紅黑樹的知識哦，理解之后，你會發現很簡單

。關于最后的紅黑樹修復操作fixAfterInsertion(e) 我那篇博客中有詳細講，由于篇幅比較多，就不重新寫了。

TreeMap的刪除節點

同樣原理還是紅黑樹節點的刪除，那篇博客也有詳細講解。這里只給出deleteEntry源碼

private void deleteEntry(Entry p)

{

modCount++;

size--;

// 如果被刪除節點的左子樹、右子樹都不為空

if (p.left != null && p.right != null)

{

// 用 p 節點的中序后繼節點代替 p 節點

Entry s = successor (p);

p.key = s.key;

p.value = s.value;

p = s;

}

// 如果 p 節點的左節點存在，replacement 代表左節點；否則代表右節點。

Entry replacement = (p.left != null ? p.left : p.right);

if (replacement != null)

{

replacement.parent = p.parent;

// 如果 p 沒有父節點，則 replacemment 變成父節點

if (p.parent == null)

root = replacement;

// 如果 p 節點是其父節點的左子節點

else if (p == p.parent.left)

p.parent.left = replacement;

// 如果 p 節點是其父節點的右子節點

else

p.parent.right = replacement;

p.left = p.right = p.parent = null;

// 修復紅黑樹

if (p.color == BLACK)

fixAfterDeletion(replacement); // ①

}

// 如果 p 節點沒有父節點

else if (p.parent == null)

{

root = null;

}

else

{

if (p.color == BLACK)

// 修復紅黑樹

fixAfterDeletion(p); // ②

if (p.parent != null)

{

// 如果 p 是其父節點的左子節點

if (p == p.parent.left)

p.parent.left = null;

// 如果 p 是其父節點的右子節點

else if (p == p.parent.right)

p.parent.right = null;

p.parent = null;

}

}

}

檢索節點

當 TreeMap 根據 key 來取出 value 時，TreeMap 對應的方法如下：

public V get(Object key)

{

// 根據指定 key 取出對應的 Entry

Entry>K,V< p = getEntry(key);

// 返回該 Entry 所包含的 value

return (p==null ? null : p.value);

}

final Entry getEntry(Object key)

{

// 如果 comparator 不為 null，表明程序采用定制排序

if (comparator != null)

// 調用 getEntryUsingComparator 方法來取出對應的 key

return getEntryUsingComparator(key);

// 如果 key 形參的值為 null，拋出 NullPointerException 異常

if (key == null)

throw new NullPointerException();

// 將 key 強制類型轉換為 Comparable 實例

Comparable k = (Comparable) key;

// 從樹的根節點開始

Entry p = root;

while (p != null)

{

// 拿 key 與當前節點的 key 進行比較

int cmp = k.compareTo(p.key);

// 如果 key 小于當前節點的 key，向“左子樹”搜索

if (cmp < 0)

p = p.left;

// 如果 key 大于當前節點的 key，向“右子樹”搜索

else if (cmp > 0)

p = p.right;

// 不大于、不小于，就是找到了目標 Entry

else

return p;

}

return null;

}

上面的 getEntry(Object obj) 方法也是充分利用排序二叉樹的特征來搜索目標 Entry，程序依然從二叉樹的根節點開始，如果被搜索節點大于當前節點，程序向“右子樹”搜索；如果被搜索節點小于當前節點，程序向“左子樹”搜索；如果相等，那就是找到了指定節點。

當 TreeMap 里的 comparator != null 即表明該 TreeMap 采用了定制排序，在采用定制排序的方式下，TreeMap 采用 getEntryUsingComparator(key) 方法來根據 key 獲取 Entry。下面是該方法的代碼

final Entry getEntryUsingComparator(Object key)

{

K k = (K) key;

// 獲取該 TreeMap 的 comparator

Comparator cpr = comparator;

if (cpr != null)

{

// 從根節點開始

Entry p = root;

while (p != null)

{

// 拿 key 與當前節點的 key 進行比較

int cmp = cpr.compare(k, p.key);

// 如果 key 小于當前節點的 key，向“左子樹”搜索

if (cmp < 0)

p = p.left;

// 如果 key 大于當前節點的 key，向“右子樹”搜索

else if (cmp > 0)

p = p.right;

// 不大于、不小于，就是找到了目標 Entry

else

return p;

}

}

return null;

}

其實 getEntry、getEntryUsingComparator 兩個方法的實現思路完全類似，只是前者對自然排序的 TreeMap 獲取有效，后者對定制排序的 TreeMap 有效。

通過上面源代碼的分析不難看出，TreeMap 這個工具類的實現其實很簡單。或者說：從內部結構來看，TreeMap 本質上就是一棵“紅黑樹”，而 TreeMap 的每個 Entry 就是該紅黑樹的一個節點。

3. 常見問題

----------------------------------------------

”為什么TreeMap采用紅黑樹而不是二叉查找樹？ “

其實這個問題就是在問紅黑樹相對于排序二叉樹的優點。我們都知道排序二叉樹雖然可以快速檢索，但在最壞的情況下：如果插入的節點集本身就是有序的，要么是由小到大排列，要么是由大到小排列，那么最后得到的排序二叉樹將變成鏈表：所有節點只有左節點（如果插入節點集本身是大到小排列）；或所有節點只有右節點（如果插入節點集本身是小到大排列）。在這種情況下，排序二叉樹就變成了普通鏈表，其檢索效率就會很差。

為了改變排序二叉樹存在的不足，Rudolf Bayer 與 1972 年發明了另一種改進后的排序二叉樹：紅黑樹，他將這種排序二叉樹稱為“對稱二叉 B 樹”，而紅黑樹這個名字則由 Leo J. Guibas 和 Robert Sedgewick 于 1978 年首次提出。

紅黑樹是一個更高效的檢索二叉樹，因此常常用來實現關聯數組。典型地，JDK 提供的集合類 TreeMap 本身就是一個紅黑樹的實現。

紅黑樹在原有的排序二叉樹增加了如下幾個要求：

Java 實現的紅黑樹

上面的性質 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。

紅黑樹通過上面這種限制來保證它大致是平衡的——因為紅黑樹的高度不會無限增高，這樣保證紅黑樹在最壞情況下都是高效的，不會出現普通排序二叉樹的情況。

由于紅黑樹只是一個特殊的排序二叉樹，因此對紅黑樹上的只讀操作與普通排序二叉樹上的只讀操作完全相同，只是紅黑樹保持了大致平衡，因此檢索性能比排序二叉樹要好很多。

但在紅黑樹上進行插入操作和刪除操作會導致樹不再符合紅黑樹的特征，因此插入操作和刪除操作都需要進行一定的維護，以保證插入節點、刪除節點后的樹依然是紅黑樹。

”TreeMap、TreeSet 對比 HashMap、HashSet的優缺點？“

缺點：

對于 TreeMap 而言，由于它底層采用一棵“紅黑樹”來保存集合中的 Entry，這意味這 TreeMap 添加元素、取出元素的性能都比 HashMap?（O(1)）低：

當 TreeMap 添加元素時，需要通過循環找到新增 Entry 的插入位置，因此比較耗性能（O(logN)）

當從 TreeMap 中取出元素時，需要通過循環才能找到合適的 Entry，也比較耗性能（O(logN)）

優點：

TreeMap 中的所有 Entry 總是按 key 根據指定排序規則保持有序狀態，TreeSet 中所有元素總是根據指定排序規則保持有序狀態。

好吧，java集合類的講解就告一段落了，這幾天把重要的Set，List，Map，HashMap，HashSet，TreeMap，TreeSet都講了一遍，不過還要慢慢屢清楚，集合類就先講這些，以后碰到了哪些重要的，還會繼續寫。

本文轉自http://blog.csdn.net/speedme/article/details/22661671

Reference：

http://www.ibm.com/developerworks/cn/java/j-lo-tree/index.html

http://shmilyaw-hotmail-com.iteye.com/blog/1836431

http://blog.csdn.net/mazhimazh/article/details/19028311

轉載自：https://blog.csdn.net/u011225629/article/details/45875765

Java 數據結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。