TreeSet and TreeMap
總體介紹
之所以把TreeSet和TreeMap放在一起講解署恍，是因?yàn)槎咴贘ava里有著相同的實(shí)現(xiàn)，前者僅僅是對(duì)后者做了一層包裝蜻直，也就是說(shuō)TreeSet里面有一個(gè)TreeMap（適配器模式）锭汛。因此本文將重點(diǎn)分析TreeMap。
Java TreeMap實(shí)現(xiàn)了SortedMap接口袭蝗，也就是說(shuō)會(huì)按照key的大小順序?qū)?em>Map中的元素進(jìn)行排序唤殴，key大小的評(píng)判可以通過(guò)其本身的自然順序（natural ordering），也可以通過(guò)構(gòu)造時(shí)傳入的比較器（Comparator）到腥。
TreeMap底層通過(guò)紅黑樹(shù)（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)同步渠脉；或者通過(guò)如下方式將TreeMap包裝成（wrapped）同步的：
SortedMap m = Collections.synchronizedSortedMap(new TreeMap(...));
紅黑樹(shù)是一種近似平衡的二叉查找樹(shù)，它能夠確保任何一個(gè)節(jié)點(diǎn)的左右子樹(shù)的高度差不會(huì)超過(guò)二者中較低那個(gè)的一陪瓶佳。具體來(lái)說(shuō)芋膘，紅黑樹(shù)是滿足如下條件的二叉查找樹(shù)（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（樹(shù)尾端）的任何路徑习寸，都含有相同個(gè)數(shù)的黑色節(jié)點(diǎn)。
在樹(shù)的結(jié)構(gòu)發(fā)生改變時(shí)（插入或者刪除操作）傻工，往往會(huì)破壞上述條件3或條件4霞溪，需要通過(guò)調(diào)整使得查找樹(shù)重新滿足紅黑樹(shù)的約束條件孵滞。
預(yù)備知識(shí)
前文說(shuō)到當(dāng)查找樹(shù)的結(jié)構(gòu)發(fā)生改變時(shí)，紅黑樹(shù)的約束條件可能被破壞鸯匹，需要通過(guò)調(diào)整使得查找樹(shù)重新滿足紅黑樹(shù)的約束條件坊饶。調(diào)整可以分為兩類：一類是顏色調(diào)整，即改變某個(gè)節(jié)點(diǎn)的顏色忽你；另一類是結(jié)構(gòu)調(diào)整幼东，集改變檢索樹(shù)的結(jié)構(gòu)關(guān)系。結(jié)構(gòu)調(diào)整過(guò)程包含兩個(gè)基本操作：左旋（Rotate Left）科雳，右旋（RotateRight）根蟹。
左旋
左旋的過(guò)程是將x的右子樹(shù)繞x逆時(shí)針旋轉(zhuǎn)，使得x的右子樹(shù)成為x的父親糟秘，同時(shí)修改相關(guān)節(jié)點(diǎn)的引用简逮。旋轉(zhuǎn)之后，二叉查找樹(shù)的屬性仍然滿足尿赚。
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;
}
}
右旋
右旋的過(guò)程是將x的左子樹(shù)繞x順時(shí)針旋轉(zhuǎn)散庶，使得x的左子樹(shù)成為x的父親，同時(shí)修改相關(guān)節(jié)點(diǎn)的引用凌净。旋轉(zhuǎn)之后悲龟，二叉查找樹(shù)的屬性仍然滿足。
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é)點(diǎn)后繼
對(duì)于一棵二叉查找樹(shù)冰寻，給定節(jié)點(diǎn)t须教，其后繼（樹(shù)中比大于t的最小的那個(gè)元素）可以通過(guò)如下方式找到：
- t的右子樹(shù)不空，則t的后繼是其右子樹(shù)中最小的那個(gè)元素斩芭。
- t的右孩子為空轻腺，則t的后繼是其第一個(gè)向左走的祖先。
后繼節(jié)點(diǎn)在紅黑樹(shù)的刪除操作中將會(huì)用到划乖。
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的右子樹(shù)不空贬养，則t的后繼是其右子樹(shù)中最小的那個(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;
}
}
方法剖析
get()
get(Object key)方法根據(jù)指定的key值返回對(duì)應(yīng)的value琴庵，該方法調(diào)用了getEntry(Object key)得到相應(yīng)的entry误算，然后返回entry.value。因此getEntry()是算法的核心细卧。算法思想是根據(jù)key的自然順序（或者比較器順序）對(duì)二叉查找樹(shù)進(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)包含則直接返回止邮，查找過(guò)程類似于getEntry()方法这橙；如果沒(méi)有找到則會(huì)在紅黑樹(shù)中插入新的entry，如果插入之后破壞了紅黑樹(shù)的約束條件导披，還需要進(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;
}
上述代碼的插入部分并不難理解：首先在紅黑樹(shù)上找到合適的位置撩匕，然后創(chuàng)建新的entry并插入（當(dāng)然鹰晨，新插入的節(jié)點(diǎn)一定是樹(shù)的葉子）。難點(diǎn)是調(diào)整函數(shù)fixAfterInsertion()止毕，前面已經(jīng)說(shuō)過(guò)模蜡，調(diào)整往往需要1.改變某些節(jié)點(diǎn)的顏色，2.對(duì)某些節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)扁凛。
調(diào)整函數(shù)fixAfterInsertion()的具體代碼如下忍疾，其中用到了上文中提到的rotateLeft()和rotateRight()函數(shù)。通過(guò)代碼我們能夠看到谨朝，情況2其實(shí)是落在情況3內(nèi)的卤妒。情況4～情況6跟前三種情況是對(duì)稱的，因此圖解中并沒(méi)有畫(huà)出后三種情況字币，讀者可以參考代碼自行理解则披。
//紅黑樹(shù)調(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，該方法首先通過(guò)上文中提到的getEntry(Object key)方法找到key值對(duì)應(yīng)的entry洗出，然后調(diào)用deleteEntry(Entry<K,V> entry)刪除對(duì)應(yīng)的entry士复。由于刪除操作會(huì)改變紅黑樹(shù)的結(jié)構(gòu)，有可能破壞紅黑樹(shù)的約束條件共苛，因此有可能要進(jìn)行調(diào)整判没。
getEntry()函數(shù)前面已經(jīng)講解過(guò)，這里重點(diǎn)放deleteEntry()上隅茎，該函數(shù)刪除指定的entry并在紅黑樹(shù)的約束被破壞時(shí)進(jìn)行調(diào)用fixAfterDeletion(Entry<K,V> x)進(jìn)行調(diào)整澄峰。
由于紅黑樹(shù)是一棵增強(qiáng)版的二叉查找樹(shù)，紅黑樹(shù)的刪除操作跟普通二叉查找樹(shù)的刪除操作也就非常相似辟犀，唯一的區(qū)別是紅黑樹(shù)在節(jié)點(diǎn)刪除之后可能需要進(jìn)行調(diào)整∏尉海現(xiàn)在考慮一棵普通二叉查找樹(shù)的刪除過(guò)程，可以簡(jiǎn)單分為兩種情況：
- 刪除點(diǎn)p的左右子樹(shù)都為空堂竟，或者只有一棵子樹(shù)非空魂毁。
- 刪除點(diǎn)p的左右子樹(shù)都非空。
對(duì)于上述情況1出嘹，處理起來(lái)比較簡(jiǎn)單席楚，直接將p刪除（左右子樹(shù)都為空時(shí)），或者用非空子樹(shù)替代p（只有一棵子樹(shù)非空時(shí)）税稼；對(duì)于情況2烦秩，可以用p的后繼s（樹(shù)中大于x的最小的那個(gè)元素）代替p垮斯，然后使用情況1刪除s（此時(shí)s一定滿足情況1.可以畫(huà)畫(huà)看）。
基于以上邏輯只祠，紅黑樹(shù)的節(jié)點(diǎn)刪除函數(shù)deleteEntry()代碼如下：
// 紅黑樹(shù)entry刪除函數(shù)deleteEntry()
private void deleteEntry(Entry<K,V> p) {
modCount++;
size--;
if (p.left != null && p.right != null) {// 2. 刪除點(diǎn)p的左右子樹(shù)都非空兜蠕。
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只有一棵子樹(shù)非空。
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的左右子樹(shù)都為空
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ù)大量代碼行的抛寝，是用來(lái)修改父子節(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ì)破壞紅黑樹(shù)的任何約束，而刪除BLACK節(jié)點(diǎn)會(huì)破壞規(guī)則4爷绘。
跟上文中講過(guò)的fixAfterInsertion()函數(shù)一樣书劝，這里也要分成若干種情況。記住土至，無(wú)論有多少情況购对，具體的調(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)整過(guò)程一定是從情況1開(kāi)始解幽。通過(guò)后續(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ù)霜定。通過(guò)代碼我們能夠看到，情況3其實(shí)是落在情況4內(nèi)的廊鸥。情況5～情況8跟前四種情況是對(duì)稱的望浩，因此圖解中并沒(méi)有畫(huà)出后四種情況，讀者可以參考代碼自行理解惰说。
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)說(shuō)過(guò)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;
}
......
}
