01

介紹

之所以把TreeSet和TreeMap放在一起講解，是因?yàn)槎咴贘ava里有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝，也就是說TreeSet里面有一個(gè)TreeMap（適配器模式）**。因此本文將重點(diǎn)分析TreeMap。

Java TreeMap實(shí)現(xiàn)了SortedMap接口，也就是說會(huì)按照key的大小順序?qū)ap中的元素進(jìn)行排序，key大小的評(píng)判可以通過其本身的自然順序（natural ordering），也可以通過構(gòu)造時(shí)傳入的比較器（Comparator）。

TreeMap底層通過紅黑樹（Red-Black tree）實(shí)現(xiàn)，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時(shí)間復(fù)雜度。其具體算法實(shí)現(xiàn)參照了《算法導(dǎo)論》。

?

圖片展示：

出于性能原因，TreeMap是非同步的（not synchronized），如果需要在多線程環(huán)境使用，需要程序員手動(dòng)同步；或者通過如下方式將TreeMap包裝成（wrapped）同步的：

SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));

紅黑樹是一種近似平衡的二叉查找樹，它能夠確保任何一個(gè)節(jié)點(diǎn)的左右子樹的高度差不會(huì)超過二者中較低那個(gè)的一倍。具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）：

每個(gè)節(jié)點(diǎn)要么是紅色，要么是黑色。

根節(jié)點(diǎn)必須是黑色

紅色節(jié)點(diǎn)不能連續(xù)（也即是，紅色節(jié)點(diǎn)的孩子和父親都不能是紅色）。

對(duì)于每個(gè)節(jié)點(diǎn)，從該點(diǎn)至null（樹尾端）的任何路徑，都含有相同個(gè)數(shù)的黑色節(jié)點(diǎn)。

在樹的結(jié)構(gòu)發(fā)生改變時(shí)（插入或者刪除操作），往往會(huì)破壞上述條件3或條件4，需要通過調(diào)整使得查找樹重新滿足紅黑樹的約束條件。

01

補(bǔ)充知識(shí)

前文說到當(dāng)查找樹的結(jié)構(gòu)發(fā)生改變時(shí)，紅黑樹的約束條件可能被破壞，需要通過調(diào)整使得查找樹重新滿足紅黑樹的約束條件。調(diào)整可以分為兩類：一類是顏色調(diào)整，即改變某個(gè)節(jié)點(diǎn)的顏色；另一類是結(jié)構(gòu)調(diào)整，集改變檢索樹的結(jié)構(gòu)關(guān)系。結(jié)構(gòu)調(diào)整過程包含兩個(gè)基本操作：左旋（Rotate Left），右旋（RotateRight）。

01

左旋

左旋的過程是將x的右子樹繞x逆時(shí)針旋轉(zhuǎn)，使得x的右子樹成為x的父親，同時(shí)修改相關(guān)節(jié)點(diǎn)的引用。旋轉(zhuǎn)之后，二叉查找樹的屬性仍然滿足。

圖片展示：

01

TreeMap中左旋代碼如下：

//Rotate Leftprivate 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; ? ?}}


01

右旋

右旋的過程是將x的左子樹繞x順時(shí)針旋轉(zhuǎn)，使得x的左子樹成為x的父親，同時(shí)修改相關(guān)節(jié)點(diǎn)的引用。旋轉(zhuǎn)之后，二叉查找樹的屬性仍然滿足。

01

TreeMap中右旋代碼如下：

//Rotate Rightprivate 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; ? ?}}


01

尋找節(jié)點(diǎn)后繼

對(duì)于一棵二叉查找樹，給定節(jié)點(diǎn)t，其后繼（樹中比大于t的最小的那個(gè)元素）可以通過如下方式找到：

1.t的右子樹不空，則t的后繼是其右子樹中最小的那個(gè)元素。

2.t的右孩子為空，則t的后繼是其第一個(gè)向左走的祖先。

后繼節(jié)點(diǎn)在紅黑樹的刪除操作中將會(huì)用到。

01

TreeMap尋找節(jié)點(diǎn)后繼的代碼如下

