红黑树代码 c++

#include <iostream>

using namespace std;

class Tree_Node
{
public:
        enum
        {
                COLOR_RED = 0,
                COLOR_BLACK = 1
        };

        Tree_Node(int num = 0)
        {
                parent = NULL;
                lchild = NULL;
                rchild = NULL;
                value = num;
                color = COLOR_RED;
        }

        Tree_Node *parent;
        Tree_Node *lchild;
        Tree_Node *rchild;
        int color;
        int value;
};

class RB_Tree
{
public:
        RB_Tree()
        {
                empty_node_->color = Tree_Node::COLOR_BLACK;
        }

        void add_node(Tree_Node *&node)
        {

                //node is root

                if (NULL == empty_node_->parent)
                {
                        empty_node_->parent = node;
                        node->color = Tree_Node::COLOR_BLACK;
                        node->lchild = empty_node_;
                        node->rchild = empty_node_;
                        return;
                }

                //add node

                Tree_Node *p = empty_node_->parent;
                Tree_Node *save;
                while (p != empty_node_)
                {
                        if (node->value < p->value)
                        {
                                p = p->lchild;
                        }
                        else
                        {
                                p = p->rchild;
                        }
                        save = p;
                }

                //append node as save's left child

                if (node->value < save->value)
                {
                        save->lchild = node;
                        node->parent = save;
                        node->lchild = empty_node_;
                        node->rchild = empty_node_;
                }
                //append node as save's right child

                else
                {
                        save->rchild = node;
                        node->parent = save;
                        node->lchild = empty_node_;
                        node->rchild = empty_node_;
                }


                //fixup rb tree

                Tree_Node *fix_point = node;
                while (true)
                {
                        //when parent is black, success

                        if (Tree_Node::COLOR_BLACK == fix_point->parent->color)
                        {
                                break;
                        }

                        //case 1 : parent and uncle are all red

                        Tree_Node *grandfather = fix_point->parent->parent;
                        if (Tree_Node::COLOR_RED == grandfather->lchild->color && Tree_Node::COLOR_RED == grandfather->rchild->color)
                        {
                                grandfather->lchild->color = Tree_Node::COLOR_BLACK;
                                grandfather->rchild->color = Tree_Node::COLOR_BLACK;
                                grandfather->color = Tree_Node::COLOR_RED;
                                fix_point = grandfather;
                                continue;
                        }

                        //case 2 : parent is red, uncle is black, and fix_point is his parent's right child

                        if (fix_point->value >= fix_point->parent->value)
                        {
                                //left rotate fix_point's father

                                Tree_Node *p = fix_point->parent;
                                if (p == p->parent->lchild)
                                {
                                        p->parent->lchild = p->rchild;
                                        p->rchild = p->rchild->lchild;
                                        p->parent->lchild->lchild = p;

                                        p->parent->lchild->parent = p->parent;
                                        p->rchild->parent = p;
                                        p->parent = p->parent->lchild;
                                }
                                else
                                {
                                        p->parent->rchild = p->rchild;
                                        p->rchild = p->rchild->lchild;
                                        p->parent->lchild->lchild = p;

                                        p->parent->rchild->parent = p->parent;
                                        p->rchild->parent = p;
                                        p->parent = p->parent->rchild;
                                }

                        }


                        //case 3 : parent is red, uncle is black, and fix_point is his parent's left child

                        {
                                fix_point->parent->color = Tree_Node::COLOR_BLACK;
                                fix_point->parent->parent->color = Tree_Node::COLOR_RED;

                                //right rotate fix_point's grandfather

                                Tree_Node *p = fix_point->parent->parent;
                                if (p == p->parent->lchild)
                                {
                                }
                                else
                                {
                                }
                        }


                }




        }
private:
        Tree_Node *empty_node_;
};

int main()
{

        RB_Tree tree;


}


 

红黑树代码，待更新。。。