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;
}</pre>