0. 前言
前文我們提到過(guò)，紅黑樹是一種平衡搜索樹，即它源于二叉搜索樹。它通過(guò)額外引入的5條規(guī)則（有的書上濃縮成了3條）來(lái)維持二叉樹的平衡。另外，又因?yàn)樗⒉灰蠼^對(duì)平衡，所以操作效率比其他樹要高效得多，也正是因?yàn)槿绱?，紅黑樹在工業(yè)界應(yīng)用范圍較廣。本文代碼是用Java寫的，大家可以看一下ConcurrentHashMap的源碼，里面用到了紅黑樹來(lái)解決鍵沖突的問(wèn)題。
紅黑樹的核心是維護(hù)結(jié)點(diǎn)的紅黑顏色平衡，這是本文要探討的重點(diǎn)。
這個(gè)系列的紅黑樹講解中，代碼實(shí)現(xiàn)基本源于《算法導(dǎo)論》上的偽碼。請(qǐng)大家對(duì)比著看就好了。特別強(qiáng)調(diào)一下：用nil來(lái)替代null，使之成為一個(gè)真正的對(duì)象，能極大地簡(jiǎn)化邊界的處理，一定要仔細(xì)體會(huì)其中的妙處。
1. 紅黑樹的屬性
- 每個(gè)結(jié)點(diǎn)不是紅色就是黑色。
- 根結(jié)點(diǎn)是黑色。
- 每個(gè)葉子結(jié)點(diǎn)是黑色。
- 不允許兩個(gè)連續(xù)的紅色結(jié)點(diǎn)（某個(gè)結(jié)點(diǎn)為紅色，它的兩個(gè)子結(jié)點(diǎn)為黑色）。
- 從根到每個(gè)葉子結(jié)點(diǎn)的路徑上，黑色結(jié)點(diǎn)的個(gè)數(shù)相等。
1和3當(dāng)成不成文的規(guī)則，不需要在代碼里面特別維護(hù)，所以我們可以去掉，修改成3規(guī)則版本（因?yàn)閿?shù)量少，記憶方便）。另外還有一個(gè)事實(shí)——結(jié)點(diǎn)剛插入時(shí)統(tǒng)一為紅色，沒(méi)有體現(xiàn)在這些屬性里面。
1.1 三規(guī)則版本
- 不允許兩個(gè)連續(xù)的紅色結(jié)點(diǎn)。
- 從根到每個(gè)葉子結(jié)點(diǎn)的路徑上，黑色結(jié)點(diǎn)的個(gè)數(shù)相等。
- 根是黑色的。
1.2 示例
上圖中的3棵樹都不是合法的紅黑樹。第1棵，根結(jié)點(diǎn)不是黑色的；第2棵右邊黑色結(jié)點(diǎn)多1個(gè)；第3棵有兩個(gè)連續(xù)的紅色結(jié)點(diǎn)。
2. 樹的旋轉(zhuǎn)
旋轉(zhuǎn)的目的：用來(lái)調(diào)整某一側(cè)黑色結(jié)點(diǎn)數(shù)目的不平衡。
《算法導(dǎo)論》說(shuō)：左旋以x到y(tǒng)的鏈為『支軸』進(jìn)行。它使y成為該子樹新的根結(jié)點(diǎn)，x成為y的左孩子，y的左孩子成為x的右孩子。反正我是記不住，所以才有本文的存在。
旋轉(zhuǎn)有左旋和右旋，它們是對(duì)稱的關(guān)系，所以這里只討論一種。
將圖2右邊子樹的結(jié)點(diǎn)1左旋，可得到左邊的子樹。注意，圖2中的樹并不是合法的紅黑樹，這里只是用來(lái)演示旋轉(zhuǎn)的效果。我們來(lái)看幾個(gè)東西：
- 樹的旋轉(zhuǎn)，沒(méi)有影響搜索樹的性質(zhì)：比父結(jié)點(diǎn)小的在左子樹、比父結(jié)點(diǎn)大的在右子樹。
- 旋轉(zhuǎn)可以使子樹的某一側(cè)多一個(gè)某顏色的結(jié)點(diǎn)，同時(shí)不減少另一側(cè)該顏色的結(jié)點(diǎn)數(shù)量。我們看圖2的右邊子樹，結(jié)點(diǎn)1的右邊比左邊多了一個(gè)黑色，旋轉(zhuǎn)之后，黑色上升到根部，左邊多了1個(gè)黑色結(jié)點(diǎn)，同時(shí)右邊還是1個(gè)黑色并沒(méi)有減少。正因?yàn)槿绱?，?dāng)樹中黑色結(jié)點(diǎn)不平衡時(shí)，我們會(huì)通過(guò)旋轉(zhuǎn)來(lái)調(diào)整黑色結(jié)點(diǎn)數(shù)目。
- 旋轉(zhuǎn)操作到底是怎樣做的呢？圖2的例子中，我們可以想象1和它的右孩子3，圍繞圖中標(biāo)示的正方形中間的藍(lán)點(diǎn)，往左邊方向（逆時(shí)針）旋轉(zhuǎn)90度。旋轉(zhuǎn)之后我們還需要處理子結(jié)點(diǎn)：1的右孩子原來(lái)是3，旋轉(zhuǎn)之后空出來(lái)了，而3的左孩子2的位置被1霸占了，所以我們把2掛在1的右側(cè)。
3. 旋轉(zhuǎn)練習(xí)
下面放幾個(gè)樹的插入與刪除過(guò)程需要旋轉(zhuǎn)的示例，請(qǐng)大家認(rèn)真練習(xí)一下，然后觀察旋轉(zhuǎn)之后樹的紅黑結(jié)點(diǎn)有什么變化。只有熟練掌握了旋轉(zhuǎn)，之后在講插入與刪除時(shí)樹的調(diào)整，才能更好地理解和掌握。需要旋轉(zhuǎn)的結(jié)點(diǎn)在圖標(biāo)題上會(huì)注明，下一幅圖就是答案，在看答案之前，請(qǐng)自己先試著做一遍。
注意：在左旋結(jié)點(diǎn)4之后，這里額外把8和9的顏色修改了，這是插入調(diào)整中的某一步，先不管它，繼續(xù)練習(xí)旋轉(zhuǎn)即可。調(diào)整之后注意看左右子樹黑色結(jié)點(diǎn)的數(shù)目哦！
下圖是某個(gè)刪除過(guò)程的一個(gè)中間態(tài)，請(qǐng)左旋結(jié)點(diǎn)3.
左旋3之前，右邊的每條路徑比左邊的每條路徑多1個(gè)黑色結(jié)點(diǎn)，通過(guò)左旋結(jié)點(diǎn)3，使黑色結(jié)點(diǎn)5上升到根部，從而達(dá)到新的平衡。
4. 旋轉(zhuǎn)的代碼實(shí)現(xiàn)
private void rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
if (y.left != nil) {
y.left.parent = x;
}
Node parent = x.parent;
y.parent = parent;
if (parent == nil) {
root = y;
} else if (parent.left == x) {
parent.left = y;
} else {
parent.right = y;
}
y.left = x;
x.parent = y;
}
private void rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
if (y.right != nil) {
y.right.parent = x;
}
Node parent = x.parent;
y.parent = parent;
if (parent == nil) {
root = y;
} else if (parent.left == x) {
parent.left = y;
} else {
parent.right = y;
}
y.right = x;
x.parent = y;
}
5. 結(jié)語(yǔ)
之前在學(xué)校的時(shí)候，發(fā)現(xiàn)自己和許多的同學(xué)都弄不懂紅黑樹是怎么一回事，永遠(yuǎn)搞不懂為什么插入有3種情況、刪除有4種情況，別提記住了，更別提能把代碼寫出來(lái)了。本文就是為后面的理解打好基礎(chǔ)。
通過(guò)本文的練習(xí)，想必大家對(duì)旋轉(zhuǎn)的原理、旋轉(zhuǎn)的步驟、旋轉(zhuǎn)的效果都掌握得比較清楚了，下一章我們將正式進(jìn)入紅黑樹的難點(diǎn)——插入與刪除。
源碼
轉(zhuǎn)載聲明
如果您需要轉(zhuǎn)載，請(qǐng)注明轉(zhuǎn)載來(lái)源。
