本文github地址
上一篇文章史上最清晰的紅黑樹講解（上）對Java TreeMap的插入以及插入之后的調(diào)整過程給出了詳述。本文接著以Java TreeMap為例，從源碼層面講解紅黑樹的刪除，以及刪除之后的調(diào)整過程。如果還沒有看過上一篇文章，請在閱讀本文之前大致瀏覽一下前文，以方便理解。
尋找節(jié)點(diǎn)后繼
對于一棵二叉查找樹，給定節(jié)點(diǎn)t，其后繼（樹種比大于t的最小的那個元素）可以通過如下方式找到：
- t的右子樹不空，則t的后繼是其右子樹中最小的那個元素。
- t的右孩子為空，則t的后繼是其第一個向左走的祖先。
后繼節(jié)點(diǎn)在紅黑樹的刪除操作中將會用到。
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的后繼是其右子樹中最小的那個元素
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;
}
}
remove()
remove(Object key)的作用是刪除key值對應(yīng)的entry，該方法首先通過上文中提到的getEntry(Object key)方法找到key值對應(yīng)的entry，然后調(diào)用deleteEntry(Entry<K,V> entry)刪除對應(yīng)的entry。由于刪除操作會改變紅黑樹的結(jié)構(gòu)，有可能破壞紅黑樹的約束條件，因此有可能要進(jìn)行調(diào)整。
getEntry()函數(shù)前面已經(jīng)講解過，這里重點(diǎn)放deleteEntry()上，該函數(shù)刪除指定的entry并在紅黑樹的約束被破壞時進(jìn)行調(diào)用fixAfterDeletion(Entry<K,V> x)進(jìn)行調(diào)整。
由于紅黑樹是一棵增強(qiáng)版的二叉查找樹，紅黑樹的刪除操作跟普通二叉查找樹的刪除操作也就非常相似，唯一的區(qū)別是紅黑樹在節(jié)點(diǎn)刪除之后可能需要進(jìn)行調(diào)整。現(xiàn)在考慮一棵普通二叉查找樹的刪除過程，可以簡單分為兩種情況：
- 刪除點(diǎn)p的左右子樹都為空，或者只有一棵子樹非空。
- 刪除點(diǎn)p的左右子樹都非空。
對于上述情況1，處理起來比較簡單，直接將p刪除（左右子樹都為空時），或者用非空子樹替代p（只有一棵子樹非空時）；對于情況2，可以用p的后繼s（樹中大于x的最小的那個元素）代替p，然后使用情況1刪除s（此時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()。首先請思考一下，刪除了哪些點(diǎn)才會導(dǎo)致調(diào)整？只有刪除點(diǎn)是BLACK的時候，才會觸發(fā)調(diào)整函數(shù)，因?yàn)閯h除RED節(jié)點(diǎn)不會破壞紅黑樹的任何約束，而刪除BLACK節(jié)點(diǎn)會破壞規(guī)則4。
跟上文中講過的fixAfterInsertion()函數(shù)一樣，這里也要分成若干種情況。記住，無論有多少情況，具體的調(diào)整操作只有兩種：1.改變某些節(jié)點(diǎn)的顏色，2.對某些節(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)。
上述圖解的總體思想是：將情況1首先轉(zhuǎn)換成情況2，或者轉(zhuǎn)換成情況3和情況4。當(dāng)然，該圖解并不意味著調(diào)整過程一定是從情況1開始。通過后續(xù)代碼我們還會發(fā)現(xiàn)幾個有趣的規(guī)則：a).如果是由情況1之后緊接著進(jìn)入的情況2，那么情況2之后一定會退出循環(huán)（因?yàn)閤為紅色）；b).一旦進(jìn)入情況3和情況4，一定會退出循環(huán)（因?yàn)閤為root）。
刪除后調(diào)整函數(shù)fixAfterDeletion()的具體代碼如下，其中用到了上文中提到的rotateLeft()和rotateRight()函數(shù)。通過代碼我們能夠看到，情況3其實(shí)是落在情況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是對TeeMap的簡單包裝，對TreeSet的函數(shù)調(diào)用都會轉(zhuǎn)換成合適的TeeMap方法，因此TreeSet的實(shí)現(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;
}
}