紅黑樹

紅黑樹的性質

紅黑樹性質

紅黑樹c語言代碼及注釋

#include 
#include 
#include 
#include 
using namespace std;
#define bug cout<<"bug"<color = BLACK;
    }
    Node *successor(Node *t);
    void rotate(Node *t,int c);///c=0 左旋 1 右旋
    void insert(int key);
    void insert_fixup(Node *t);
    void remove(int key);
    void remove_fixup(Node *t);
    void out(){
        dfs(head,0);cout<key<<" "<<(t->color==BLACK?'B':'R')<<" ";
        //cout<<"L";if(t->ch[0]!=nil&&t->ch[0]->p!=t) cout<<"bug"<ch[0],d+(t->color==BLACK));
        //cout<<"U";cout<<"R";if(t->ch[1]!=nil&&t->ch[1]->p!=t) cout<<"bug"<ch[1],d+(t->color==BLACK));
        //cout<<"U";
    }
};
void Tree::rotate(Node *t,int c){
    Node *&pt = (t->p==nil) ? head : t->p->ch[t->p->ch[1]==t];// t的父親指向t的指針
    Node *y = t->ch[c^1];
    t->ch[c^1] = y->ch[c];
    y->ch[c]->p = t;
    y->ch[c] = t;
    y->p = t->p;
    t->p = y;
    pt = y;
}
Node *Tree::successor(Node *t){//返回t的後繼結點
    Node *p;
    if(t->ch[1]!=nil){
        p = t->ch[1];
        while(p->ch[0]!=nil) p = p->ch[0];
        return p;
    }else{
        p = t->p;
        while(p!=nil&&p->p->ch[1]==p) p = p->p;
        return p;
    }
}
void Tree::insert(int key){
    Node *t = new Node();
    t->key = key;
    t->ch[0] = t->ch[1] = nil;
    t->color = RED;
    Node *x=head,*y=nil;
    while(x!=nil)  //尋找葉子作為插入的地方
    {
        y = x;
        x = x->ch[key > x->key];
    }
    t->p = y;
    if(y==nil) head = t;
    else y->ch[key > y->key] = t;
    insert_fixup(t);
}
void Tree::insert_fixup(Node *t){
    while(t->p->color==RED){
        Node *p = t->p;//父親R
        Node *g = p->p;//祖父B
        int pa = g->ch[1]==p;//父親是左右孩子
        int ta = p->ch[1]==t;//自己是左右孩子
        Node *u = g->ch[pa^1];//叔叔
        if(u->color==RED){//case1：叔叔也是紅色，改變p,u,t的顏色
            g->color = RED;
            p->color = u->color = BLACK;
            t = g;
        }else{
            if(ta!=pa)//case2：不在一條直線上
            {
                rotate(p,ta^1);//轉成在同一條直線上
                swap(t,p);
                ta = pa;
            }
            g->color = RED;//case3：改變p，g的顏色
            p->color = BLACK;
            rotate(g,pa^1);//把祖父旋轉
        }
    }
    head->color = BLACK;
}
void Tree::remove(int key)
{
    Node *t= head,*y;
    while(t!=nil&&t->key!=key) t = t->ch[key>t->key]; //查找被刪除的結點
    if(t==nil) return ;
    if(t->ch[0]==nil||t->ch[1]==nil) y = t;//y是真正要刪除的結點
    else y = successor(t);
    Node *x = y->ch[y->ch[0]==nil];
    x->p = y->p;
    if(y->p==nil)//y是根
        head = x;
    else
        y->p->ch[y->p->ch[1]==y] = x; //把y從樹中移除
    if(y!=t)
        t->key = y->key;
    if(y->color==BLACK)//y是黑色則要進行紅黑樹的維護
        remove_fixup(x);
    delete(y);
}
void Tree::remove_fixup(Node *t)
{
    while(t!=head && t->color==BLACK){
        Node *p = t->p;
        int ta = p->ch[1]==t;
        Node *w = p->ch[ta^1];//兄弟
        if(w->color==RED)//case1：兄弟是紅色，兄弟染成黑色，父親染成紅色，
        {
            w->color = BLACK;
            p->color = RED;
            rotate(p,ta);
            w = p->ch[ta^1];
        }
        if(w->ch[0]->color==BLACK&&w->ch[1]->color==BLACK){ //case2：兩個侄子是黑色：把兄弟染紅，把缺一個黑色結點的狀態推給父親
            w->color = RED;
            t = p;
        }else{
            if(w->ch[ta^1]->color == BLACK){ //case3：有一個比較遠的侄子是黑色更近的侄子是紅色：把更近是侄子染黑，兄弟染紅，兄弟旋轉；
                w->ch[ta]->color = BLACK;    //轉完之後的狀態是，兄弟黑，更遠的侄子紅。
                w->color = RED;
                rotate(w,ta^1);
                w = p->ch[ta^1];
            }
            //case4：兄弟是黑色，較遠的侄子是紅色：兄弟染成父親的顏色，父親染黑，較遠的侄子染黑，旋轉父親結點。
            w->color = p->color;
            p->color = BLACK;
            w->ch[ta^1]->color = BLACK;
            rotate(p,ta);
            t = head;
        }
    }
    t->color = BLACK;
}
int re[10200];
int main()
{
    Tree tre;
    int n = 100;
    for(int i=0;i博客地址：http://blog.csdn.net/binwin20/article/details/17221017