上一篇文章是纯粹地实现了红黑树，但是在STL中，红黑树容器是需要迭代器实现的。故将上一篇文章改进后实现红黑树容器。

本人实现的红黑树容器是底层红黑树结构是依据算法导论中设计的包含普通节点和空节点。不同于STL中的红黑树，其迭代器故也

有点不一样

//my_rb_tree.h

#ifndef MY_RB_TREE_H_INCLUDED
#define MY_RB_TREE_H_INCLUDED

#include"iterator_rb_tree.h"
#include"simple_allocator.h"

namespace juine
{
    //红黑树
    /*
    **红黑树容器中树节点存放的对象是Value，但是比较的对象，用来决定树的结构的则是Key，
    函数对象KeyOfvalue这是Value对象向Key对象的转化.
    这样红黑树容器与红黑树地区别就在于：
    在insert和delete需找对象进行比较的时候，我们得到了Value对象，要将其转化为Key,然后在进行比较
    例如以前是这样写的：
      if(temp->data<value)  //节点所指值小于值value
      要改成如下：
      if(key_compare(key(temp)),KeyOfValue()(value) )
      key_compare:为比较函数
      key：将所指节点值转化为key类型
      KeyOfValue；将Value值转化为Key类型

    */

    template<class Key,class Value,class KeyOfValue,class Compare,class Alloc=my_alloc>
    class RB_Tree
    {
    public:
        typedef Key key_type;
        typedef Value value_type;
    protected:

        RB_Node<Value>* root;   //红黑树的根节点
        RB_Node<Value>* nullNode;  //空节点，黑色的
        size_t node_num;
        Compare key_compare;   //定义一个比较函数对象


        typedef simple_allocator<RB_Node<Value>,Alloc> RB_Node_Container;

        //插入完成后要记得修复，使其满足红黑树的性质
        //插入时中的三种情况
        void InsertFixUp(RB_Node<Value> *node)
        {
            while(node->parent->RB_COLOR==RED)
            {
                //插入节点为父节点的左孩子
                if(node->parent->left==node)
                {
                    RB_Node<Value> *uncle=node->parent->parent->right;
                    if(uncle->RB_COLOR==RED)   //case 1
                    {
                        node->parent->RB_COLOR=BLACK;
                        uncle->RB_COLOR=BLACK;
                        node=node->parent->parent;
                        node->RB_COLOR=RED;
                    }
                    else
                    {
                        if(node->parent==node->parent->parent->right)    //case 2
                        {
                            node=node->parent;
                            right_rotate(node);
                           // goto double_left_rotate;
                        }
                        //case2结束以后直接进入case3，或者直接进入case3
                       // double_right_rotate:
                        else{
                            node->parent->RB_COLOR=BLACK;
                            node->parent->parent->RB_COLOR=RED;
                            right_rotate(node->parent->parent);
                        }
                    }

                }
                //当节点为为父节点的右孩子
                else
                {
                    RB_Node<Value> *uncle=node->parent->parent->left;
                    if(uncle->RB_COLOR==RED)   //case 1
                    {
                        node->parent->RB_COLOR=BLACK;
                        uncle->RB_COLOR=BLACK;
                        node=node->parent->parent;
                        node->RB_COLOR=RED;
                    }
                    else
                    {
                        if(node->parent==node->parent->parent->left)    //case 2
                        {
                            node=node->parent;
                            left_rotate(node);
                           // goto double_right_rotate;
                        }
                        //case2结束以后直接进入case3，或者直接进入case3
                      //  double_left_rotate:
                        else{
                            node->parent->RB_COLOR=BLACK;
                            node->parent->parent->RB_COLOR=RED;
                            left_rotate(node->parent->parent);
                        }
                    }
                }
            }
            if(node==root)
                node->RB_COLOR=BLACK;
        }

        //左旋转
        void left_rotate(RB_Node<Value> *node)
        {
            RB_Node<Value> *temp=node->right;
            temp->parent=node->parent;
            if(node->parent==nullNode)
                root=temp;
            else
            {
                if(node==node->parent->left)
                    node->parent->left=temp;
                else
                    node->parent->right=temp;
            }
            node->right=temp->left;
            if(temp->left!=nullNode)
                temp->left->parent=node;
            node->parent=temp;
            temp->left=node;
        }
        //右旋转
        void right_rotate(RB_Node<Value> *node)
        {
            RB_Node<Value> *temp=node->left;
            temp->parent=node->parent;
            if(node==root) //等价于node->parent==NULL
                root=temp;
            else
            {
                if(node==node->parent->left)
                    node->parent->left=temp;
                else
                    node->parent->right=temp;
            }
            node->left=temp->right;
            if(temp->right!=nullNode)
                temp->right->parent=node;
            node->parent=temp;
            temp->right=node;

        }