// 尋找節(jié)點(diǎn)后繼函數(shù)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的后繼是其右子樹中最小的那個(gè)元素 ? ? ? ?Entry<K,V> p = t.right; ? ? ? ?while (p.left != null) ? ? ? ? ? ?p = p.left; ? ? ? ?return p; ? ?} else {// 2. t的右孩子為空，則t的后繼是其第一個(gè)向左走的祖先 ? ? ? ?Entry<K,V> p = t.parent; ? ? ? ?Entry<K,V> ch = t; ? ? ? ?while (p != null && ch == p.right) { ? ? ? ? ? ?ch = p; ? ? ? ? ? ?p = p.parent; ? ? ? ?} ? ? ? ?return p; ? ?}}

01

方法剖析

get()

get(Object key)方法根據(jù)指定的key值返回對(duì)應(yīng)的value，該方法調(diào)用了getEntry(Object key)得到相應(yīng)的entry，然后返回entry.value。因此getEntry()是算法的核心。算法思想是根據(jù)key的自然順序（或者比較器順序）對(duì)二叉查找樹進(jìn)行查找，直到找到滿足k.compareTo(p.key) == 0的entry。

具體代碼如下：

//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;}


put()

put(K key, V value)方法是將指定的key, value對(duì)添加到map里。該方法首先會(huì)對(duì)map做一次查找，看是否包含該元組，如果已經(jīng)包含則直接返回，查找過程類似于getEntry()方法；如果沒有找到則會(huì)在紅黑樹中插入新的entry，如果插入之后破壞了紅黑樹的約束條件，還需要進(jìn)行調(diào)整（旋轉(zhuǎn)，改變某些節(jié)點(diǎn)的顏色）。

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);//創(chuàng)建并插入新的entry ? ?if (cmp < 0) parent.left = e; ? ?else parent.right = e; ? ?fixAfterInsertion(e);//調(diào)整 ? ?size++; ? ?return null;}

上述代碼的插入部分并不難理解：首先在紅黑樹上找到合適的位置，然后創(chuàng)建新的entry并插入（當(dāng)然，新插入的節(jié)點(diǎn)一定是樹的葉子）。難點(diǎn)是調(diào)整函數(shù)fixAfterInsertion()，前面已經(jīng)說過，調(diào)整往往需要1.改變某些節(jié)點(diǎn)的顏色，2.對(duì)某些節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)。

? ? ? ? ? ? ? ? ? ? ? ? ??

調(diào)整函數(shù)fixAfterInsertion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數(shù)。通過代碼我們能夠看到，情況2其實(shí)是落在情況3內(nèi)的。情況4～情況6跟前三種情況是對(duì)稱的，因此圖解中并沒有畫出后三種情況，讀者可以參考代碼自行理解。

//紅黑樹調(diào)整函數(shù)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;}


? ? ? ? ? ? ? ? ? ? ? ? ? ??

remove()

remove(Object key)的作用是刪除key值對(duì)應(yīng)的entry，該方法首先通過上文中提到的getEntry(Object key)方法找到key值對(duì)應(yīng)的entry，然后調(diào)用deleteEntry(Entry<K,V> entry)刪除對(duì)應(yīng)的entry。由于刪除操作會(huì)改變紅黑樹的結(jié)構(gòu)，有可能破壞紅黑樹的約束條件，因此有可能要進(jìn)行調(diào)整。

getEntry()函數(shù)前面已經(jīng)講解過，這里重點(diǎn)放deleteEntry()上，該函數(shù)刪除指定的entry并在紅黑樹的約束被破壞時(shí)進(jìn)行調(diào)用fixAfterDeletion(Entry<K,V> x)進(jìn)行調(diào)整。

由于紅黑樹是一棵增強(qiáng)版的二叉查找樹，紅黑樹的刪除操作跟普通二叉查找樹的刪除操作也就非常相似，唯一的區(qū)別是紅黑樹在節(jié)點(diǎn)刪除之后可能需要進(jìn)行調(diào)整?，F(xiàn)在考慮一棵普通二叉查找樹的刪除過程，可以簡(jiǎn)單分為兩種情況：

