|
ld; } pointer operator->() const { return &(operator*()); } _Self& operator++() { _M_increment(); return *this; } _Self operator++(int) { _Self __tmp = *this; _M_increment(); return __tmp; } _Self& operator--() { _M_decrement(); return *this; } _Self operator--(int) { _Self __tmp = *this; _M_decrement(); return __tmp; } }; inline bool operator==(const _Rb_tree_base_iterator& __x, const _Rb_tree_base_iterator& __y) { return __x._M_node == __y._M_node; } inline bool operator!=(const _Rb_tree_base_iterator& __x, const _Rb_tree_base_iterator& __y) { return __x._M_node != __y._M_node; } inline bidirectional_iterator_tag iterator_category(const _Rb_tree_base_iterator&) { return bidirectional_iterator_tag(); } inline _Rb_tree_base_iterator::difference_type* distance_type(const _Rb_tree_base_iterator&) { return (_Rb_tree_base_iterator::difference_type*) 0; } template
inline _Value* value_type(const _Rb_tree_iterator<_Value, _Ref, _Ptr>&) { return (_Value*) 0; } ///将以__x为根的子树左旋 inline void _Rb_tree_rotate_left(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) { ///用__x->_M_right取代__x的位置,x取代x->_M_right的左孩子 ///x->_M_right的左孩子取代x的右孩子 _Rb_tree_node_base* __y = __x->_M_right; __x->_M_right = __y->_M_left; if (__y->_M_left !=0) __y->_M_left->_M_parent = __x; __y->_M_parent = __x->_M_parent; if (__x == __root) __root = __y; else if (__x == __x->_M_parent->_M_left) __x->_M_parent->_M_left = __y; else __x->_M_parent->_M_right = __y; __y->_M_left = __x; __x->_M_parent = __y; } ///将以__x为根的子树右旋 inline void _Rb_tree_rotate_right(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) { ///用__x->_M_left取代__x的位置,x取代x->_M_left的右孩子 ///x->_M_left的右孩子取代x的左孩子 _Rb_tree_node_base* __y = __x->_M_left; __x->_M_left = __y->_M_right; if (__y->_M_right != 0) __y->_M_right->_M_parent = __x; __y->_M_parent = __x->_M_parent; if (__x == __root) __root = __y; else if (__x == __x->_M_parent->_M_right) __x->_M_parent->_M_right = __y; else __x->_M_parent->_M_left = __y; __y->_M_right = __x; __x->_M_parent = __y; } ///插入结点x之后的调整,使其符合RB树的定义, ///调整采用按子树逐层上溯处理,直至整棵树合法为止 inline void _Rb_tree_rebalance(_Rb_tree_node_base* __x, _Rb_tree_node_base*& __root) { __x->_M_color = _S_rb_tree_red; ///新插入的结点默认为红色 ///如果是根节点,只需要最后矫正根节点颜色,如果其父节点为黑色,则无需调整. while (__x != __root && __x->_M_parent->_M_color == _S_rb_tree_red) { if (__x->_M_parent == __x->_M_parent->_M_parent->_M_left) ///父节点为左孩子 { _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_right; ///y为其叔父结点 if (__y && __y->_M_color == _S_rb_tree_red) ///父节点和叔父结点同为红色 { ///其祖父结点必不为红色,因此可以直接将红色上移至其祖父结点, ///然后将其父节点和叔父结点同时染黑,可保证自其祖父结点以下 ///满足RB树的定义. __x->_M_parent->_M_color = _S_rb_tree_black; __y->_M_color = _S_rb_tree_black; __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; __x = __x->_M_parent->_M_parent; ///将x指向其祖父结点,再次循环从其祖父结点开始调整 } else ///其叔父结点为黑色 { ///此时x,x父节点均为红色,x叔父结点为黑色 if (__x == __x->_M_parent->_M_right) ///调整,将x调整为左孩子交由后面处理 { __x = __x->_M_parent; _Rb_tree_rotate_left(__x, __root); } ///此时x必为左孩子,且x,x父节点均为红色,x叔父结点为黑色 __x->_M_parent->_M_color = _S_rb_tree_black; __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; _Rb_tree_rotate_right(__x->_M_parent->_M_parent, __root); ///此时x父节点已经为黑色,可保证整棵树符合RB树的定义,完全可以跳出循环 } } else ///父节点为右孩子,和上面对称操作 { _Rb_tree_node_base* __y = __x->_M_parent->_M_parent->_M_left; if (__y && __y->_M_color == _S_rb_tree_red) { __x->_M_p |