        //找到值为value的节点
        RB_Node<Value>* find_node(Value value)
        {
            RB_Node<Value> *temp=root;
            while(temp!=nullNode)
            {
                if(key_compare(KeyOfValue()(value),key(temp)))
                    temp=temp->left;
                else if(key_compare(key(temp),KeyOfValue()(value)))
                    temp=temp->right;
                else
                    break;
            }
            return temp;
        }

        //该函数的功能是用来在删除节点时，如果节点存在左右孩子节点则找到应该替换的节点
        RB_Node<Value>* find_delete_node(RB_Node<Value> *node)
        {
            if(node->left==nullNode||node==nullNode)
                return nullNode;
            RB_Node<Value> *temp=node->left;
            while(temp->right!=nullNode)
                temp=temp->right;
            return temp;

        }

        void deleteFixUp(RB_Node<Value> *node)
        {
            RB_Node<Value> *temp=node;
            while(temp->RB_COLOR==BLACK&&temp!=root)
            {
                RB_Node<Value> *brother;
                //该节点为父节点的左节点
                if(temp==temp->parent->left)
                {
                    brother=temp->parent->right;
                    if(brother->RB_COLOR==RED)   //case 1
                    {
                        temp->parent->RB_COLOR=RED;
                        brother->RB_COLOR=BLACK;
                        //在旋转之后兄弟节点会发生变化，因此在旋转之前就将兄弟节点给换过来
                        brother=brother->left;
                        left_rotate(temp->parent);
                    }
                    //case 1结束后，会进入case2/case3/case4
                    if(brother->left->RB_COLOR==BLACK&&brother->right->RB_COLOR==BLACK)  //case2
                    {
                        brother->RB_COLOR=RED;
                        temp=temp->parent;
                    }
                    else
                    {
                        if(brother->right->RB_COLOR==BLACK)   //case 3
                        {
                            brother->RB_COLOR=RED;
                            brother->left->RB_COLOR=BLACK;
                            brother=brother->left;
                            right_rotate(brother->parent);
                        }
                        //进入case4情况
                        brother->RB_COLOR=temp->parent->RB_COLOR;
                        brother->right->RB_COLOR=temp->parent->RB_COLOR=BLACK;
                        left_rotate(temp->parent);
                        temp=root;
                    }
                }
                else  //该节点为父节点的右孩子
                {
                    brother=temp->parent->left;
                    if(brother->RB_COLOR==RED)   //case 1
                    {
                        temp->parent->RB_COLOR=RED;
                        brother->RB_COLOR=BLACK;
                        //在旋转之后兄弟节点会发生变化，因此在旋转之前就将兄弟节点给换过来
                        brother=brother->right;
                        right_rotate(temp->parent);
                    }
                    //case 1结束后，会进入case2/case3/case4
                    if(brother->left->RB_COLOR==BLACK&&brother->right->RB_COLOR==BLACK)  //case2
                    {
                        brother->RB_COLOR=RED;
                        temp=temp->parent;
                    }
                    else
                    {
                        if(brother->right->RB_COLOR==BLACK)   //case 3
                        {
                            brother->RB_COLOR=RED;
                            brother->left->RB_COLOR=BLACK;
                            brother=brother->left;
                            left_rotate(brother->parent);
                        }
                        //进入case4情况
                        brother->RB_COLOR=temp->parent->RB_COLOR;
                        brother->right->RB_COLOR=temp->parent->RB_COLOR=BLACK;
                        right_rotate(temp->parent);
                        temp=root;
                    }

                }
            }
            //最后退出来的时候记得将节点颜色变成黑色
            temp->RB_COLOR=BLACK;
        }

        RB_Node<Value>* alloc(COLOR color, Value value)
        {
            RB_Node<Value>* temp=RB_Node_Container::alloc(1);
            construct(temp,RB_Node<Value>(color,value));
            return temp;
        }


