Explain
一、紅黑樹(shù)的性質(zhì)紅黑樹(shù)是每個(gè)節(jié)點(diǎn)都帶有顏色屬性的二叉查找樹(shù)，顏色為紅色或黑色。在二叉查找樹(shù)強(qiáng)制一般要求以外，對(duì)于任何有效的紅黑樹(shù)我們?cè)黾恿巳缦碌念~外要求: 性質(zhì)1. 節(jié)點(diǎn)是紅色或黑色。 性質(zhì)2. 根是黑色。 性質(zhì)3. 所有葉子都是黑色（葉子是NIL節(jié)點(diǎn)）。 性質(zhì)4. 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色。(從每個(gè)葉子到根的所有路徑上不能有兩個(gè)連續(xù)的紅色節(jié)點(diǎn)) 性質(zhì)5. 從任一節(jié)點(diǎn)到其每個(gè)葉子的所有簡(jiǎn)單路徑都包含相同數(shù)目的黑色節(jié)點(diǎn)。 這些約束強(qiáng)制了紅黑樹(shù)的關(guān)鍵性質(zhì): 從根到葉子的最長(zhǎng)的可能路徑不多于最短的可能路徑的兩倍長(zhǎng)（性質(zhì)4 保證了路徑最長(zhǎng)的情況為一紅一黑，最短的情況為全黑，再結(jié)合性質(zhì)5，可以推導(dǎo)出）。結(jié)果是這個(gè)樹(shù)大致上是平衡的。因?yàn)椴僮鞅热绮迦搿h除和查找某個(gè)值的最壞情況時(shí)間都要求與樹(shù)的高度成比例，這個(gè)在高度上的理論上限允許紅黑樹(shù)在最壞情況下都是高效的，而不同于普通的二叉查找樹(shù)。 紅黑樹(shù)結(jié)構(gòu)定義： /* * RBTree.h * * Created on: Sep 25, 2014 * Author: root */ #ifndef RBTREE_H_ #define RBTREE_H_ typedef unsigned long rbtree_key_t; typedef long rbtree_key_int_t; struct rbtree_node_t { rbtree_key_t key; //key rbtree_node_t *left; //左子樹(shù) rbtree_node_t *right; //右子樹(shù) rbtree_node_t *parent; //父節(jié)點(diǎn) unsigned char color; //顏色 }; struct rbtree_t { rbtree_node_t *root; //根節(jié)點(diǎn) rbtree_node_t *sentinel; //哨兵 }; #endif /* RBTREE_H_ */
二、樹(shù)的旋轉(zhuǎn)知識(shí) 1.左旋 如上圖所示： 當(dāng)在某個(gè)結(jié)點(diǎn)pivot上，做左旋操作時(shí)，我們假設(shè)它的右孩子y不是NIL[T]，pivot可以為樹(shù)內(nèi)任意右孩子而不是NIL[T]的結(jié)點(diǎn)。 左旋以pivot到y(tǒng)之間的鏈為“支軸”進(jìn)行，它使y成為該孩子樹(shù)新的根，而y的左孩子b則成為pivot的右孩子。
偽代碼圖解：
實(shí)現(xiàn)代碼： void RBTree::rbtree_left_rotate( rbtree_node_t* node_x) { rbtree_node_t *node_y; rbtree_node_t **root = & m_rbtree. root; rbtree_node_t *sentinel = m_rbtree. sentinel; node_y = node_x-> right; //Setp 1. 設(shè)置y node_x-> right = node_y-> left; //Step 2 .將y 的左子樹(shù)變?yōu)閤的右子樹(shù) if(node_y-> left != sentinel) { node_y-> left-> parent = node_x; } node_y-> parent = node_x-> parent; //Step 3. 設(shè)置y的父親 if(node_x == *root) //空樹(shù)，將y設(shè)為根 { *root = node_y; } else if(node_x == node_x->parent ->left ) //x為左子樹(shù)，將y放在x父節(jié)點(diǎn)的左子樹(shù) { node_x-> parent-> left = node_y; } else //x為右子樹(shù)，將y放在x父節(jié)點(diǎn)的右子樹(shù) { node_x-> parent-> right = node_y; } node_y-> left = node_x; //Step4.將x鏈到y(tǒng)的左子樹(shù) node_x-> parent = node_y; }
2.右旋
偽代碼圖解：
實(shí)現(xiàn)代碼： void rb_tree::rbtree_right_rotate( rbtree_node_t *node_x) { rbtree_node_t *node_y; rbtree_node_t **root = & m_rbtree. root; rbtree_node_t *sentinel = m_rbtree. sentinel; node_y = node_x-> left; //Step 1. 設(shè)置y node_x-> left = node_y-> right; //Step 2.將y的右子樹(shù)變?yōu)閤的左子樹(shù) if( node_y-> right != sentinel) { node_y-> right-> parent = node_x; } node_y-> parent = node_x-> parent; if( node_x == *root) //Step 3.若x為根，設(shè)置y為跟 { *root = node_y; } else if( node_x == node_x->parent ->right ) //x在右子樹(shù)，y設(shè)置在右子樹(shù) { node_x-> parent-> right = node_y; } else //x在左子樹(shù)，y設(shè)置在左子樹(shù) { node_x-> parent-> left = node_y; } node_y-> right = node_x; //Step 4.將x鏈接在y的右子樹(shù) node_x-> parent = node_y; }
三、紅黑樹(shù)的插入 紅黑樹(shù)的插入和二叉樹(shù)的相似，都是如果左子樹(shù)小，向左子樹(shù)搜索，否則向右子樹(shù)搜索，不同的紅黑樹(shù)插入完需要調(diào)整，恢復(fù)紅黑樹(shù)的特性，偽代碼如下 ： RB-INSERT(T,z) y <- NIL[T] //Step 1.將y設(shè)置為哨兵,將x設(shè)置為根 x <- root[T] while x!=NIL[T] //Step 2.搜索，如果z比x小，向左子樹(shù)搜索，否則向右子樹(shù)搜索，y插入位置 do y <- x if key[z] < key[x] then x <- left[x] else x <- right[x] p[z] <- y if y=NIL[T] //Step 3.若為空樹(shù)，z為根， then root[T] <- z else if key[z] < key[y] //若z比y小，z放在y的左子樹(shù) then left[y] <- z else right[y] <- z //否則，z放在y的右子樹(shù) left[z] <- NIL[T] right[z] <- NIL[T] //Step 4.將z左右子樹(shù)設(shè)置為哨兵，顏色設(shè)置為紅色 color[z] <- RED RB-INSERT-FIXUP(T,z) //Step 5.紅黑樹(shù)調(diào)整 實(shí)現(xiàn)代碼： void RBTree::rbtree_insert( rbtree_node_t *node_z) { rbtree_node_t *node_y = m_rbtree. sentinel; //Step 1.將y設(shè)置為哨兵,將x設(shè)置為根 rbtree_node_t *node_x = m_rbtree.root; if(m_rbtree.root== m_rbtree. sentinel) //若為空樹(shù)，z為根， { node_z-> parent = NULL; node_z-> left = m_rbtree. sentinel; node_z-> right = m_rbtree. sentinel; rbt_black(node_z); m_rbtree.root = node_z; return; } for(;node_x != m_rbtree.sentinel;) //Step 2.搜索，如果z比x小，向左子樹(shù)搜索，否則向右子樹(shù)搜索，y插入位置 { node_y = node_x; node_x = node_z->key - node_x->key < 0 ? node_x->left:node_x->right; } node_z->parent = node_y; if(node_z->key - node_y->key < 0) //Step 3 若z比y小，z放在y的左子樹(shù) { node_y->left = node_z; } else //否則，z放在y的右子樹(shù) { node_y->right = node_z; } node_z-> left = m_rbtree. sentinel; //Step 4.將z左右子樹(shù)設(shè)置為哨兵，顏色設(shè)置為紅色 node_z-> right = m_rbtree. sentinel; rbt_red(node_z); //re-balance tree rbtree_insert_fixup(node); //Step 5.紅黑樹(shù)調(diào)整 } 紅黑樹(shù)插入調(diào)整偽代碼：
RB-INSERT-FIXUP(T,z) while color[p[z]]=RED do if p[z]=left[p[p[z]]] then y <- right[p[p[z]]] if color[y]=RED then color[y] <- BLACK //情況1，z的叔叔y是紅色 color[p[z]] <- BLACK color[p[p[z]]] <- RED z <- p[p[z]] else if z=right[p[z]] //情況2，z的叔叔y是黑色，且z是右孩子 then z <- p[z] LEFT-ROTATE(T,z) color[p[z]] <- BLACK // 情況3，z的叔叔y是黑色，且z是左孩子 color[p[p[z]]] <- RED RIGHT-ROTATE(T,p[p[z]]) else (same as then clause with “right” and “l(fā)eft” exchanged) color[root[T]] <- BLACK 情況1：z的叔叔y是紅色
違反性質(zhì)4，z和z的父親都是紅色。 調(diào)整方法： 首先將z->p涂黑，再將z->p->p涂紅，最后將y涂黑。將z->p的顏色和z->p->p的顏色對(duì)換一下，再將y涂黑，其實(shí)是把z->p->p的黑色分發(fā)到兩個(gè)紅色兒子結(jié)點(diǎn)中，而其自身變?yōu)榧t色，維持了性質(zhì)5，即維護(hù)了所有路徑黑結(jié)點(diǎn)數(shù)量的一致性。這里要提出的一個(gè)小細(xì)節(jié)是，紅色結(jié)點(diǎn)變黑色不用考慮結(jié)點(diǎn)顏色沖突，而黑色結(jié)點(diǎn)變紅色則要考慮結(jié)點(diǎn)顏色沖突，紅變黑，隨意變，黑變紅，看沖突（不考慮性質(zhì)5的前提下）。因?yàn)閦->p->p是由黑色變紅的，這時(shí)將z指向z->p->p，如果不出現(xiàn)結(jié)點(diǎn)顏色沖突的情況則完成修復(fù)，有顏色沖突則進(jìn)入下一輪循環(huán)。
情況2：z的叔叔y是黑色，且z是右孩子
違反性質(zhì)4，z和z的父親都是紅色。 調(diào)整方法： 首先也是將z->p涂黑，z->p->p涂紅，這時(shí)候，我們就會(huì)發(fā)現(xiàn)根結(jié)點(diǎn)到y(tǒng)結(jié)點(diǎn)路徑中的黑結(jié)點(diǎn)數(shù)目減少了1，我們?cè)倩仡櫼幌虑懊鎸?duì)左旋、右旋方法的介紹，那么我們會(huì)發(fā)現(xiàn)，左旋、右旋的意義就在于此了：RIGHT-ROTATE(T,z->p->p)后，為根結(jié)點(diǎn)到y(tǒng)結(jié)點(diǎn)的路徑上增加了一個(gè)黑色結(jié)點(diǎn)z->p，為根結(jié)點(diǎn)到z結(jié)點(diǎn)的路徑上減少了一個(gè)紅色結(jié)點(diǎn)z->p->p，一條路徑增加黑色結(jié)點(diǎn)，另一條路徑減少紅色結(jié)點(diǎn)，insert就這樣被修復(fù)了。
情況3：z的叔叔y是黑色，且z是左孩子
違反性質(zhì)4，z和z的父親都是紅色。 調(diào)整方法： 將z->p涂黑，z->p->p涂紅，這時(shí)候，想對(duì)紅黑樹(shù)進(jìn)行修復(fù)的話，你會(huì)想到什么呢？和case 3一樣直接RIGHT-ROTATE(T,z->p->p)么，如果直接RIGHT-ROTATE(T,z->p->p)的話，紅色結(jié)點(diǎn)z將變成紅色結(jié)點(diǎn)z->p->p的左兒子，其實(shí)是做了無(wú)用功。那我們就想辦法把它變成case 3的那種形式吧，LEFT-ROTATE(T,z)，很容易想到吧，LEFT-ROTATE(T,z)之后z，z->p，z->p->p又變成了我們喜聞樂(lè)見(jiàn)的三點(diǎn)一線的形式，也就是case 3。
實(shí)現(xiàn)代碼： void RBTree::rbtree_insert_fixup( rbtree_node_t *node_z) { rbtree_node_t **root = & m_rbtree. root; rbtree_node_t *node_y; while( node_z != *root && rbt_is_red(node_z-> parent)) { if(node_z-> parent == node_z->parent->parent->left) { node_y = node_z->parent->parent->right; //case1:z的叔叔y是紅色 if(rbt_is_red(node_y)) { rbt_black( node_z->parent); rbt_black(node_y); rbt_red( node_z->parent->parent); node_z = node_z ->parent ->parent ; } else { //case2:z的叔叔y是黑色，且z是右孩子 if(node_z == node_z->parent->right) { node_z = node_z ->parent ; rbtree_left_rotate( node_z); } rbt_black( node_z->parent); rbt_red( node_z->parent->parent); rbtree_right_rotate( node_z); } } else { node_y = node_z->parent->parent->left; //case1:z的叔叔y是紅色 if(rbt_is_red(node_y)) { rbt_black( node_z->parent); rbt_black(node_y); rbt_red( node_z->parent->parent); node_z = node_z ->parent ->parent ; } else { //case2:z的叔叔y是黑色，且z是左孩子 if(node_z == node_z->parent->left) { node_z =node_z ->parent ; rbtree_right_rotate( node_z); } rbt_black( node_z->parent); rbt_red( node_z->parent->parent); rbtree_left_rotate( node_z->parent->parent); } } } rbt_black(*root); }
四、紅黑樹(shù)的刪除 刪除的節(jié)點(diǎn)按照兒子的個(gè)數(shù)可以分為三種：
OK，回到紅黑樹(shù)上來(lái)。算法導(dǎo)論一書，給的紅黑樹(shù)結(jié)點(diǎn)刪除的算法實(shí)現(xiàn)是： RB-DELETE(T, z) if left[z] = nil[T] or right[z] = nil[T] //沒(méi)有或者有一個(gè)兒子 then y ← z else y ← TREE-SUCCESSOR(z) //有兩個(gè)兒子，取左子樹(shù)的最大節(jié)點(diǎn)或右子樹(shù)的最小節(jié)點(diǎn) if left[y] ≠ nil[T] then x ← left[y] else x ← right[y] p[x] ← p[y] if p[y] = nil[T] //要?jiǎng)h除的為根角點(diǎn)，則直接用x替代根節(jié)點(diǎn) then root[T] ← x else if y = left[p[y]] //要?jiǎng)h除的節(jié)點(diǎn)在左子樹(shù)，則x放在在左子樹(shù) then left[p[y]] ← x else right[p[y]] ← x //要?jiǎng)h除的節(jié)點(diǎn)在右子樹(shù)，則x放在在右子樹(shù) if y ≠ z //z有兩個(gè)兒子 then key[z] ← key[y] //將y的數(shù)據(jù)給z，實(shí)際上是刪除的右子樹(shù)的最小節(jié)點(diǎn)，然后把這個(gè)節(jié)點(diǎn)的數(shù)據(jù)拷到了z的位置 copy y's satellite data into z if color[y] = BLACK //設(shè)置y的顏色為黑色 then RB-DELETE-FIXUP(T, x) return y
實(shí)現(xiàn)代碼：
void RBTree::rbtree_delete( rbtree_node_t *node_z) { rbtree_node_t **root =& m_rbtree. root; rbtree_node_t *sentinel = m_rbtree. sentinel; rbtree_node_t *node_y; //the node to replace node_z rbtree_node_t *node_x; //node_y's child bool is_node_y_red = false; if(node_z-> left == sentinel) { node_x = node_z-> right; node_y = node_z; } else if(node_z->right == sentinel) { node_x = node_z-> left; node_y = node_z; } else { node_y = rbtree_min(node_z-> right); if(node_y->left != sentinel) { node_x = node_y-> left; } else { node_x = node_y-> right; } } //the node to delete is root if(node_y == *root) { *root = node_x; rbt_black(node_x); node_z->left = NULL; node_z->right = NULL; node_z->parent = NULL; node_z->key = 0; return; } is_node_y_red = rbt_is_red(node_y); //Link node_y's child node_x to node_y's parent if(node_y == node_y-> parent-> left) { node_y-> parent-> left = node_x; } else { node_y-> parent-> right = node_x; } if(node_y == node_z) { node_x-> parent = node_y-> parent; } else { if(node_y->parent == node_z) { node_x-> parent = node_y; } else { node_x-> parent = node_y-> parent; } //replace node_z with node_y,include color,so the place of node_z is not change node_y-> left = node_z-> left; node_y-> right = node_z-> right; node_y-> parent = node_z-> parent; rbt_copy_color(node_y,node_z); //the node to delete is root if( node_z == *root) { *root = node_y; } else { if(node_z == node_z->parent ->left ) { node_z-> parent-> left = node_y; } else { node_z-> parent-> right = node_y; } } if(node_z->left != sentinel) { node_y-> left-> parent = node_y; } if(node_z->right != sentinel) { node_y-> right-> parent = node_y; } } node_z->left = NULL; node_z->right = NULL; node_z->parent = NULL; node_z->key = 0; //if node_y is a black node,the action move node_y to replace node_z change the struct of rbtree if(!is_node_y_red) { rbtree_delete_fixup(node_x); } } 紅黑樹(shù)刪除調(diào)整偽代碼： while x ≠ root[T] and color[x] = BLACK do if x = left[p[x]] then w ← right[p[x]] if color[w] = RED then color[w] ← BLACK // Case 1 color[p[x]] ← RED // Case 1 LEFT-ROTATE(T, p[x]) // Case 1 w ← right[p[x]] // Case 1 if color[left[w]] = BLACK and color[right[w]] = BLACK then color[w] ← RED //Case 2 x ← p[x] //Case 2 else if color[right[w]] = BLACK then color[left[w]] ← BLACK //Case 3 color[w] ← RED //Case 3 RIGHT-ROTATE(T, w) //Case 3 w ← right[p[x]] //Case 3 color[w] ← color[p[x]] //Case 4 color[p[x]] ← BLACK //Case 4 color[right[w]] ← BLACK //Case 4 LEFT-ROTATE(T, p[x]) //Case 4 x ← root[T] //Case 4 else (same as then clause with "right" and "left" exchanged) color[x] ← BLACK 情況1：x的兄弟w是紅色的
這時(shí)，將w涂黑，將x->p涂紅，然后進(jìn)行左旋，得到的以w為結(jié)點(diǎn)的紅黑樹(shù)如下：
進(jìn)行變形之后不會(huì)改變每條路徑的黑色結(jié)點(diǎn)數(shù)目，這時(shí)將w重新做指向，令w=x->p->right，這樣w變成了黑色結(jié)點(diǎn)，在下一輪循環(huán)時(shí)可能進(jìn)入case 2、3、4。 情況2：x的兄弟w是黑色的，而w的兩個(gè)兒子都是黑色
這時(shí)，將w涂紅，root結(jié)點(diǎn)到x->p為根子樹(shù)的每個(gè)葉子結(jié)點(diǎn)的路徑將比其他路徑少的黑結(jié)點(diǎn)數(shù)目少1，將x->p設(shè)為x，若x為紅結(jié)點(diǎn)，將其涂黑即可成功修復(fù)二叉樹(shù)；若x為黑結(jié)點(diǎn)，即進(jìn)入下一輪循環(huán)，可能出現(xiàn)case 1、2、3、4。如果連續(xù)出現(xiàn)的是case 2其結(jié)果就相當(dāng)于最后在除root到最初的x結(jié)點(diǎn)的每條路徑上減少一個(gè)黑色結(jié)點(diǎn)，直到x為root結(jié)點(diǎn)，結(jié)束循環(huán)。 情況3：x的兄弟w是黑色的，而w的左孩子為紅色，右孩子為黑色
這時(shí)候我們應(yīng)該想如何將case 3變?yōu)閏ase 4中的那種形式，還要維持紅黑樹(shù)的性質(zhì)，我們看到w->left是紅色，那么我們就將其涂黑，然后將w涂紅，再對(duì)w進(jìn)行右旋，得到：
變?yōu)閏ase 4的那種形式，即可進(jìn)入case 4對(duì)紅黑樹(shù)進(jìn)行修復(fù)操作。 情況4：x的兄弟w是黑色的，而w的左孩子為黑色，右孩子為紅色
路徑root到x的黑結(jié)點(diǎn)數(shù)少1，這時(shí)候我們調(diào)換x->p和w的顏色，并將w->right涂黑，再進(jìn)行一次左旋得到下面的紅黑樹(shù)：
可以發(fā)現(xiàn)，得到的紅黑樹(shù)對(duì)RB-DELETE操作成功進(jìn)行了修復(fù)，所以說(shuō)以x->p為根結(jié)點(diǎn)的子樹(shù)不滿足這一形式時(shí)，應(yīng)該通過(guò)一定的變形和一定數(shù)目結(jié)點(diǎn)顏色的改變，來(lái)滿足這一形式。 case之間的狀態(tài)轉(zhuǎn)移如下：
void RBTree::rbtree_delete_fixup( rbtree_node_t *node_x) while( node_x != *root && rbt_is_black(node_x)) //case1:node_x's brother node_w is red //case2:node_x's brother node_w is black,both child of node_w is black //case4:node_x's brother node_w is black,node_w's right child is red //break while running //case1:node_x's brother node_w is red //case2:node_x's brother node_w is black,both child of node_w is black //case4:node_x's brother node_w is black,node_w's left child is red //break while running } rbt_black(node_x);
代碼下載地址：http://download.csdn.net/detail/chen19870707/7979779Reference
1.《算法導(dǎo)論》 第十三章 紅黑樹(shù) P163 2.http://blog.sina.com.cn/s/blog_453d87aa0100yr3b.html - Echo Chen：Blog.csdn.net/chen19870707 - |
|
|
