9.TreeSet和TreeMap · java核心知識整理

# 總體介紹之所以把*TreeSet*和*TreeMap*放在一起講解，是因為二者在Java里有著相同的實現，前者僅僅是對后者做了一層包裝，也就是說***TreeSet*里面有一個*TreeMap*（適配器模式）\*\*。因此本文將重點分析*TreeMap*。 Java*TreeMap*實現了*SortedMap*接口，也就是說會按照`key`的大小順序對*Map*中的元素進行排序，`key`大小的評判可以通過其本身的自然順序（natural ordering），也可以通過構造時傳入的比較器（Comparator）。 ***TreeMap*底層通過紅黑樹（Red-Black tree）實現**，也就意味著`containsKey()`,`get()`,`put()`,`remove()`都有著`log(n)`的時間復雜度。其具體算法實現參照了《算法導論》。 [![TreeMap_base.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_base.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_base.png) 出于性能原因，*TreeMap*是非同步的（not synchronized），如果需要在多線程環境使用，需要程序員手動同步；或者通過如下方式將*TreeMap*包裝成（wrapped）同步的： `SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));` **紅黑樹是一種近似平衡的二叉查找樹，它能夠確保任何一個節點的左右子樹的高度差不會超過二者中較低那個的一陪**。具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）： 1. 每個節點要么是紅色，要么是黑色。 2. 根節點必須是黑色 3. 紅色節點不能連續（也即是，紅色節點的孩子和父親都不能是紅色）。 4. 對于每個節點，從該點至`null`（樹尾端）的任何路徑，都含有相同個數的黑色節點。在樹的結構發生改變時（插入或者刪除操作），往往會破壞上述條件3或條件4，需要通過調整使得查找樹重新滿足紅黑樹的約束條件。 # [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#預備知識)預備知識前文說到當查找樹的結構發生改變時，紅黑樹的約束條件可能被破壞，需要通過調整使得查找樹重新滿足紅黑樹的約束條件。調整可以分為兩類：一類是顏色調整，即改變某個節點的顏色；另一類是結構調整，集改變檢索樹的結構關系。結構調整過程包含兩個基本操作：**左旋（Rotate Left），右旋（RotateRight）**。 ## [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#左旋)左旋左旋的過程是將`x`的右子樹繞`x`逆時針旋轉，使得`x`的右子樹成為`x`的父親，同時修改相關節點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。 [![TreeMap_rotateLeft.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_rotateLeft.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_rotateLeft.png) *TreeMap*中左旋代碼如下： ~~~java //Rotate Left private void rotateLeft(Entry<K,V> p) { if (p != null) { Entry<K,V> r = p.right; p.right = r.left; if (r.left != null) r.left.parent = p; r.parent = p.parent; if (p.parent == null) root = r; else if (p.parent.left == p) p.parent.left = r; else p.parent.right = r; r.left = p; p.parent = r; } } ~~~ ## [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#右旋)右旋右旋的過程是將`x`的左子樹繞`x`順時針旋轉，使得`x`的左子樹成為`x`的父親，同時修改相關節點的引用。旋轉之后，二叉查找樹的屬性仍然滿足。 [![TreeMap_rotateRight.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_rotateRight.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_rotateRight.png) *TreeMap*中右旋代碼如下： ~~~java //Rotate Right private void rotateRight(Entry<K,V> p) { if (p != null) { Entry<K,V> l = p.left; p.left = l.right; if (l.right != null) l.right.parent = p; l.parent = p.parent; if (p.parent == null) root = l; else if (p.parent.right == p) p.parent.right = l; else p.parent.left = l; l.right = p; p.parent = l; } } ~~~ ## [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#尋找節點后繼)尋找節點后繼對于一棵二叉查找樹，給定節點t，其后繼（樹中比大于t的最小的那個元素）可以通過如下方式找到： > 1. t的右子樹不空，則t的后繼是其右子樹中最小的那個元素。 > 2. t的右孩子為空，則t的后繼是其第一個向左走的祖先。后繼節點在紅黑樹的刪除操作中將會用到。 [![TreeMap_successor.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_successor.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_successor.png) *TreeMap*中尋找節點后繼的代碼如下： ~~~java // 尋找節點后繼函數successor() static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) { if (t == null) return null; else if (t.right != null) {// 1. t的右子樹不空，則t的后繼是其右子樹中最小的那個元素 Entry<K,V> p = t.right; while (p.left != null) p = p.left; return p; } else {// 2. t的右孩子為空，則t的后繼是其第一個向左走的祖先 Entry<K,V> p = t.parent; Entry<K,V> ch = t; while (p != null && ch == p.right) { ch = p; p = p.parent; } return p; } } ~~~ # [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#方法剖析)方法剖析 ## [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#get)get() `get(Object key)`方法根據指定的`key`值返回對應的`value`，該方法調用了`getEntry(Object key)`得到相應的`entry`，然后返回`entry.value`。因此`getEntry()`是算法的核心。算法思想是根據`key`的自然順序（或者比較器順序）對二叉查找樹進行查找，直到找到滿足`k.compareTo(p.key) == 0`的`entry`。 [![TreeMap_getEntry.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_getEntry.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_getEntry.png) 具體代碼如下： ~~~java //getEntry()方法 final Entry<K,V> getEntry(Object key) { ...... if (key == null)//不允許key值為null throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序 Entry<K,V> p = root; while (p != null) { int cmp = k.compareTo(p.key); if (cmp < 0)//向左找 p = p.left; else if (cmp > 0)//向右找 p = p.right; else return p; } return null; } ~~~ ## [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#put)put() `put(K key, V value)`方法是將指定的`key`,`value`對添加到`map`里。該方法首先會對`map`做一次查找，看是否包含該元組，如果已經包含則直接返回，查找過程類似于`getEntry()`方法；如果沒有找到則會在紅黑樹中插入新的`entry`，如果插入之后破壞了紅黑樹的約束條件，還需要進行調整（旋轉，改變某些節點的顏色）。 ~~~java public V put(K key, V value) { ...... int cmp; Entry<K,V> parent; if (key == null) throw new NullPointerException(); Comparable<? super K> k = (Comparable<? super K>) key;//使用元素的自然順序 do { parent = t; cmp = k.compareTo(t.key); if (cmp < 0) t = t.left;//向左找 else if (cmp > 0) t = t.right;//向右找 else return t.setValue(value); } while (t != null); Entry<K,V> e = new Entry<>(key, value, parent);//創建并插入新的entry if (cmp < 0) parent.left = e; else parent.right = e; fixAfterInsertion(e);//調整 size++; return null; } ~~~ 上述代碼的插入部分并不難理解：首先在紅黑樹上找到合適的位置，然后創建新的`entry`并插入（當然，新插入的節點一定是樹的葉子）。難點是調整函數`fixAfterInsertion()`，前面已經說過，調整往往需要1.改變某些節點的顏色，2.對某些節點進行旋轉。 [![TreeMap_put.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_put.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_put.png) 調整函數`fixAfterInsertion()`的具體代碼如下，其中用到了上文中提到的`rotateLeft()`和`rotateRight()`函數。通過代碼我們能夠看到，情況2其實是落在情況3內的。情況4～情況6跟前三種情況是對稱的，因此圖解中并沒有畫出后三種情況，讀者可以參考代碼自行理解。 ~~~java //紅黑樹調整函數fixAfterInsertion() private void fixAfterInsertion(Entry<K,V> x) { x.color = RED; while (x != null && x != root && x.parent.color == RED) { if (parentOf(x) == leftOf(parentOf(parentOf(x)))) { Entry<K,V> y = rightOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); // 情況1 setColor(y, BLACK); // 情況1 setColor(parentOf(parentOf(x)), RED); // 情況1 x = parentOf(parentOf(x)); // 情況1 } else { if (x == rightOf(parentOf(x))) { x = parentOf(x); // 情況2 rotateLeft(x); // 情況2 } setColor(parentOf(x), BLACK); // 情況3 setColor(parentOf(parentOf(x)), RED); // 情況3 rotateRight(parentOf(parentOf(x))); // 情況3 } } else { Entry<K,V> y = leftOf(parentOf(parentOf(x))); if (colorOf(y) == RED) { setColor(parentOf(x), BLACK); // 情況4 setColor(y, BLACK); // 情況4 setColor(parentOf(parentOf(x)), RED); // 情況4 x = parentOf(parentOf(x)); // 情況4 } else { if (x == leftOf(parentOf(x))) { x = parentOf(x); // 情況5 rotateRight(x); // 情況5 } setColor(parentOf(x), BLACK); // 情況6 setColor(parentOf(parentOf(x)), RED); // 情況6 rotateLeft(parentOf(parentOf(x))); // 情況6 } } } root.color = BLACK; } ~~~ ## [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#remove)remove() `remove(Object key)`的作用是刪除`key`值對應的`entry`，該方法首先通過上文中提到的`getEntry(Object key)`方法找到`key`值對應的`entry`，然后調用`deleteEntry(Entry<K,V> entry)`刪除對應的`entry`。由于刪除操作會改變紅黑樹的結構，有可能破壞紅黑樹的約束條件，因此有可能要進行調整。 `getEntry()`函數前面已經講解過，這里重點放`deleteEntry()`上，該函數刪除指定的`entry`并在紅黑樹的約束被破壞時進行調用`fixAfterDeletion(Entry<K,V> x)`進行調整。 **由于紅黑樹是一棵增強版的二叉查找樹，紅黑樹的刪除操作跟普通二叉查找樹的刪除操作也就非常相似，唯一的區別是紅黑樹在節點刪除之后可能需要進行調整**。現在考慮一棵普通二叉查找樹的刪除過程，可以簡單分為兩種情況： > 1. 刪除點p的左右子樹都為空，或者只有一棵子樹非空。 > 2. 刪除點p的左右子樹都非空。對于上述情況1，處理起來比較簡單，直接將p刪除（左右子樹都為空時），或者用非空子樹替代p（只有一棵子樹非空時）；對于情況2，可以用p的后繼s（樹中大于x的最小的那個元素）代替p，然后使用情況1刪除s（此時s一定滿足情況1.可以畫畫看）。基于以上邏輯，紅黑樹的節點刪除函數`deleteEntry()`代碼如下： ~~~java // 紅黑樹entry刪除函數deleteEntry() private void deleteEntry(Entry<K,V> p) { modCount++; size--; if (p.left != null && p.right != null) {// 2. 刪除點p的左右子樹都非空。 Entry<K,V> s = successor(p);// 后繼 p.key = s.key; p.value = s.value; p = s; } Entry<K,V> replacement = (p.left != null ? p.left : p.right); if (replacement != null) {// 1. 刪除點p只有一棵子樹非空。 replacement.parent = p.parent; if (p.parent == null) root = replacement; else if (p == p.parent.left) p.parent.left = replacement; else p.parent.right = replacement; p.left = p.right = p.parent = null; if (p.color == BLACK) fixAfterDeletion(replacement);// 調整 } else if (p.parent == null) { root = null; } else { // 1. 刪除點p的左右子樹都為空 if (p.color == BLACK) fixAfterDeletion(p);// 調整 if (p.parent != null) { if (p == p.parent.left) p.parent.left = null; else if (p == p.parent.right) p.parent.right = null; p.parent = null; } } } ~~~ 上述代碼中占據大量代碼行的，是用來修改父子節點間引用關系的代碼，其邏輯并不難理解。下面著重講解刪除后調整函數`fixAfterDeletion()`。首先請思考一下，刪除了哪些點才會導致調整？**只有刪除點是BLACK的時候，才會觸發調整函數**，因為刪除RED節點不會破壞紅黑樹的任何約束，而刪除BLACK節點會破壞規則4。跟上文中講過的`fixAfterInsertion()`函數一樣，這里也要分成若干種情況。記住，**無論有多少情況，具體的調整操作只有兩種：1.改變某些節點的顏色，2.對某些節點進行旋轉。** [![TreeMap_fixAfterDeletion.png](https://github.com/CarpenterLee/JCFInternals/raw/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_fixAfterDeletion.png)](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/PNGFigures/TreeMap_fixAfterDeletion.png) 上述圖解的總體思想是：將情況1首先轉換成情況2，或者轉換成情況3和情況4。當然，該圖解并不意味著調整過程一定是從情況1開始。通過后續代碼我們還會發現幾個有趣的規則：a).如果是由情況1之后緊接著進入的情況2，那么情況2之后一定會退出循環（因為x為紅色）；b).一旦進入情況3和情況4，一定會退出循環（因為x為root）。刪除后調整函數`fixAfterDeletion()`的具體代碼如下，其中用到了上文中提到的`rotateLeft()`和`rotateRight()`函數。通過代碼我們能夠看到，情況3其實是落在情況4內的。情況5～情況8跟前四種情況是對稱的，因此圖解中并沒有畫出后四種情況，讀者可以參考代碼自行理解。 ~~~java private void fixAfterDeletion(Entry<K,V> x) { while (x != root && colorOf(x) == BLACK) { if (x == leftOf(parentOf(x))) { Entry<K,V> sib = rightOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); // 情況1 setColor(parentOf(x), RED); // 情況1 rotateLeft(parentOf(x)); // 情況1 sib = rightOf(parentOf(x)); // 情況1 } if (colorOf(leftOf(sib)) == BLACK && colorOf(rightOf(sib)) == BLACK) { setColor(sib, RED); // 情況2 x = parentOf(x); // 情況2 } else { if (colorOf(rightOf(sib)) == BLACK) { setColor(leftOf(sib), BLACK); // 情況3 setColor(sib, RED); // 情況3 rotateRight(sib); // 情況3 sib = rightOf(parentOf(x)); // 情況3 } setColor(sib, colorOf(parentOf(x))); // 情況4 setColor(parentOf(x), BLACK); // 情況4 setColor(rightOf(sib), BLACK); // 情況4 rotateLeft(parentOf(x)); // 情況4 x = root; // 情況4 } } else { // 跟前四種情況對稱 Entry<K,V> sib = leftOf(parentOf(x)); if (colorOf(sib) == RED) { setColor(sib, BLACK); // 情況5 setColor(parentOf(x), RED); // 情況5 rotateRight(parentOf(x)); // 情況5 sib = leftOf(parentOf(x)); // 情況5 } if (colorOf(rightOf(sib)) == BLACK && colorOf(leftOf(sib)) == BLACK) { setColor(sib, RED); // 情況6 x = parentOf(x); // 情況6 } else { if (colorOf(leftOf(sib)) == BLACK) { setColor(rightOf(sib), BLACK); // 情況7 setColor(sib, RED); // 情況7 rotateLeft(sib); // 情況7 sib = leftOf(parentOf(x)); // 情況7 } setColor(sib, colorOf(parentOf(x))); // 情況8 setColor(parentOf(x), BLACK); // 情況8 setColor(leftOf(sib), BLACK); // 情況8 rotateRight(parentOf(x)); // 情況8 x = root; // 情況8 } } } setColor(x, BLACK); } ~~~ # [](https://github.com/CarpenterLee/JCFInternals/blob/049c84bb65a3114ba4b8355d83c490fb9b26c6af/markdown/5-TreeSet%20and%20TreeMap.md#treeset)TreeSet 前面已經說過`TreeSet`是對`TreeMap`的簡單包裝，對`TreeSet`的函數調用都會轉換成合適的`TreeMap`方法，因此`TreeSet`的實現非常簡單。這里不再贅述。 ~~~java // TreeSet是對TreeMap的簡單包裝 public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { ...... private transient NavigableMap<E,Object> m; // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); public TreeSet() { this.m = new TreeMap<E,Object>();// TreeSet里面有一個TreeMap } ...... public boolean add(E e) { return m.put(e, PRESENT)==null; } ...... } ~~~