概述
紅黑樹是一種自平衡二叉查找樹,它相對于二叉查找樹性能會更加高效(查找、刪除什湘、添加等操作需要O(log n),其中n為樹中元素的個數(shù)),但實(shí)現(xiàn)較為復(fù)雜(需要保持自身的平衡).
性質(zhì)
紅黑樹與二叉查找樹不同,它的節(jié)點(diǎn)多了一個顏色屬性,每個節(jié)點(diǎn)非黑即紅,這也是它名字的由來.
紅黑樹的節(jié)點(diǎn)定義如以下代碼:
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
private class Node {
private int size = 0;
private boolean color = RED; //顏色
private Node parent, left, right;
private int orderStatus = 0;
private K key;
private V value;
public Node(K key, V value) {
this.key = key;
this.value = value;
this.size = 1;
}
}
完整的代碼我已經(jīng)放在了我的Gist中,點(diǎn)擊查看完整代碼.
紅黑樹需要保證以下性質(zhì):
- 每個節(jié)點(diǎn)的顏色非黑即紅.
- 根節(jié)點(diǎn)的顏色為黑色.
- 所有葉子節(jié)點(diǎn)都為黑色(即NIL節(jié)點(diǎn)).
每個紅色節(jié)點(diǎn)的兩個子節(jié)點(diǎn)都必須為黑色(不能有兩個連續(xù)的紅節(jié)點(diǎn)).
從任一節(jié)點(diǎn)到其葉子的所有簡單路徑包含相同數(shù)量的黑色節(jié)點(diǎn).
插入
紅黑樹的查找操作與二叉查找樹一致(因?yàn)椴檎也粫绊憳涞慕Y(jié)構(gòu)),而插入與刪除操作需要在最后對樹進(jìn)行調(diào)整.
我們將新的節(jié)點(diǎn)的顏色設(shè)為紅色(如果設(shè)為黑色會使根節(jié)點(diǎn)到葉子的一條路徑上多了一個黑節(jié)點(diǎn),違反了性質(zhì)5,這個是很難調(diào)整的).
現(xiàn)在我們假設(shè)新節(jié)點(diǎn)為N,它的父節(jié)點(diǎn)為P(且P為G的左節(jié)點(diǎn),如果為右節(jié)點(diǎn)則與其操作互為鏡像),祖父節(jié)點(diǎn)為G,叔叔節(jié)點(diǎn)為U.插入一個節(jié)點(diǎn)會有以下種情況.
情況1
N位于根,它沒有父節(jié)點(diǎn)與子節(jié)點(diǎn),這時(shí)候只需要把它重新設(shè)置為黑色即可,無需其他調(diào)整.
情況2
P的顏色為黑色,這種情況下保持了性質(zhì)4(N只有兩個葉子節(jié)點(diǎn),它們都為黑色)與性質(zhì)5(N是一個紅色節(jié)點(diǎn),不會對其造成影響)的有效,所以無需調(diào)整.
情況3
如果P與U都為紅色,我們可以將它們兩個重新繪制為黑色,然后將G繪制為紅色(保持性質(zhì)5),最后再從G開始繼續(xù)向上進(jìn)行調(diào)整.
情況4
P為紅色,U為黑色,且N為P的左子節(jié)點(diǎn),這種情況下,我們需要在G處進(jìn)行一次右旋轉(zhuǎn),結(jié)果滿足了性質(zhì)4與性質(zhì)5,因?yàn)橥ㄟ^這三個節(jié)點(diǎn)中任何一個的所有路徑以前都通過祖父節(jié)點(diǎn)G晴股，現(xiàn)在它們都通過以前的父節(jié)點(diǎn)P.
關(guān)于旋轉(zhuǎn)操作,可以查看這篇文章《Algorithms,4th Edition》讀書筆記-紅黑二叉查找樹.
情況5
P為紅色,U為黑色,且N為P的右子節(jié)點(diǎn),我們需要先在P處進(jìn)行一次左旋轉(zhuǎn),這樣就又回到了情況4.
代碼
private void fixAfterInsertion(Node x) {
while (x != null && x != root && colorOf(parentOf(x)) == RED) {
if (parentOf(x) == grandpaOf(x).left) {
x = parentIsLeftNode(x);
} else {
x = parentIsRightNode(x);
}
fixSize(x);
}
setColor(root, BLACK);
}
private Node parentIsLeftNode(Node x) {
Node xUncle = grandpaOf(x).right;
// 情況3
if (colorOf(xUncle) == RED) {
x = uncleColorIsRed(x, xUncle);
} else {
// 情況5
if (x == parentOf(x).right) {
x = parentOf(x);
rotateLeft(x);
}
// 情況4
rotateRight(grandpaOf(x));
}
return x;
}
private Node parentIsRightNode(Node x) {
Node xUncle = grandpaOf(x).left;
if (colorOf(xUncle) == RED) {
x = uncleColorIsRed(x, xUncle);
} else {
if (x == parentOf(x).left) {
x = parentOf(x);
rotateRight(x);
}
rotateLeft(grandpaOf(x));
}
return x;
}
private Node uncleColorIsRed(Node x, Node xUncle) {
setColor(parentOf(x), BLACK);
setColor(xUncle, BLACK);
setColor(grandpaOf(x), RED);
x = grandpaOf(x);
return x;
}
刪除
我們只考慮刪除節(jié)點(diǎn)只有一個子節(jié)點(diǎn)的情況,且只有后繼節(jié)點(diǎn)與刪除節(jié)點(diǎn)都為黑色(如果刪除節(jié)點(diǎn)為紅色,從根節(jié)點(diǎn)到葉子節(jié)點(diǎn)的每條路徑上少了一個紅色節(jié)點(diǎn)并不會違反紅黑樹的性質(zhì),而如果后繼節(jié)點(diǎn)為紅色,只需要將它重新繪制為黑色即可).
先將刪除節(jié)點(diǎn)替換為后繼節(jié)點(diǎn),且后繼節(jié)點(diǎn)定義為N,它的兄弟節(jié)點(diǎn)為S.
情況1
N為新的根節(jié)點(diǎn),在這種情況下只需要把根節(jié)點(diǎn)保持為黑色即可.
情況2
S為紅色,只需要在P進(jìn)行一次左旋轉(zhuǎn),接下來則繼續(xù)按以下情況進(jìn)行處理(盡管路徑上的黑色節(jié)點(diǎn)數(shù)量沒有改變,但N有了一個黑色的兄弟節(jié)點(diǎn)與紅色的父節(jié)點(diǎn)).
情況3
S和它的子節(jié)點(diǎn)都是黑色的,而P為紅色.這種情況下只需要將S與P的顏色進(jìn)行交換
情況4
S和它的子節(jié)點(diǎn)都是黑色的,這種情況下需要把S重新繪制為紅色.這時(shí)不通過N的路徑都將少一個黑色節(jié)點(diǎn)(通過N的路徑因?yàn)閯h除節(jié)點(diǎn)是黑色的也都少了一個黑色節(jié)點(diǎn)),這讓它們平衡了起來.
但現(xiàn)在通過P的路徑比不通過P的路徑都少了一個黑色節(jié)點(diǎn),所以還需要在P上繼續(xù)進(jìn)行調(diào)整.
情況5
S為黑色,它的左子節(jié)點(diǎn)為紅色,右子節(jié)點(diǎn)為黑色.這種情況下,我們在S上做右旋轉(zhuǎn),這樣S的左兒子成為S的父親和N的新兄弟。我們接著交換S和它的新父親的顏色。所有路徑仍有同樣數(shù)目的黑色節(jié)點(diǎn)辐脖，但是現(xiàn)在N有了一個右兒子是紅色的黑色兄弟狭莱，所以我們進(jìn)入了情況6僵娃。N和P都不受這個變換的影響。
情況6
S是黑色腋妙，它的右子節(jié)點(diǎn)是紅色,我們在N的父親P上做左旋轉(zhuǎn).這樣S成為N的父親和S的右兒子的父親默怨。我們接著交換N的父親和S的顏色，并使S的右兒子為黑色骤素。子樹在它的根上的仍是同樣的顏色,但是,N現(xiàn)在增加了一個黑色祖先.所以,通過N的路徑都增加了一個黑色節(jié)點(diǎn).此時(shí),如果一個路徑不通過N,則有兩種可能性:
- 它通過
N的新兄弟.那么它以前和現(xiàn)在都必定通過S和N的父親,而它們只是交換了顏色.所以路徑保持了同樣數(shù)目的黑色節(jié)點(diǎn).
- 它通過
N的新叔父,S的右兒子.那么它以前通過S匙睹、S的父親和S的右兒子,但是現(xiàn)在只通過S,它被假定為它以前的父親的顏色,和S的右兒子,它被從紅色改變?yōu)楹谏?合成效果是這個路徑通過了同樣數(shù)目的黑色節(jié)點(diǎn).
在任何情況下,在這些路徑上的黑色節(jié)點(diǎn)數(shù)目都沒有改變.所以我們恢復(fù)了性質(zhì)4.在示意圖中的白色節(jié)點(diǎn)可以是紅色或黑色,但是在變換前后都必須指定相同的顏色.
代碼
private void fixAfterDeletion(Node x) {
while (x != null && x != root && colorOf(x) == BLACK) {
if (x == parentOf(x).left) {
x = successorIsLeftNode(x);
} else {
x = successorIsRightNode(x);
}
}
setColor(x, BLACK);
}
private Node successorIsLeftNode(Node x) {
Node brother = parentOf(x).right;
// 情況2
if (colorOf(brother) == RED) {
rotateLeft(parentOf(x));
brother = parentOf(x).right;
}
// 情況3,4
if (colorOf(brother.left) == BLACK && colorOf(brother.right) == BLACK) {
x = brotherChildrenColorIsBlack(x, brother);
} else {
// 情況5
if (colorOf(brother.right) == BLACK) {
rotateRight(brother);
brother = parentOf(x).right;
}
// 情況6
setColor(brother.right, BLACK);
rotateLeft(parentOf(x));
x = root;
}
return x;
}
private Node brotherChildrenColorIsBlack(Node x, Node brother) {
setColor(brother, RED);
x = parentOf(x);
return x;
}
參考資料
本文作者為SylvanasSun(sylvanassun_xtz@163.com),轉(zhuǎn)載請務(wù)必指明原文鏈接.
