（學(xué)習(xí)的參考資料主要是《算法導(dǎo)論》）
首先是紅黑樹的性質(zhì)。一棵二叉查找樹滿足以下的紅黑性質(zhì)，則為一棵紅黑樹。
1)每個(gè)結(jié)點(diǎn)或是紅的，或是黑的。
2)根結(jié)點(diǎn)是黑的。
3)每個(gè)葉結(jié)點(diǎn)(NIL)是黑的。
4)紅結(jié)點(diǎn)的兩個(gè)孩子都是黑的。
5)對任意結(jié)點(diǎn)，從它到其子孫結(jié)點(diǎn)所有路徑上包含相同數(shù)目的黑結(jié)點(diǎn)。
初學(xué)時(shí)并不在意，但是仔細(xì)研究相關(guān)算法就會知道，算法都是圍繞保持這些性質(zhì)來進(jìn)行的。性質(zhì)5）保證了紅黑樹使用時(shí)的高效。定理證明了n個(gè)內(nèi)結(jié)點(diǎn)的紅黑樹高度至多為2lg(n+1)。
不同于一般二叉查找樹，紅黑樹一般采用一個(gè)哨兵結(jié)點(diǎn)代表NIL，這對算法的使用提供了很多方便，具體編寫時(shí)可以體會的到。哨兵設(shè)置為黑色，它是根的父結(jié)點(diǎn)，也是所有的葉子結(jié)點(diǎn)。而它的其他域可以設(shè)置為任意值。我用關(guān)鍵字把它和普通的結(jié)點(diǎn)進(jìn)行區(qū)分。
旋轉(zhuǎn)是紅黑樹的特有操作。以前搞不清左旋和右旋究竟是如何進(jìn)行的，現(xiàn)在比較明白，可以這樣概括：以x結(jié)點(diǎn)左旋即為，使x從一棵子樹的根變成這個(gè)子樹的左孩子；對稱的，同理。旋轉(zhuǎn)是紅黑樹插入和刪除時(shí)為了維持紅黑性質(zhì)而可能進(jìn)行的操作。
插入的原理：
除了空指針的處理，插入的過程和二叉查找樹相同，但是插入后需要進(jìn)行獨(dú)有的調(diào)整算法以保證紅黑性質(zhì)。下面的描述是我的個(gè)人概括，看上去比較混亂，和算法以及實(shí)例相對照著可能容易理解一些。
新插入的點(diǎn)z直接染成紅色，再根據(jù)其父結(jié)點(diǎn)是否為紅(與性質(zhì)4沖突)和插入的結(jié)點(diǎn)是否為根（與性質(zhì)2沖突）進(jìn)行調(diào)整。后者直接把根染黑即可。
對于前者，找到z的叔叔y（找叔叔y雖然需要分情況處理，但比較簡單，不詳寫），根據(jù)y是紅還是黑進(jìn)一步分清況。z的父親為左孩子時(shí)，前者只需要把z的父親和叔叔同時(shí)變黑、z的父結(jié)點(diǎn)的父結(jié)點(diǎn)變紅、令z指向z的父結(jié)點(diǎn)的父結(jié)點(diǎn)迭代處理即可；后者進(jìn)一步分z是左孩子還是右孩子處理。z是左孩子時(shí)直接以z的父結(jié)點(diǎn)進(jìn)行旋轉(zhuǎn)讓z的父親左旋并成為新z即成為后一種情況。在后一種情況中，將z的父親染黑，祖父染紅，以z的祖父右旋就能獲得。
刪除的原理:
算法導(dǎo)論上的刪除算法把兩種情況同時(shí)進(jìn)行處理，確實(shí)很有技巧。紅黑樹的刪除除了最后需要根據(jù)對于刪除結(jié)點(diǎn)的顏色來判斷是否需要進(jìn)行調(diào)整外，和普通的二叉查找樹沒有區(qū)別，這里稍微做一下分析。
用w表示x的兄弟。
情況1為w紅。此時(shí)調(diào)整w為黑，p[x]為紅，以p[x]左旋，w指向x的新兄弟，此時(shí)則成為情況2或3或4。
情況2為w黑，且w的兩個(gè)孩子均黑。此時(shí)把w染紅，令p[x]成為新的x。這相當(dāng)于把x剝離了一層黑色，使這層黑色上移。
情況3為w黑，w的左孩子為紅，右孩子為黑。這時(shí)交換w和左孩子顏色，并對w右旋，此時(shí)成為情況4。
情況4為w黑，w有孩子為紅。這時(shí)使w成為p[x]的顏色，p[x]置為黑色，w的右孩子置為黑，對p[x]左旋。令x為根。這時(shí)相當(dāng)于把原先x上的一重黑色傳給了其父親并于它一起下移，而w代替了其父親原先的顏色和位置。這是不存在紅黑結(jié)點(diǎn)或二重黑結(jié)點(diǎn)。
每次處理都判斷x是否為根且x是否為黑。x不為根且為黑時(shí)才代表有紅黑結(jié)點(diǎn)或二重黑結(jié)點(diǎn)，需要進(jìn)行新一輪循環(huán)。循環(huán)結(jié)束后把根染黑就結(jié)束了。
最后附上一個(gè)我自己用C寫的紅黑樹操作。插入操作驗(yàn)證無誤，刪除操作驗(yàn)證次數(shù)有限，可能有bug存在。
#define T_nil -1
//T_nil is a key of nil[T] in the book.
#define RED 1
#define BLACK 0//T_nil is BLACK
//T_nil's p is itself. need to set.
struct rb_tree {
int color;
int key; //normally a positive number.
struct rb_tree *left;
struct rb_tree *right;
struct rb_tree *p;
};
int rb_walk(struct rb_tree *node) {
if (node->key != T_nil) {
rb_walk(node->left);
printf("%d, color is %s/n",node->key,(node->color?"RED":"BLACK"));
rb_walk(node->right);
}
return 1;
}
struct rb_tree* rb_search(struct rb_tree *node, int k) {
if ((node->key == T_nil) || (node->key == k))
return node;
if ( k < node->key )
return rb_search(node->left,k);
else
return rb_search(node->right,k);
}
struct rb_tree* tree_minimum(struct rb_tree *node) {
if (node->key == T_nil)
return node;
while (node->left->key != T_nil)
node = node->left;
return node;
}
struct rb_tree* tree_maximum(struct rb_tree *node) {
if (node->key == T_nil)
return node;
while (node->right->key != T_nil)
node = node->right;
return node;
}
struct rb_tree* tree_successor(struct rb_tree *node) {
struct rb_tree *y;
if (node->right->key != T_nil)
return tree_minimum(node->right);
y = node->p;
while ((y->key != T_nil) && (node == y->right)) {
node = y;
y = y->p;
}
return y;
}
//3 function of below is copy from tree.
struct rb_tree * left_rotate(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *y;
//if (x->right->key == T_nil) {
// printf("have no right child,rotation cancel./n");
// return rb;
//}
y = x->right;
x->right = y->left;
if (y->left->key != T_nil)
y->left->p = x;
y->p = x->p;
if (x->p->key == T_nil)
rb = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->left = x;
x->p = y;
return rb;
}
struct rb_tree *right_rotate(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *y;
//if (x->left->key == T_nil ) {
// printf("have no left child,rotation cancel./n");
// return rb;
//}
y = x->left;
x->left = y->right;
if (y->right->key != T_nil )
y->right->p = x;
y->p = x->p;
if (x->p->key == T_nil)
rb = y;
else if (x == x->p->left)
x->p->left = y;
else
x->p->right = y;
y->right = x;
x->p = y;
return rb;
}
struct rb_tree* rb_insert_fixup(struct rb_tree *rb, struct rb_tree *z) {
struct rb_tree *y;
while (z->p->color == RED) {
if (z->p == z->p->p->left) {
y = z->p->p->right;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->right) {
z= z->p;
rb = left_rotate(rb,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rb = right_rotate(rb,z->p->p);
}
}
else {//same as right and left exchanged
y = z->p->p->left;
if (y->color == RED) {
z->p->color = BLACK;
y->color = BLACK;
z->p->p->color = RED;
z = z->p->p;
}
else {
if (z == z->p->left) {
z= z->p;
rb = right_rotate(rb,z);
}
z->p->color = BLACK;
z->p->p->color = RED;
rb = left_rotate(rb,z->p->p);
}
}
}
rb->color = BLACK;
return rb;
}
struct rb_tree* rb_insert(struct rb_tree *rb, int k) {
struct rb_tree *y = rb->p;
struct rb_tree *x = rb;
struct rb_tree *z;
z= (struct rb_tree *)malloc(sizeof(struct rb_tree));
z->key = k;
while (x->key != T_nil) {
y = x;
if (k< x->key)
x = x->left;
else
x = x->right;
}
z->p = y;
if (y->key == T_nil)
rb = z;
else if (z->key <y->key)
y->left = z;
else
y->right =z;
z->left = rb->p;
z->right = rb->p;
z->color = RED;
return rb_insert_fixup(rb,z);
}
struct rb_tree* rb_delete_fixup(struct rb_tree *rb, struct rb_tree *x) {
struct rb_tree *w;
while ((x !=rb)&&(x->color == BLACK)) {
if (x == x->p->left) {
w = x->p->right;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
left_rotate(rb,x->p);
w = x->p->right;
}
if ((w->left->color == BLACK)&&(w->right->color == BLACK)) {
w->color = RED;
x = x->p;
}
else if (w->right->color == BLACK) {
w->left->color = BLACK;
w->color = RED;
right_rotate(rb,w);
w = x->p->right;
}
w->color = x->p->color;
x->p->color = BLACK;
w->right->color = BLACK;
left_rotate(rb,x->p);
x = rb;
}
else { //same as right and left exchanged
w = x->p->left;
if (w->color == RED) {
w->color = BLACK;
x->p->color = RED;
right_rotate(rb,x->p);
w = x->p->right;
}
if ((w->right->color == BLACK)&&(w->left->color == BLACK)) {
w->color = RED;
x = x->p;
}
else if (w->left->color == BLACK) {
w->right->color = BLACK;
w->color = RED;
left_rotate(rb,w);
w = x->p->left;
}
w->color = x->p->color;
x->p->color = BLACK;
w->left->color = BLACK;
right_rotate(rb,x->p);
x = rb;
}
}
x->color = BLACK;
}
struct rb_tree* rb_delete(struct rb_tree *rb, struct rb_tree *z) {
struct rb_tree *x,*y;
if ((z->left->key == T_nil) || (z->right->key == T_nil))
y = z;
else y = tree_successor(z);
if (y->left->key != T_nil)
x = y->left;
else
x = y->right;
x->p = y->p;
if (y->p->key == T_nil)
rb = x;
else if (y==x->p->left)
y->p->left = x;
else
y->p->right = x;
if (y!=x) //copy y's data to z
z->key = y->key;
if (y->color == BLACK)
rb_delete_fixup(rb,x);
free(y);
return rb;
}
int main () {
struct rb_tree *p,*root;
struct rb_tree tree_nil = {BLACK,T_nil,&tree_nil,&tree_nil,&tree_nil};
root = &tree_nil;
root = rb_insert(root,15);
root = rb_insert(root,5);
root = rb_insert(root,16);
root = rb_insert(root,3);
root = rb_insert(root,12);
root = rb_insert(root,20);
root = rb_insert(root,10);
root = rb_insert(root,13);
root = rb_insert(root,6);
root = rb_insert(root,7);
root = rb_insert(root,18);
root = rb_insert(root,23);
rb_walk(root);
p = rb_search(root,18);
root = rb_delete(root,p);
rb_walk(root);
return 1;
}
新聞熱點(diǎn)
疑難解答
圖片精選
