C++红黑树的完整实现

#include <iostream>

using namespace std;

typedef enum Color
{
    RED,
    BLACK,
}Color;
template<typename Type>
struct RbNode
{
    Color color;
    Type data;
    RbNode<Type> *parent;
    RbNode<Type> *left;
    RbNode<Type> *right;
    RbNode(Type d=Type()):left(NULL),right(NULL),parent(NULL),data(d),color(RED){}
};

template<typename Type>
class RbTree
{
    public:
    RbTree()
    {
        Root = NULL;
        Nul  = NULL;
        Start = BuyNode();      
        Start->color = BLACK;   
    }
    void Insert(Type ar[],int n)
    {
        for(int i=0;i<n;i++)
        {
            _Insert(Root,ar[i]);
        }
    }
    private:
    bool _Insert(RbNode<Type> *p,int val)
    {
        RbNode<Type> *pr = NULL;
        while(p!=NULL)
        {
            if(p->data == val)return false;
            pr = p;
            if(p->data > val)p=p->left;
            else p=p->right;
        }
        if(pr==NULL)
            {
                Root = BuyNode(val);
                p = Root;
            }
        else
            p = BuyNode(val);
        if(pr!=NULL)
                {
                    if(pr->data>val)    
                                pr->left = p;
                    else
                            pr->right = p;
                    p->parent = pr;
                }
        Init_Set(Root,p);
        Root->color = BLACK;
    }
    RbNode<Type>* BuyNode(Type d=Type())
    {
        RbNode<Type> *s = new RbNode<Type>(d);
        return s;
    }
    bool Init_Set(RbNode<Type> *&t,RbNode<Type> *&p)
    {
        p->color = RED;
        if(p->parent!=Nul && p->parent->color == RED)
            {

                if(p->parent->parent->left==p->parent)
                {
                    if(p->parent->left==p)
                        {
                            RbNode<Type> *s = p->parent->parent->right;
                            if(s!=Nul && s->color==RED)
                            {
                                p->parent->color = BLACK;
                                s->color = BLACK;
                                p=s->parent;
                                Init_Set(Root,p);
                            }
                            else 
                            {
                            p->parent->color = BLACK;
                                    p->parent->parent->color=RED;
                                p = p->parent->parent;
                              StateR(Root,p);
                            }
                        }
                        else
                        {
                            RbNode<Type> *s = p->parent->parent->right;
                            if(s!=Nul && s->color==RED)
                            {
                                p->parent->color = BLACK;
                                s->color = BLACK;
                                p=s->parent;
                                Init_Set(Root,p);
                            }
                            else
                            {
                                p = p->parent;  
                                StateL(Root,p);
                                Init_Set(Root,p->left);
                            }                   
                        }
                }
                else
                {
                    if(p->parent->right==p)//  \ s
                    {
                        RbNode<Type> *s = p->parent->parent->left;
                        if(s!=Nul && s->color == RED)
                        {   
                            p->parent->color = BLACK;
                            s->color = BLACK;
                            p = s->parent;
                            Init_Set(Root,p);
                        }
                        else
                        {
                            p->parent->color = BLACK;
                                p->parent->parent->color=RED;       
                                p=p->parent->parent;    
                                StateL(Root,p);
                        }
                    }
                    else
                    {   
                            RbNode<Type> *s = p->parent->parent->left;
                            if(s!=Nul && s->color==RED)
                            {
                                p->parent->color = BLACK;
                                s->color = BLACK;
                                p=s->parent;
                                Init_Set(Root,p);
                            }
                            else
                            {
                                p = p->parent;  
                                StateR(Root,p);
                                Init_Set(Root,p->right);
                            }                   
                    }
                }
            }
    }
    void StateL(RbNode<Type> *&t,RbNode<Type> *&p)
    {
        int flogs = 0;

    RbNode<Type> *q = p->right;
        RbNode<Type> *save = p->parent;

   if(p==t){
            flogs++;
            }
        p->right = q->left;
        if(q->left)
            q->left->parent = p;

        q->left = p;
        p->parent = q;

        if(save)
                {
                    if(save->left==p)
                        save->left=q;
                    else
                        save->right=q;
                    q->parent=save;
                }
                p = q;
        if(flogs==1)
            {Root = p;Root->parent=Start;}
    }
    void StateR(RbNode<Type> *&t,RbNode<Type> *&p)
    {
        int flogs = 0;

        RbNode<Type> *q = p->left;
        if(t==p)
            flogs++;
        RbNode<Type> *save = p->parent;
        p->left = q->right;
        if(q->right!=NULL)
        q->right->parent = p;

        q->right = p;
        p->parent = q;

        if(save!=NULL)
            if(save->left==p)
                {
                    save->left = q;
                }
            else 
                {
                    save->right=q;
                }
        q->parent = save;
        p = q;
            if(flogs==1){Root = p;Root->parent=Start;}
    }
    public:
    void Printf()
    {
        Printf(Root);
    }
    void Remove(Type val)
    {
        Remove(Root,val);
    }
    private:
    void Remove(RbNode<Type> *t,Type val)
    {
        RbNode<Type> *p = t;
        RbNode<Type> *pr = NULL;
        while(p!=NULL)
        {
            if(p->data == val)break;
            if(p->data>val)p=p->left;
            else p=p->right;
        }
        if(p==NULL)return ;
        else
        {
    //          t = p;
            if(p->left!=NULL && p->right!=NULL)
                {
                    pr = p->right;
                    while(pr->left!=NULL)pr=pr->left;
                    t->data = pr->data;
                    p = pr;
                }
                pr = p->parent;
                if(t->left==p)
                        {
                            RbNode<Type> *s = p->right;
                            t->left = s;
                            if(s!=NULL)
                              {
                                s->parent = NULL;
                                s->parent = t;
                                }
                            if(p->color==BLACK)
                            {
                             if(s!=Nul && s->color==RED)
                                 {
                                    s->color=BLACK;
                                 }
                           else if(s!=Nul && s->color==BLACK)
                            {   
                                    Remove_Set(Root,s); 
                              }

                        }
                else
                        {
                            RbNode<Type> *s = p->right;
                            t->left = s;
                            if(s!=NULL)
                              {
                                s->parent = NULL;
                                s->parent = t;
                                }
                            if(p->color==BLACK)
                            {
                             if(s!=Nul && s->color==RED)
                                 {
                                    s->color = BLACK;
                                 }
                                else if(s!=Nul  && s->color==BLACK)
                                {
                                    Remove_Set(Root,s);
                                }
                            }
                        }
                }
        }
        Root->color = BLACK;
        delete p;p=NULL;
    }
    void Remove_Set(RbNode<Type> *&t,RbNode<Type> *p)
    {
        RbNode<Type> *s  = p->parent->right;
        while(p!=Start && p->color!=RED)
        {
            if(s!=NULL)
            {   
                if(s->color==RED)
                {
                    s->parent->color = RED;
                    s->color = BLACK;
                    s=s->parent;
                    StateL(Root,s);
                }
                else if(s->color==BLACK)
                {   
                    if(s->left!=NULL && s->right!=NULL)
                    {   
                        if(s->left->color==BLACK && s->left->right->color==BLACK)
                        {
                            s->color = RED;
                            s->parent->color = BLACK;
                            p = s->parent;
                        }
                        else if(s->right->color==BLACK && s->left->color==RED)
                        {
                            StateR(Root,s);
                        }
                        else if(s->right->color==RED && s->color==BLACK)
                        {   
                            s=s->parent;
                            StateL(Root,s);
                            p = s;
                        }
                    }
                }
            }
        }       
    }
    void Printf(RbNode<Type> *&t)
    {
        if(t==NULL)return ;
        else
        {
            Printf(t->left);
            cout<<t->data<<":"<<t->color<<"\t";
            Printf(t->right);
        }
    }
    RbNode<Type> *Start;
    RbNode<Type> *Root;
    RbNode<Type> *Nul;
};

int main()
{
    int a[]={0,2,3,1,5,10,15,7,8};
    RbTree<int> rb;
    rb.Insert(a,9);
    rb.Remove(5);
    rb.Printf();
    return 0;
}

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点！
本站所提供的图片等素材，版权归原作者所有，如需使用，请与原作者联系。