频道栏目
首页 > 程序开发 > 软件开发 > C语言 > 正文
红黑树-C语言实现
2013-12-09 15:35:41         来源:binwin20  
收藏   我要投稿

红黑树的性质

红黑树性质

红黑树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博客地址:https://blog.csdn.net/binwin20/article/details/17221017


点击复制链接 与好友分享!回本站首页
相关TAG标签 语言
上一篇:C语言指针总结
下一篇:c 16进制 字符串 加一 c 16进制 字符串 加1 源代码
相关文章
图文推荐
文章
推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站