TreeSet and TreeMap
總體介紹
之所以把TreeSet和TreeMap放在一起講解，是因為二者在Java里有著相同的實現(xiàn)白修，前者僅僅是對后者做了一層包裝东亦，也就是說TreeSet里面有一個TreeMap（適配器模式）。因此本文將重點分析TreeMap唯竹。
Java TreeMap實現(xiàn)了SortedMap接口乐导，也就是說會按照key的大小順序?qū)?em>Map中的元素進行排序，key大小的評判可以通過其本身的自然順序（natural ordering）浸颓，也可以通過構(gòu)造時傳入的比較器（Comparator）物臂。
TreeMap底層通過紅黑樹（Red-Black tree）實現(xiàn)，也就意味著containsKey(), get(), put(), remove()都有著log(n)的時間復雜度产上。其具體算法實現(xiàn)參照了《算法導論》棵磷。
出于性能原因，TreeMap是非同步的（not synchronized）晋涣，如果需要在多線程環(huán)境使用仪媒，需要程序員手動同步；或者通過如下方式將TreeMap包裝成（wrapped）同步的：
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
紅黑樹是一種近似平衡的二叉查找樹谢鹊，它能夠確保任何一個節(jié)點的左右子樹的高度差不會超過二者中較低那個的一陪算吩。具體來說，紅黑樹是滿足如下條件的二叉查找樹（binary search tree）：
- 每個節(jié)點要么是紅色佃扼，要么是黑色偎巢。
- 根節(jié)點必須是黑色
- 紅色節(jié)點不能連續(xù)（也即是，紅色節(jié)點的孩子和父親都不能是紅色）兼耀。
- 對于每個節(jié)點压昼，從該點至
null（樹尾端）的任何路徑，都含有相同個數(shù)的黑色節(jié)點瘤运。
在樹的結(jié)構(gòu)發(fā)生改變時（插入或者刪除操作）巢音，往往會破壞上述條件3或條件4，需要通過調(diào)整使得查找樹重新滿足紅黑樹的約束條件尽超。
預備知識
前文說到當查找樹的結(jié)構(gòu)發(fā)生改變時官撼，紅黑樹的約束條件可能被破壞，需要通過調(diào)整使得查找樹重新滿足紅黑樹的約束條件似谁。調(diào)整可以分為兩類：一類是顏色調(diào)整傲绣，即改變某個節(jié)點的顏色；另一類是結(jié)構(gòu)調(diào)整巩踏，集改變檢索樹的結(jié)構(gòu)關系秃诵。結(jié)構(gòu)調(diào)整過程包含兩個基本操作：左旋（Rotate Left），右旋（RotateRight）塞琼。
左旋
左旋的過程是將x的右子樹繞x逆時針旋轉(zhuǎn)菠净，使得x的右子樹成為x的父親，同時修改相關節(jié)點的引用。旋轉(zhuǎn)之后毅往，二叉查找樹的屬性仍然滿足牵咙。
TreeMap中左旋代碼如下：
//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;
}
}
右旋
右旋的過程是將x的左子樹繞x順時針旋轉(zhuǎn)，使得x的左子樹成為x的父親攀唯，同時修改相關節(jié)點的引用洁桌。旋轉(zhuǎn)之后，二叉查找樹的屬性仍然滿足侯嘀。
TreeMap中右旋代碼如下：
//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;
}
}
尋找節(jié)點后繼
對于一棵二叉查找樹另凌，給定節(jié)點t，其后繼（樹中比大于t的最小的那個元素）可以通過如下方式找到：
- t的右子樹不空戒幔，則t的后繼是其右子樹中最小的那個元素吠谢。
- t的右孩子為空，則t的后繼是其第一個向左走的祖先诗茎。
后繼節(jié)點在紅黑樹的刪除操作中將會用到工坊。
TreeMap中尋找節(jié)點后繼的代碼如下：
// 尋找節(jié)點后繼函數(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的后繼是其右子樹中最小的那個元素
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;
}
}
方法剖析
get()
get(Object key)方法根據(jù)指定的key值返回對應的value，該方法調(diào)用了getEntry(Object key)得到相應的entry雀瓢，然后返回entry.value枢析。因此getEntry()是算法的核心。算法思想是根據(jù)key的自然順序（或者比較器順序）對二叉查找樹進行查找刃麸，直到找到滿足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對添加到map里。該方法首先會對map做一次查找泊业，看是否包含該元組把沼，如果已經(jīng)包含則直接返回，查找過程類似于getEntry()方法吁伺；如果沒有找到則會在紅黑樹中插入新的entry饮睬，如果插入之后破壞了紅黑樹的約束條件，還需要進行調(diào)整（旋轉(zhuǎn)篮奄，改變某些節(jié)點的顏色）捆愁。
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并插入（當然窟却，新插入的節(jié)點一定是樹的葉子）昼丑。難點是調(diào)整函數(shù)fixAfterInsertion()，前面已經(jīng)說過夸赫，調(diào)整往往需要1.改變某些節(jié)點的顏色菩帝，2.對某些節(jié)點進行旋轉(zhuǎn)。
調(diào)整函數(shù)fixAfterInsertion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數(shù)呼奢。通過代碼我們能夠看到宜雀，情況2其實是落在情況3內(nèi)的。情況4～情況6跟前三種情況是對稱的控妻，因此圖解中并沒有畫出后三種情況州袒，讀者可以參考代碼自行理解。
//紅黑樹調(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值對應的entry弓候，該方法首先通過上文中提到的getEntry(Object key)方法找到key值對應的entry郎哭，然后調(diào)用deleteEntry(Entry<K,V> entry)刪除對應的entry。由于刪除操作會改變紅黑樹的結(jié)構(gòu)菇存，有可能破壞紅黑樹的約束條件夸研，因此有可能要進行調(diào)整。
getEntry()函數(shù)前面已經(jīng)講解過依鸥，這里重點放deleteEntry()上亥至，該函數(shù)刪除指定的entry并在紅黑樹的約束被破壞時進行調(diào)用fixAfterDeletion(Entry<K,V> x)進行調(diào)整。
由于紅黑樹是一棵增強版的二叉查找樹贱迟，紅黑樹的刪除操作跟普通二叉查找樹的刪除操作也就非常相似姐扮，唯一的區(qū)別是紅黑樹在節(jié)點刪除之后可能需要進行調(diào)整。現(xiàn)在考慮一棵普通二叉查找樹的刪除過程衣吠，可以簡單分為兩種情況：
- 刪除點p的左右子樹都為空茶敏，或者只有一棵子樹非空。
- 刪除點p的左右子樹都非空缚俏。
對于上述情況1惊搏，處理起來比較簡單，直接將p刪除（左右子樹都為空時）忧换，或者用非空子樹替代p（只有一棵子樹非空時）恬惯；對于情況2，可以用p的后繼s（樹中大于x的最小的那個元素）代替p亚茬，然后使用情況1刪除s（此時s一定滿足情況1.可以畫畫看）酪耳。
基于以上邏輯，紅黑樹的節(jié)點刪除函數(shù)deleteEntry()代碼如下：
// 紅黑樹entry刪除函數(shù)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);// 調(diào)整
} else if (p.parent == null) {
root = null;
} else { // 1\. 刪除點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ào)整函數(shù)fixAfterDeletion()。首先請思考一下厨疙，刪除了哪些點才會導致調(diào)整洲守？只有刪除點是BLACK的時候，才會觸發(fā)調(diào)整函數(shù)，因為刪除RED節(jié)點不會破壞紅黑樹的任何約束梗醇，而刪除BLACK節(jié)點會破壞規(guī)則4知允。
跟上文中講過的fixAfterInsertion()函數(shù)一樣，這里也要分成若干種情況叙谨。記住温鸽，無論有多少情況，具體的調(diào)整操作只有兩種：1.改變某些節(jié)點的顏色手负，2.對某些節(jié)點進行旋轉(zhuǎn)涤垫。
上述圖解的總體思想是：將情況1首先轉(zhuǎn)換成情況2，或者轉(zhuǎn)換成情況3和情況4竟终。當然蝠猬，該圖解并不意味著調(diào)整過程一定是從情況1開始。通過后續(xù)代碼我們還會發(fā)現(xiàn)幾個有趣的規(guī)則：a).如果是由情況1之后緊接著進入的情況2统捶，那么情況2之后一定會退出循環(huán)（因為x為紅色）榆芦；b).一旦進入情況3和情況4，一定會退出循環(huán)（因為x為root）喘鸟。
刪除后調(diào)整函數(shù)fixAfterDeletion()的具體代碼如下匆绣，其中用到了上文中提到的rotateLeft()和rotateRight()函數(shù)。通過代碼我們能夠看到什黑，情況3其實是落在情況4內(nèi)的崎淳。情況5～情況8跟前四種情況是對稱的，因此圖解中并沒有畫出后四種情況兑凿，讀者可以參考代碼自行理解凯力。
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);
}
TreeSet
前面已經(jīng)說過TreeSet是對TreeMap的簡單包裝茵瘾，對TreeSet的函數(shù)調(diào)用都會轉(zhuǎn)換成合適的TreeMap方法礼华，因此TreeSet的實現(xiàn)非常簡單。這里不再贅述拗秘。
// 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;
}
......
}