刪除點(diǎn)p的左右子樹都為空，或者只有一棵子樹非空。

刪除點(diǎn)p的左右子樹都非空。

對(duì)于上述情況1，處理起來比較簡(jiǎn)單，直接將p刪除（左右子樹都為空時(shí)），或者用非空子樹替代p（只有一棵子樹非空時(shí)）；對(duì)于情況2，可以用p的后繼s（樹中大于x的最小的那個(gè)元素）代替p，然后使用情況1刪除s（此時(shí)s一定滿足情況1.可以畫畫看）。

基于以上邏輯，紅黑樹的節(jié)點(diǎn)刪除函數(shù)deleteEntry()代碼如下：

// 紅黑樹entry刪除函數(shù)deleteEntry()private void deleteEntry(Entry<K,V> p) { ? ?modCount++; ? ?size--; ? ?if (p.left != null && p.right != null) {// 2. 刪除點(diǎn)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. 刪除點(diǎn)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);// 調(diào)整 ? ?} else if (p.parent == null) { ? ? ? ?root = null; ? ?} else { // 1. 刪除點(diǎn)p的左右子樹都為空 ? ? ? ?if (p.color == BLACK) ? ? ? ? ? ?fixAfterDeletion(p);// 調(diào)整 ? ? ? ?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; ? ? ? ?} ? ?}}


? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

上述代碼中占據(jù)大量代碼行的，是用來修改父子節(jié)點(diǎn)間引用關(guān)系的代碼，其邏輯并不難理解。下面著重講解刪除后調(diào)整函數(shù)fixAfterDeletion()。首先請(qǐng)思考一下，刪除了哪些點(diǎn)才會(huì)導(dǎo)致調(diào)整？只有刪除點(diǎn)是BLACK的時(shí)候，才會(huì)觸發(fā)調(diào)整函數(shù)，因?yàn)閯h除RED節(jié)點(diǎn)不會(huì)破壞紅黑樹的任何約束，而刪除BLACK節(jié)點(diǎn)會(huì)破壞規(guī)則4。

跟上文中講過的fixAfterInsertion()函數(shù)一樣，這里也要分成若干種情況。記住，無論有多少情況，具體的調(diào)整操作只有兩種：1.改變某些節(jié)點(diǎn)的顏色，2.對(duì)某些節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)。

上述圖解的總體思想是：將情況1首先轉(zhuǎn)換成情況2，或者轉(zhuǎn)換成情況3和情況4。當(dāng)然，該圖解并不意味著調(diào)整過程一定是從情況1開始。通過后續(xù)代碼我們還會(huì)發(fā)現(xiàn)幾個(gè)有趣的規(guī)則：a).如果是由情況1之后緊接著進(jìn)入的情況2，那么情況2之后一定會(huì)退出循環(huán)（因?yàn)閤為紅色）；b).一旦進(jìn)入情況3和情況4，一定會(huì)退出循環(huán)（因?yàn)閤為root）。

刪除后調(diào)整函數(shù)fixAfterDeletion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數(shù)。通過代碼我們能夠看到，情況3其實(shí)是落在情況4內(nèi)的。情況5～情況8跟前四種情況是對(duì)稱的，因此圖解中并沒有畫出后四種情況，讀者可以參考代碼自行理解。

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 { // 跟前四種情況對(duì)稱 ? ? ? ? ? ?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);}


TreeSet

前面已經(jīng)說過TreeSet是對(duì)TreeMap的簡(jiǎn)單包裝，對(duì)TreeSet的函數(shù)調(diào)用都會(huì)轉(zhuǎn)換成合適的TreeMap方法，因此TreeSet的實(shí)現(xiàn)非常簡(jiǎn)單。這里不再贅述。

// TreeSet是對(duì)TreeMap的簡(jiǎn)單包裝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里面有一個(gè)TreeMap ? ?} ? ?...... ? ?public boolean add(E e) { ? ? ? ?return m.put(e, PRESENT)==null; ? ?} ? ?......}

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?