    public:
        //定义迭代器
        typedef Iterator_RB_Node<Value,Value&,Value*> iterator;
        typedef Iterator_RB_Node<Value,const Value&,const Value*> const_iterator;
        iterator begin()
        {
            RB_Node<Value>* temp=root;
            while(temp->left!=nullNode)
                temp=temp->left;
            return iterator(temp,nullNode);
        }
        iterator end(){  return iterator(nullNode,nullNode);}

        iterator minleft() {return begin();}
        iterator maxright()
        {
            RB_Node<Value>* temp=root;
            while(temp->right!=nullNode)
                temp=temp->right;
            return iterator(temp,nullNode);
        }

        //得到迭代器所指对象的key值
        key_type key(RB_Node<Value> *iter)
        {
            return KeyOfValue()(iter->data);
        }

        //构造函数初始化
        RB_Tree()
        {
            nullNode=alloc(BLACK,Value());
            root=nullNode;
            node_num=0;
            nullNode->left=nullNode->right=nullNode;
            nullNode->parent=root;

        }

        //红黑树的插入操作
        void insert_node(Value value)
        {
            node_num++;
            RB_Node<Value> *node=alloc(RED,value);
            node->left=node->right=node->parent=nullNode;
            if(root==nullNode)    //先把空树的情况处理掉
            {
                root=node;
                root->RB_COLOR=BLACK;
                return ;
            }
            RB_Node<Value> *temp=root;
            RB_Node<Value> *insert_parent;
            while(temp!=nullNode)
            {
                insert_parent=temp;
                // if(value<temp->data)
                if(key_compare(KeyOfValue()(value),key(temp)))
                    temp=temp->left;
                else
                    temp=temp->right;
            }
            // if(value<insert_parent->data)
            if(key_compare(KeyOfValue()(value),key(insert_parent)))
                insert_parent->left=node;
            else
                insert_parent->right=node;
            node->parent=insert_parent;
            //完成插入后的修复工作
            InsertFixUp(node);
        }

        //红黑树的删除操作
        void delete_node(Value value)
        {
            node_num--;
            RB_Node<Value> *node= find_node(value);
            RB_Node<Value> *delete_node,*delete_node_child;
            if(node->left==nullNode||node->right==nullNode)
                delete_node=node;
            else
                delete_node=find_delete_node(node);

            //如果删除点不是node，则应该将delete_node值复制过来
            if(delete_node!=node)
                node->data=http://www.mamicode.com/delete_node->data;>
#ifndef ITERATOR_RB_TREE_H_INCLUDED
#define ITERATOR_RB_TREE_H_INCLUDED

#include"my_iterator_base.h"
/*
**
iterator_rb_tree.h
红黑树地泛型容器地迭代器
与以往前面地容器构造方式不同，该容器采用双层架构，使其获得更加大的弹性
*/

namespace juine
{
    enum COLOR{RED,BLACK};

    template<class T>                //红黑树的节点信息
    struct RB_Node
    {
        typedef RB_Node* base_ptr;
        base_ptr left;
        base_ptr right;
        base_ptr parent;
        COLOR RB_COLOR;
        T data;
        RB_Node(COLOR _RB_COLOR=BLACK,T _data=http://www.mamicode.com/0):RB_COLOR(_RB_COLOR),data(_data){}>
以下是测试代码：
#include<iostream>
#include"my_rb_tree.h"
//#include<stack>
using namespace std;
using namespace juine;
template<typename T>
struct identity
{
    const T& operator()(const T& x)
    {
        return x;
    }
};

template<class T>
struct comp
{
    bool operator()(T v1,T v2)
    {
        return v1>v2;
    }

};
int main()
{
    RB_Tree<int,int,identity<int>,comp<int> > q;
    int i;
    for(i=1;i<10;i++)
        q.insert_node(i);
    RB_Tree<int,int,identity<int>,comp<int> >::iterator iter=q.maxright();
        for(iter=q.maxright();iter!=q.end();iter--)
            cout<<*iter<<"  颜色为： "<<iter->RB_COLOR<<endl;
    for(i=1;i<10;i++)
    {
        q.delete_node(i);
        cout<<"删除"<<i<<"后："<<endl;
        RB_Tree<int,int,identity<int>,comp<int> >::iterator iter=q.maxright();
        for(iter=q.maxright();iter!=q.end();iter--)
            cout<<*iter<<"  颜色为： "<<iter->RB_COLOR<<endl;
    }

    return 0;
}