|
arent->_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; } else { if (__x == __x->_M_parent->_M_left) { __x = __x->_M_parent; _Rb_tree_rotate_right(__x, __root); } __x->_M_parent->_M_color = _S_rb_tree_black; __x->_M_parent->_M_parent->_M_color = _S_rb_tree_red; _Rb_tree_rotate_left(__x->_M_parent->_M_parent, __root); } } } __root->_M_color = _S_rb_tree_black; ///调整根节点颜色 } ///删除结点z并调整该树,使其符合RB树的定义 inline _Rb_tree_node_base* _Rb_tree_rebalance_for_erase(_Rb_tree_node_base* __z, _Rb_tree_node_base*& __root, _Rb_tree_node_base*& __leftmost, _Rb_tree_node_base*& __rightmost) { _Rb_tree_node_base* __y = __z; _Rb_tree_node_base* __x = 0; _Rb_tree_node_base* __x_parent = 0; if (__y->_M_left == 0) /// __z has at most one non-null child. y == z. __x = __y->_M_right; /// __x might be null. else if (__y->_M_right == 0) /// __z has exactly one non-null child. y == z. __x = __y->_M_left; /// __x is not null. else { ///为了删除以后方便调整,RB树只删除没有孩子或只有一个孩子的结点 ///如果需要删除的结点具有双孩子,需要找到该结点的后继(一定无双孩子) ///然后用后继代替该节点,同时染上该节点的颜色,调整因此,实际删除 ///的结点永远无双孩子 /// __z has two non-null children. Set __y to __y = __y->_M_right; /// __z's successor. __x might be null. while (__y->_M_left != 0) __y = __y->_M_left; __x = __y->_M_right; } if (__y != __z) ///z具有双孩子 { /// relink y in place of z. y is z's successor __z->_M_left->_M_parent = __y; __y->_M_left = __z->_M_left; if (__y != __z->_M_right) { __x_parent = __y->_M_parent; if (__x) __x->_M_parent = __y->_M_parent; __y->_M_parent->_M_left = __x; /// __y must be a child of _M_left __y->_M_right = __z->_M_right; __z->_M_right->_M_parent = __y; } else __x_parent = __y; if (__root == __z) __root = __y; else if (__z->_M_parent->_M_left == __z) __z->_M_parent->_M_left = __y; else __z->_M_parent->_M_right = __y; __y->_M_parent = __z->_M_parent; __STD::swap(__y->_M_color, __z->_M_color); __y = __z; /// __y now points to node to be actually deleted } else /// __y == __z { ///z不具有双孩子 __x_parent = __y->_M_parent; if (__x) __x->_M_parent = __y->_M_parent; if (__root == __z) __root = __x; else if (__z->_M_parent->_M_left == __z) __z->_M_parent->_M_left = __x; else __z->_M_parent->_M_right = __x; if (__leftmost == __z) if (__z->_M_right == 0) /// __z->_M_left must be null also __leftmost = __z->_M_parent; /// makes __leftmost == _M_header if __z == __root else __leftmost = _Rb_tree_node_base::_S_minimum(__x); if (__rightmost == __z) if (__z->_M_left == 0) /// __z->_M_right must be null also __rightmost = __z->_M_parent; /// makes __rightmost == _M_header if __z == __root else /// __x == __z->_M_left __rightmost = _Rb_tree_node_base::_S_maximum(__x); } ///删除完毕,需要调整,和rebalance一样是按子树逐层上溯处理,直到整棵树合法为止 ///如果为红色结点不需要调整 if (__y->_M_color != _S_rb_tree_red) { ///如果x是根结点或者红色结点,只需最后调整结点颜色为黑色即可使整棵树满足RB树的定义 while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black)) if (__x == __x_parent->_M_left) { ///w为被删结点的兄弟,由于删除操作,w子树比x子树多一个黑结点 _Rb_tree_node_base* __w = __x_parent->_M_right; if (__w->_M_color == _S_rb_tree_red) { ///通过调整将w变为黑色,交由下面处理 __w->_M_color = _S_rb_tree_black; __x_parent->_M_color = _S_rb_tree_red; _Rb_tree_rotate_left(__x_parent, __root); __w = __x_parent->_M_right; } ///此时w一定为黑色,而且仍然比x子树多一个黑结点 if ((__w->_M_left == 0 || __w->_M_left->_M_color == _S_rb_tree_black) && (__w->_M_right == 0 || __w->_M_right->_M_color == _S_rb_tree_black)) ///w的两个孩 |