RB-tree（红黑树）

RB-tree的节点设计

SGI STL的实现源代码为了有更大的弹性，节点和迭代器都分为两层。

typedef bool __rb_tree_color_type;            
const __rb_tree_color_type __rb_tree_red = false;    //定义红色为0
const __rb_tree_color_type __rb_tree_black = true;    //定义黑色为1

struct __rb_tree_node_base
{
    typedef __rb_tree_color_type color_type;        //bool
    typedef __rb_tree_node_base* base_ptr;           

    color_type color;                      //定义节点颜色
    base_ptr parent;                       //指向父节点
    base_ptr left;                         //指向左孩子
    base_ptr right;                        //指向右孩子

    static base_ptr minimum(base_ptr x)    //取以x为根节点的最小值
    {
        while(NULL != x->next) x = x->left;
        return x;
    }

    static base_ptr maximum(base_ptr x)     //取以x为根节点的最大值
    {
        while(NULL != x->next) x = x->right;
        return x;
    }
};

template<class Value>
struct __rb_tree_node : public __rb_tree_node_base
{
    typedef __rb_tree_node<Value>* link_type;   //重命名指向其他节点的指针
    Value value_field;             //节点值
};

RB-tree的迭代器

基层迭代器

struct __rb_tree_base_iterator
{
    typedef __rb_tree_node_base::base_ptr base_ptr;     //即__rb_tree_node_base*
    typedef bidirectional_iterator_tag iterator_category;    //双向迭代器类型
    typedef ptrdiff_t difference_type;        //表示迭代器之间的距离

    base_ptr node;     //与容器之间产生一个连结关系

    void increment()       //在顺序队列中找到node的下一位
    {
        if(node -> right != 0)     //该节点有右子树，右子树的最小值
        {
            node = node->right;
            while(node->left != 0)
            {
                node = node->left;
            }
        }
        else                        //该节点没有右子树
        { 
            base_ptr y = node->parent;      //若该节点为父节点的左孩子，找该节点的父节点，就是我们要找的
            while(node == y->right)         //若该节点为父节点的右孩子，向上找，直至不为右孩子，有两种情况：(1)该节点为最大值，直到null(2).该节点的位于某个节点的左子树上，找到了这个节点
            {
                node = y;
                y = y->parent;
            }
            if(node->right != y)
            {
                node = y;
            }
        }
    }

    void decrement()     //在顺序队列中找到node的上一位
    {
        if(node->color == __rb_tree_red && node->parent->parent == node)
        {
            node = node->right;
        }
        else if(node->left != 0)     //左子树的最大值
        {
            base_ptr y = node->left;
            while(y->right != 0)
            {
                y = y->right;
            }
            node = y;
        }
        else                    //找父节点         
        {
            base_ptr y = node->parent;
            while(node == y->left)
            {
                node = y;
                y = y->parent;
            }
            node = y;
        }
    }

};

正规迭代器

template<class Value, class Ref, class Ptr>
struct __rb_tree_iterator : public __rb_tree_base_iterator
{
    typedef Value value_type;
    typedef Ref reference;
    typedef Ptr pointer;
    typedef __rb_tree_iterator<Value, Ref, Ptr> self;
    typedef __rb_tree_iterator<Value, Value&, Value*> iterator;
    typedef __rb_tree_iterator<Value, const Value&, const Value*> const_iterator;

    __rb_tree_iterator() {}
    __rb_tree_iterator(link_type x) { node = x; }
    __rb_tree_iterator(const iterator& it) { node = it.node; }

    reference operator*() const 
    {
        return link_type(node)->value_field;
    }
#ifndef   __SGI_STL_NO_ARROW_OPERATOR
    pointer operator->() const { return &(operator*());}
#endif
    self& operator++()
    {
        increment();
        return *this;
    }
    self operator++(int)
    {
        self tmp = *this;
        increment();
        return tmp;
    }
    self& operator--()
    {
        decrement();
        return *this;
    }
    self operator--(int)
    {
        self tmp = *this;
        decrement();
        return tmp;
    }
};    

RB-tree的数据结构