|
子均为黑色 { ///将w染成红色,此时w子树减少了一个黑结点,和x子树黑结点数目相同 ///但__x_parent子树比其兄弟子树少一个结点,因此令x=__x_parent, ///交由下次循环处理 __w->_M_color = _S_rb_tree_red; __x = __x_parent; __x_parent = __x_parent->_M_parent; } else ///w为黑色,其孩子一红一黑或者同为红色 { if (__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) ///w孩子节点左红右黑 { if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; __w->_M_color = _S_rb_tree_red; _Rb_tree_rotate_right(__w, __root); __w = __x_parent->_M_right; ///此处w仍然为黑色,w子树的黑结点仍然比x子树多1,但w的孩子节点为左黑右红,交由下面处理 } ///此时此处w一定为黑色,w子树的黑结点一定比x子树多1,w的右孩子节点一定为红色 __w->_M_color = __x_parent->_M_color; __x_parent->_M_color = _S_rb_tree_black; if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; _Rb_tree_rotate_left(__x_parent, __root); ///至此处可保证整棵树符合RB树的定义 break; } } else /// same as above, with _M_right <-> _M_left. { _Rb_tree_node_base* __w = __x_parent->_M_left; if (__w->_M_color == _S_rb_tree_red) { __w->_M_color = _S_rb_tree_black; __x_parent->_M_color = _S_rb_tree_red; _Rb_tree_rotate_right(__x_parent, __root); __w = __x_parent->_M_left; } if ((__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black) && (__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black)) { __w->_M_color = _S_rb_tree_red; __x = __x_parent; __x_parent = __x_parent->_M_parent; } else { if (__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) { if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; __w->_M_color = _S_rb_tree_red; _Rb_tree_rotate_left(__w, __root); __w = __x_parent->_M_left; } __w->_M_color = __x_parent->_M_color; __x_parent->_M_color = _S_rb_tree_black; if (__w->_M_left) __w->_M_left->_M_color = _S_rb_tree_black; _Rb_tree_rotate_right(__x_parent, __root); break; } } if (__x) __x->_M_color = _S_rb_tree_black; } return __y; } /// In order to avoid having an empty base class, we arbitrarily ///move one of rb_tree's data members into the base class. template
struct _Rb_tree_base { typedef _Alloc allocator_type; allocator_type get_allocator() const { return allocator_type(); } _Rb_tree_base(const allocator_type&) : _M_header(0) { _M_header = _M_get_node(); } ~_Rb_tree_base() { _M_put_node(_M_header); } protected: _Rb_tree_node<_Tp>* _M_header; ///不存储数据元素,只存储指向根节点,最小节点, ///和最大结点的指针 typedef simple_alloc<_Rb_tree_node<_Tp>, _Alloc> _Alloc_type; _Rb_tree_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } void _M_put_node(_Rb_tree_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } }; template
class _Rb_tree : protected _Rb_tree_base<_Value, _Alloc> { typedef _Rb_tree_base<_Value, _Alloc> _Base; protected: typedef _Rb_tree_node_base* _Base_ptr; typedef _Rb_tree_node<_Value> _Rb_tree_node; typedef _Rb_tree_Color_type _Color_type; public: typedef _Key key_type; typedef _Value value_type; typedef value_type* pointer; typedef const value_type* const_pointer; typedef value_type& reference; typedef const value_type& const_reference; typedef _Rb_tree_node* _Link_type; typedef size_t size_type; typedef ptrdiff_t difference_type; typedef typename _Base::allocator_type allocator_type; allocator_type get_allocator() const { return _Base::get_allocator(); } protected: using _Base::_M_get_node; using _Base::_M_put_node; using _Base::_M_header; protected: _Link_type _M_create_node(const value_type& __x) { _Link_type __tmp = _M_get_node(); try { construct(&__tmp->_M_value_field, __x); } catch(...) { _M_put_node(__tmp); } return __t |