本文共 4462 字，大约阅读时间需要 14 分钟。
//全局函数，用于删除节点后调整树形
//__z为待删除点,__root为根节点,__leftmost左极点，__rightmost为右极点
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; //__y的某个子节点
_Rb_tree_node_base* __x_parent = 0; //__x的父节点
if (__y->_M_left == 0) //__z最多有右子节点一个非空子节点，__y=__z
__x = __y->_M_right; // __x可能为空
else
if (__y->_M_right == 0) // __z确实有一个非空左子节点（因为上个if的限定）. y == z.
__x = __y->_M_left; // __x不为空
else { // __z 有两个非空子节点，设定__y为__z的后继，
__y = __y->_M_right; // __x为__y的右节点，__x可能为空
while (__y->_M_left != 0)
__y = __y->_M_left;
__x = __y->_M_right;
}
if (__y != __z) { // 重新设置__y的链接以取代__z，__y是__z的后继
__z->_M_left->_M_parent = __y; //在__y!=__z是__z的左子节点
__y->_M_left = __z->_M_left; //一定会设置为__y的左子节点
if (__y != __z->_M_right) { //__y不为__z的右子节点是
__x_parent = __y->_M_parent;
if (__x) __x->_M_parent = __y->_M_parent;
__y->_M_parent->_M_left = __x; // __y一定是其父节点的左孩子
__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 现在指向实际被删除的节点
}
else { // __y == __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也一定为0
__leftmost = __z->_M_parent;
// 设定__leftmost为__z的父节点，覆盖了__z为root，__leftmost指向_M_header的情况
else
__leftmost = _Rb_tree_node_base::_S_minimum(__x);
if (__rightmost == __z)
if (__z->_M_left == 0) // __z->_M_right也一定为0
__rightmost = __z->_M_parent;
//设定__rightmost为__z的父节点，覆盖了__z为root，__rightmost指向_M_header的情况
else // __x == __z->_M_left
__rightmost = _Rb_tree_node_base::_S_maximum(__x);
}
//以下代码可把__x看成着双重黑色！
if (__y->_M_color != _S_rb_tree_red) { //只有当__y为黑时才需调整树形
while (__x != __root && (__x == 0 || __x->_M_color == _S_rb_tree_black))
if (__x == __x_parent->_M_left) { //__x为父亲的左儿子
_Rb_tree_node_base* __w = __x_parent->_M_right; //令__w为其兄弟
if (__w->_M_color == _S_rb_tree_red) { //__w为红色时，令__w为黑，__x父亲为红
__w->_M_color = _S_rb_tree_black; //并以__x父亲为旋转点左旋，并更新__w
__x_parent->_M_color = _S_rb_tree_red; //转换为__w为黑的情况
_Rb_tree_rotate_left(__x_parent, __root);
__w = __x_parent->_M_right;
}//以下为__w为黑色的各种情况，
if ((__w->_M_left == 0 || //__w的左右孩子都为黑或者都为空的时候
__w->_M_left->_M_color == _S_rb_tree_black) &&
(__w->_M_right == 0 ||
__w->_M_right->_M_color == _S_rb_tree_black)) {
__w->_M_color = _S_rb_tree_red; //改__w为红色并将__x上移
__x = __x_parent;
__x_parent = __x_parent->_M_parent;
} else {
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; //将左孩子着为黑，原__w改为红
_Rb_tree_rotate_right(__w, __root); //并以原__w为旋转点右旋
__w = __x_parent->_M_right; //然后更新__w，进入__w右孩子为红色的情况
}
//下面为__w右孩子为红的情况
__w->_M_color = __x_parent->_M_color; //着__w为红
__x_parent->_M_color = _S_rb_tree_black; //__x父亲为黑
if (__w->_M_right) __w->_M_right->_M_color = _S_rb_tree_black; //__w右节点着黑色
_Rb_tree_rotate_left(__x_parent, __root); //以__x父亲为旋转点左旋
break; //结束循环
}
} else { // 当__x为右孩子时，与以上情况相同，只需对调左右即可.
_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; //__x为红色时，着__x为黑色即可
}
return __y; //返回__待删除节点地址
}
说明：以下为程序中举出的四种情形
转载地址：https://blog.csdn.net/yangjie569889321/article/details/7905616 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！
发表评论
最新留言
关于作者
