|
紅黑樹的性質(zhì)與定義 紅黑樹(red-black tree)是一棵滿足下述性質(zhì)的二叉查找樹： 1. 每一個結(jié)點要么是紅色，要么是黑色。 2. 根結(jié)點是黑色的。 3. 所有葉子結(jié)點都是黑色的（實際上都是Null指針，下圖用NIL表示）。葉子結(jié)點不包含任何關(guān)鍵字信息，所有查詢關(guān)鍵字都在非終結(jié)點上。 4. 每個紅色結(jié)點的兩個子節(jié)點必須是黑色的。換句話說：從每個葉子到根的所有路徑上不能有兩個連續(xù)的紅色結(jié)點 5. 從任一結(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色結(jié)點  黑深度 ——從某個結(jié)點x出發(fā)(不包括結(jié)點x本身)到葉結(jié)點(包括葉子結(jié)點)的路徑上的黑結(jié)點個數(shù),稱為該結(jié)點x的黑深度,記為bd(x),根結(jié)點的黑深度就是該紅黑樹的黑深度。葉子結(jié)點的黑深度為0。比如：上圖bd(13)=2，bd(8)=2，bd(1)=1內(nèi)部結(jié)點—— 紅黑樹的非終結(jié)點 外部節(jié)點—— 紅黑樹的葉子結(jié)點 紅黑樹相關(guān)定理 1. 從根到葉子的最長的可能路徑不多于最短的可能路徑的兩倍長。 根據(jù)上面的性質(zhì)5我們知道上圖的紅黑樹每條路徑上都是3個黑結(jié)點。因此最短路徑長度為2(沒有紅結(jié)點的路徑)。再根據(jù)性質(zhì)4(兩個紅結(jié)點不能相連)和性質(zhì)1，2(葉子和根必須是黑結(jié)點)。那么我們可以得出：一條具有3個黑結(jié)點的路徑上最多只能有2個紅結(jié)點(紅黑間隔存在)。也就是說黑深度為2（根結(jié)點也是黑色）的紅黑樹最長路徑為4，最短路徑為2。從這一點我們可以看出紅黑樹是大致平衡的。(當(dāng)然比平衡二叉樹要差一些，AVL的平衡因子最多為1) 2. 紅黑樹的樹高(h)不大于兩倍的紅黑樹的黑深度(bd)，即h<=2bd 根據(jù)定理1，我們不難說明這一點。bd是紅黑樹的最短路徑長度。而可能的最長路徑長度(樹高的最大值)就是紅黑相間的路徑，等于2bd。因此h<=2bd。 3. 一棵擁有n個內(nèi)部結(jié)點(不包括葉子結(jié)點)的紅黑樹的樹高h(yuǎn)<=2log(n+1) 下面我們首先證明一顆有n個內(nèi)部結(jié)點的紅黑樹滿足n>=2^bd-1。這可以用數(shù)學(xué)歸納法證明，施歸納于樹高h(yuǎn)。當(dāng)h=0時，這相當(dāng)于是一個葉結(jié)點，黑高度bd為0，而內(nèi)部結(jié)點數(shù)量n為0，此時0>=2^0-1成立。假設(shè)樹高h(yuǎn)<=t時，n>=2^bd-1成立，我們記一顆樹高 為t+1的紅黑樹的根結(jié)點的左子樹的內(nèi)部結(jié)點數(shù)量為nl，右子樹的內(nèi)部結(jié)點數(shù)量為nr，記這兩顆子樹的黑高度為bd'（注意這兩顆子樹的黑高度必然一 樣），顯然這兩顆子樹的樹高<=t，于是有nl>=2^bd'-1以及nr>=2^bd'-1，將這兩個不等式相加有nl+nr>=2^(bd'+1)-2，將該不等式左右加1，得到n>=2^(bd'+1)-1，很顯然bd'+1>=bd，于是前面的不等式可以 變?yōu)閚>=2^bd-1，這樣就證明了一顆有n個內(nèi)部結(jié)點的紅黑樹滿足n>=2^bd-1。 在根據(jù)定理2，h<=2bd。即n>=2^(h/2)-1，那么h<=2log(n+1) 從這里我們能夠看出，紅黑樹的查找長度最多不超過2log(n+1)，因此其查找時間復(fù)雜度也是O(log N)級別的。 紅黑樹的操作 因為每一個紅黑樹也是一個特化的二叉查找樹，因此紅黑樹上的查找操作與普通二叉查找樹上的查找操作相同。然而，在紅黑樹上進行插入操作和刪除操作會導(dǎo)致不 再符合紅黑樹的性質(zhì)。恢復(fù)紅黑樹的屬性需要少量(O(log n))的顏色變更(實際是非?？焖俚?和不超過三次樹旋轉(zhuǎn)(對于插入操作是兩次)。雖然插入和刪除很復(fù)雜，但操作時間仍可以保持為 O(log n)次。 插入操作 我們首先以二叉查找樹的方法增加節(jié)點并標(biāo)記它為紅色。（如果設(shè)為黑色，就會導(dǎo)致根到葉子的路徑上有一條路上，多一個額外的黑節(jié)點，這個是很難調(diào)整的。但是設(shè)為紅色節(jié)點后，可能會導(dǎo)致出現(xiàn)兩個連續(xù)紅色節(jié)點的沖突，那么可以通過顏色調(diào)換（color flips）和樹旋轉(zhuǎn)來調(diào)整。）下面要進行什么操作取決于其他臨近節(jié)點的顏色。同人類的家族樹中一樣，我們將使用術(shù)語叔父節(jié)點來指一個節(jié)點的父節(jié)點的兄弟節(jié)點。 假設(shè)新加入的結(jié)點為N，父親結(jié)點為P，叔父結(jié)點為Ui(叔父結(jié)點就是一些列P的兄弟結(jié)點)，祖父結(jié)點G(父親結(jié)點P的父親)。下面會給出每一種情況，我們將使用C示例代碼來展示。通過下列函數(shù)，可以找到一個節(jié)點的叔父和祖父節(jié)點:
node grandparent(node n) {
return n->parent->parent;
}
node uncle(node n) {
if (n->parent == grandparent(n)->left)
return grandparent(n)->right;
else
return grandparent(n)->left;
}
情況1. 當(dāng)前紅黑樹為空，新結(jié)點N位于樹的根上，沒有父結(jié)點。 此時很簡單，我們將直接插入一個黑結(jié)點N（滿足性質(zhì)2），其他情況下插入的N為紅色（原因在前面提到了）。
void insert_case1(node n) {
if (n->parent == NULL)
n->color = BLACK;
else
insert_case2(n); //插入情況2
}
情況2. 新結(jié)點N的父結(jié)點P是黑色。 在這種情況下，我們插入一個紅色結(jié)點N(滿足性質(zhì)5)。
void insert_case2(node n) {
if (n->parent->color == BLACK)
return; // 樹仍舊有效
else
insert_case3(n); //插入情況3
}
注意：在情況3，4，5下，我們假定新節(jié)點有祖父節(jié)點，因為父節(jié)點是紅色；并且如果它是根，它就應(yīng)當(dāng)是黑色。所以新節(jié)點總有一個叔父節(jié)點，盡管在情形4和5下它可能是葉子。 情況3.如果父節(jié)點P和叔父節(jié)點U二者都是紅色。 如下圖，因為新加入的N結(jié)點必須為紅色，那么我們可以將父結(jié)點P(保證性質(zhì)4)，以及N的叔父結(jié)點U(保證性質(zhì)5)重新繪制成黑色。如果此時祖父結(jié)點G是根，則結(jié)束變化。如果不是根，則祖父結(jié)點重繪為紅色(保證性質(zhì)5)。但是，G的父親也可能是紅色的，為了保證性質(zhì)4。我們把G遞歸當(dāng)做新加入的結(jié)點N在進行各種情況的重新檢查。
void insert_case3(node n) {
if (uncle(n) != NULL && uncle(n)->color == RED) {
n->parent->color = BLACK;
uncle(n)->color = BLACK;
grandparent(n)->color = RED;
insert_case1(grandparent(n));
}
else
insert_case4(n);
}
注意：在情形4和5下，我們假定父節(jié)點P 是祖父結(jié)點G 的左子節(jié)點。如果它是右子節(jié)點，情形4和情形5中的左和右應(yīng)當(dāng)對調(diào)。 情況4. 父節(jié)點P是紅色而叔父節(jié)點U是黑色或缺少; 另外，新節(jié)點N是其父節(jié)點P的右子節(jié)點，而父節(jié)點P又是祖父結(jié)點G的左子節(jié)點。 如下圖, 在這種情形下，我們進行一次左旋轉(zhuǎn)調(diào)換新節(jié)點和其父節(jié)點的角色（與AVL樹的左旋轉(zhuǎn)相同）; 這導(dǎo)致某些路徑通過它們以前不通過的新節(jié)點N或父節(jié)點P中的一個，但是這兩個節(jié)點都是紅色的，所以性質(zhì)5沒有失效。但目前情況將違反性質(zhì)4，所以接著，我們按下面的情況5繼續(xù)處理以前的父節(jié)點P。 
void insert_case4(node n) {
if (n == n->parent->right && n->parent == grandparent(n)->left) {
rotate_left(n->parent);
n = n->left;
} else if (n == n->parent->left && n->parent == grandparent(n)->right) {
rotate_right(n->parent);
n = n->right;
}
insert_case5(n)
}
情況5. 父節(jié)點P是紅色而叔父節(jié)點U 是黑色或缺少，新節(jié)點N 是其父節(jié)點的左子節(jié)點，而父節(jié)點P又是祖父結(jié)點的G的左子節(jié)點。 如下圖： 在這種情形下，我們進行針對祖父節(jié)點P 的一次右旋轉(zhuǎn); 在旋轉(zhuǎn)產(chǎn)生的樹中，以前的父節(jié)點P現(xiàn)在是新節(jié)點N和以前的祖父節(jié)點G的父節(jié)點。我們知道以前的祖父節(jié)點G是黑色，否則父節(jié)點P就不可能是紅色。我們切換以前的父節(jié)點P和祖父節(jié)點G的顏色，結(jié)果的樹滿足性質(zhì)4[3]。性質(zhì)5[4]也仍然保持滿足，因為通過這三個節(jié)點中任何一個的所有路徑以前都通過祖父節(jié)點G，現(xiàn)在它們都通過以前的父節(jié)點P。在各自的情形下，這都是三個節(jié)點中唯一的黑色節(jié)點。 
void insert_case5(node n) {
n->parent->color = BLACK;
grandparent(n)->color = RED;
if (n == n->parent->left && n->parent == grandparent(n)->left) {
rotate_right(grandparent(n));
} else {
/* Here, n == n->parent->right && n->parent == grandparent(n)->right */
rotate_left(grandparent(n));
}
}
刪除操作 如果需要刪除的節(jié)點有兩個兒子，那么問題可以被轉(zhuǎn)化成刪除另一個只有一個兒子的節(jié)點的問題（為了表述方便，這里所指的兒子，為非葉子節(jié)點的兒子）。 對于二叉查找樹，在刪除帶有兩個非葉子兒子的節(jié)點的時候，我們找到要么在它的左子樹中的最大元素、要么在它的右子樹中的最小元素，并把它的值轉(zhuǎn)移到要刪除 的節(jié)點中(如在這里所展示的那樣)。我們接著刪除我們從中復(fù)制出值的那個節(jié)點，它必定有少于兩個非葉子的兒子。因為只是復(fù)制了一個值而不違反任何屬性，這 就把問題簡化為如何刪除最多有一個兒子的節(jié)點的問題。它不關(guān)心這個節(jié)點是最初要刪除的節(jié)點還是我們從中復(fù)制出值的那個節(jié)點。 在本文余下的部分中，我們只需要討論刪除只有一個兒子的節(jié)點(如果它兩個兒子都為空，即均為葉子，我們?nèi)我鈱⑵渲幸粋€看作它的兒子)。如果我們刪除一個紅色節(jié)點，它的父親和兒子一定是黑色的。所以我們可以簡單的用它的黑色兒子替換它，并不會破壞屬性3和4。通過被刪除節(jié)點的所有路徑只是少了一個紅色 節(jié)點，這樣可以繼續(xù)保證屬性5。另一種簡單情況是在被刪除節(jié)點是黑色而它的兒子是紅色的時候。如果只是去除這個黑色節(jié)點，用它的紅色兒子頂替上來的話，會 破壞屬性4，但是如果我們重繪它的兒子為黑色，則曾經(jīng)通過它的所有路徑將通過它的黑色兒子，這樣可以繼續(xù)保持屬性4。 需要進一步討論的是在要刪除的節(jié)點和它的兒子二者都是黑色的時候，這是一種復(fù)雜的情況。我們首先把要刪除的節(jié)點替換為它的兒子。出于方便，稱呼這個兒子為N，稱呼它的兄弟(它父親的另一個兒子)為S。在下面的示意圖中，我們還是使用P稱呼N的父親，SL稱呼S的左兒子，SR稱呼S的右兒子。我們將使用下述 函數(shù)找到兄弟節(jié)點:
struct node * sibling(struct node *n)
{
if (n == n->parent->left)
return n->parent->right;
else
return n->parent->left;
}
我們可以使用下列代碼進行上述的概要步驟，這里的函數(shù) replace_node 替換 child 到 n 在樹中的位置。出于方便，在本章節(jié)中的代碼將假定空葉子被用不是 NULL 的實際節(jié)點對象來表示(在插入章節(jié)中的代碼可以同任何一種表示一起工作)。
void delete_one_child(struct node *n)
{
/*
* Precondition: n has at most one non-null child.
*/
struct node *child = is_leaf(n->right) ? n->left : n->right;
replace_node(n, child);
if (n->color == BLACK) {
if (child->color == RED)
child->color = BLACK;
else
delete_case1(child);
}
free(n);
}
如果 N 和它初始的父親是黑色，則刪除它的父親導(dǎo)致通過 N 的路徑都比不通過它的路徑少了一個黑色節(jié)點。因為這違反了屬性 4，樹需要被重新平衡。有幾種情況需要考慮: 情況1. N 是新的根。 在這種情況下，我們就做完了。我們從所有路徑去除了一個黑色節(jié)點，而新根是黑色的，所以屬性都保持著。
void delete_case1(struct node *n)
{
if (n->parent != NULL)
delete_case2(n);
}
注意: 在情況2、5和6下，我們假定 N 是它父親的左兒子。如果它是右兒子，則在這些情況下的左和右應(yīng)當(dāng)對調(diào)。 情況2. S 是紅色。 在這種情況下我們在N的父親上做左旋轉(zhuǎn)，把紅色兄弟轉(zhuǎn)換成N的祖父。我們接著對調(diào) N的父親和祖父的顏色。盡管所有的路徑仍然有相同數(shù)目的黑色節(jié)點，現(xiàn)在 N 有了一個黑色的兄弟和一個紅色的父親，所以我們可以接下去按4、5或6情況來處理。(它的新兄弟是黑色因為它是紅色S的一個兒子。) 
void delete_case2(struct node *n)
{
struct node *s = sibling(n);
if (s->color == RED) {
n->parent->color = RED;
s->color = BLACK;
if (n == n->parent->left)
rotate_left(n->parent);
else
rotate_right(n->parent);
}
delete_case3(n);
}
情況 3: N 的父親、S 和 S 的兒子都是黑色的。 在這種情況下，我們簡單的重繪 S為紅色。結(jié)果是通過S的所有路徑, 它們就是以前不通過 N 的那些路徑，都少了一個黑色節(jié)點。因為刪除 N 的初始的父親使通過 N的所有路徑少了一個黑色節(jié)點，這使事情都平衡了起來。但是，通過 P 的所有路徑現(xiàn)在比不通過 P的路徑少了一個黑色節(jié)點，所以仍然違反屬性4。要修正這個問題，我們要從情況 1 開始，在 P 上做重新平衡處理。 
void delete_case3(struct node *n)
{
struct node *s = sibling(n);
if ((n->parent->color == BLACK) &&
(s->color == BLACK) &&
(s->left->color == BLACK) &&
(s->right->color == BLACK)) {
s->color = RED;
delete_case1(n->parent);
} else
delete_case4(n);
}
情況4. S 和 S 的兒子都是黑色，但是 N 的父親是紅色。 在這種情況下，我們簡單的交換 N 的兄弟和父親的顏色。這不影響不通過 N 的路徑的黑色節(jié)點的數(shù)目，但是它在通過 N 的路徑上對黑色節(jié)點數(shù)目增加了一，添補了在這些路徑上刪除的黑色節(jié)點。 
void delete_case4(struct node *n)
{
struct node *s = sibling(n);
if ((n->parent->color == RED) &&
(s->color == BLACK) &&
(s->left->color == BLACK) &&
(s->right->color == BLACK)) {
s->color = RED;
n->parent->color = BLACK;
} else
delete_case5(n);
}
情況5. S 是黑色，S 的左兒子是紅色，S 的右兒子是黑色，而 N是它父親的左兒子。 在這種情況下我們在 S 上做右旋轉(zhuǎn)，這樣 S 的左兒子成為 S 的父親和 N 的新兄弟。我們接著交換 S和它的新父親的顏色。所有路徑仍有同樣數(shù)目的黑色節(jié)點，但是現(xiàn)在 N 有了一個右兒子是紅色的黑色兄弟，所以我們進入了情況 6。N和它的父親都不受這個變換的影響。 
void delete_case5(struct node *n)
{
struct node *s = sibling(n);
if (s->color == BLACK)
/* this if statement is trivial,
due to Case 2 (even though Case two changed the sibling to a sibling's child,
the sibling's child can't be red, since no red parent can have a red child). */
// the following statements just force the red to be on the left of the left of the parent,
// or right of the right, so case six will rotate correctly.
if ((n == n->parent->left) &&
(s->right->color == BLACK) &&
(s->left->color == RED)) { // this last test is trivial too due to cases 2-4.
s->color = RED;
s->left->color = BLACK;
rotate_right(s);
} else if ((n == n->parent->right) &&
(s->left->color == BLACK) &&
(s->right->color == RED)) {// this last test is trivial too due to cases 2-4.
s->color = RED;
s->right->color = BLACK;
rotate_left(s);
}
}
delete_case6(n);
}
情況6. S 是黑色，S 的右兒子是紅色，而 N是它父親的左兒子。 在這種情況下我們在 N 的父親上做左旋轉(zhuǎn)，這樣 S 成為 N 的父親和 S 的右兒子的父親。我們接著交換 N 的父親和 S的顏色，并使 S 的右兒子為黑色。子樹在它的根上的仍是同樣的顏色，所以屬性 3 沒有被違反。但是，N 現(xiàn)在增加了一個黑色祖先: 要么 N的父親變成黑色，要么它是黑色而 S 被增加為一個黑色祖父。所以，通過 N 的路徑都增加了一個黑色節(jié)點。 此時，如果一個路徑不通過 N，則有兩種可能性: 它通過 N 的新兄弟。那么它以前和現(xiàn)在都必定通過 S 和 N 的父親，而它們只是交換了顏色。所以路徑保持了同樣數(shù)目的黑色節(jié)點。
它通過 N 的新叔父，S 的右兒子。那么它以前通過 S、S 的父親和 S 的右兒子，但是現(xiàn)在只通過 S，它被假定為它以前的父親的顏色，和 S 的右兒子，它被從紅色改變?yōu)楹谏?。合成效果是這個路徑通過了同樣數(shù)目的黑色節(jié)點。 在任何情況下，在這些路徑上的黑色節(jié)點數(shù)目都沒有改變。所以我們恢復(fù)了屬性 4。在示意圖中的白色節(jié)點可以是紅色或黑色，但是在變換前后都必須指定相同的顏色。 
void delete_case6(struct node *n)
{
struct node *s = sibling(n);
s->color = n->parent->color;
n->parent->color = BLACK;
if (n == n->parent->left) {
s->right->color = BLACK;
rotate_left(n->parent);
} else {
s->left->color = BLACK;
rotate_right(n->parent);
}
}
同樣的，函數(shù)調(diào)用都使用了尾部遞歸，所以算法是就地的。此外，在旋轉(zhuǎn)之后不再做遞歸調(diào)用，所以進行了恒定數(shù)目(最多 3 次)的旋轉(zhuǎn)。 紅黑樹的優(yōu)勢 紅黑樹能夠以O(shè)(log2(N))的時間復(fù)雜度進行搜索、插入、刪除操作。此外,任何不平衡都會在3次旋轉(zhuǎn)之內(nèi)解決。這一點是AVL所不具備的。 而且實際應(yīng)用中，很多語言都實現(xiàn)了紅黑樹的數(shù)據(jù)結(jié)構(gòu)。比如 TreeMap, TreeSet(Java )、 STL(C++)等。 |
|
|
