/**
Red-black tree class, designed for use in implementing STL
associative containers (set, multiset, map, and multimap). The
insertion and deletion algorithms are based on those in Cormen,
Leiserson, and Rivest, Introduction to Algorithms (MIT Press, 1990),
except that

(1) the header cell is maintained with links not only to the root
but also to the leftmost node of the tree, to enable constant time
begin(), and to the rightmost node of the tree, to enable linear time
performance when used with the generic set algorithms (set_union,
etc.);

(2) when a node being deleted has two children its successor node is
relinked into its place, rather than copied, so that the only
iterators invalidated are those referring to the deleted node.
*/

typedef bool _Rb_tree_Color_type;
const _Rb_tree_Color_type _S_rb_tree_red = false;
const _Rb_tree_Color_type _S_rb_tree_black = true;

struct _Rb_tree_node_base
{
    typedef _Rb_tree_Color_type _Color_type;
    typedef _Rb_tree_node_base* _Base_ptr;

    _Color_type _M_color;
    _Base_ptr _M_parent;     ///指向父节点的指针
    _Base_ptr _M_left;
    _Base_ptr _M_right;

    ///寻找以x为根节点的RB树的最小值结点
    static _Base_ptr _S_minimum(_Base_ptr __x)
    {
        while (__x->_M_left != 0) __x = __x->_M_left;
        return __x;
    }

    ///寻找以x为根节点的RB树的最大值结点
    static _Base_ptr _S_maximum(_Base_ptr __x)
    {
        while (__x->_M_right != 0) __x = __x->_M_right;
        return __x;
    }
};

template 
  
   
struct _Rb_tree_node : public _Rb_tree_node_base
{
    typedef _Rb_tree_node<_Value>* _Link_type;
    _Value _M_value_field;
};


struct _Rb_tree_base_iterator
{
    typedef _Rb_tree_node_base::_Base_ptr _Base_ptr;
    typedef bidirectional_iterator_tag iterator_category;   ///双向迭代器
    typedef ptrdiff_t difference_type;
    _Base_ptr _M_node;

    ///找到递增序列的后继
    void _M_increment()
    {
        if (_M_node->_M_right != 0)    ///如果右子树非空
        {

            ///找到右子树的最左端子孙结点
            _M_node = _M_node->_M_right;
            while (_M_node->_M_left != 0)
                _M_node = _M_node->_M_left;
        }
        else                                         ///右子树为空
        {

            _Base_ptr __y = _M_node->_M_parent;

            ///沿着父节点上溯,直到其为父节点的左孩子,或者到达根节点
            while (_M_node == __y->_M_right)
            {
                _M_node = __y;
                __y = __y->_M_parent;
            }

            ///结点的右孩子不为其父节点,则后继即为该父节点,如果结点的右孩子为其父节点
            ///只有一种情况,根节点无右子树(根节点为right_most结点),此时while循环亦会将迭
            ///代器指针指向end结点,因此在此处不需要再次修改迭代器指向.
            if (_M_node->_M_right != __y)
                _M_node = __y;
        }

    }

    ///找到递增序列的前驱
    void _M_decrement()
    {
        if (_M_node->_M_color == _S_rb_tree_red &&
                _M_node->_M_parent->_M_parent == _M_node)   ///对end迭代器进行递减,指向最大值
            _M_node = _M_node->_M_right;

        else if (_M_node->_M_left != 0)             ///左子树不为空
        {

            ///找到左子树最右边子孙结点
            _Base_ptr __y = _M_node->_M_left;
            while (__y->_M_right != 0)
                __y = __y->_M_right;
            _M_node = __y;
        }
        else                                  ///左子树为空
        {

            ///沿着父节点上溯,直到其为父节点的右孩子,或者到达根节点
            _Base_ptr __y = _M_node->_M_parent;
            while (_M_node == __y->_M_left)
            {
                _M_node = __y;
                __y = __y->_M_parent;
            }

            ///找到前驱,即为其父节点
            _M_node = __y;
        }
    }
};

template 
   
     struct _Rb_tree_iterator : public _Rb_tree_base_iterator { typedef _Value value_type; typedef _Ref reference; typedef _Ptr pointer; typedef _Rb_tree_iterator<_Value, _Value&, _Value*> iterator; typedef _Rb_tree_iterator<_Value, const _Value&, const _Value*> const_iterator; typedef _Rb_tree_iterator<_Value, _Ref, _Ptr> _Self; typedef _Rb_tree_node<_Value>* _Link_type; _Rb_tree_iterator() {} _Rb_tree_iterator(_Link_type __x) { _M_node = __x; } _Rb_tree_iterator(const iterator& __it) { _M_node = __it._M_node; ///指向同一位置即可 } reference operator*() const { return _Link_type(_M_node)->_M_value_fie