rent_ptr);//其实就是转换为父右儿右的情况
? ? ? ? ? ? ? ? }else{//父右儿右
? ? ? ? ? ? ? ? ? ? current_ptr->parent->color=BLACK;
? ? ? ? ? ? ? ? ? ? current_ptr->parent->parent->color=RED;
? ? ? ? ? ? ? ? ? ? _left_rotate(current_ptr->parent->parent);
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? head->parent->color=BLACK;
? ? ? ? return true;
? ? }
? ? template
? ? bool rb_tree::_erase_fix_up(rb_ptr current_ptr,rb_ptr parent_ptr){
? ? ? ? while((!current_ptr||current_ptr->color==BLACK)&¤t_ptr!=head->parent){
? ? ? ? ? ? if(parent_ptr->left ==current_ptr){
? ? ? ? ? ? ? ? rb_ptr brother_ptr = parent_ptr->right;
? ? ? ? ? ? ? ? if(brother_ptr->color ==RED){
? ? ? ? ? ? ? ? ? ? parent_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? brother_ptr->color=BLACK;
? ? ? ? ? ? ? ? ? ? _left_rotate(brother_ptr);
? ? ? ? ? ? ? ? ? ? brother_ptr=current_ptr->parent->right;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(brother_ptr->color==BLACK &&
? ? ? ? ? ? ? ? ? ? ? ? (!brother_ptr->left ||brother_ptr->left->color ==BLACK)&&
? ? ? ? ? ? ? ? ? ? ? ? (!brother_ptr->right || brother_ptr->right->color ==BLACK)){
? ? ? ? ? ? ? ? ? ? brother_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? current_ptr=parent_ptr;
? ? ? ? ? ? ? ? ? ? parent_ptr=current_ptr->parent;
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? if(brother_ptr->color==BLACK &&
? ? ? ? ? ? ? ? ? ? ? ? (!brother_ptr->right||brother_ptr->right->color==BLACK)){//右侄黑，左侄红
?
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr->left->color=BLACK;
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? ? ? _right_rotate(brother_ptr);
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr=parent_ptr->right;
? ? ? ? ? ? ? ? ? ? }//右侄红色
? ? ? ? ? ? ? ? ? ? brother_ptr->color=parent_ptr->color;
? ? ? ? ? ? ? ? ? ? parent_ptr->color=BLACK;
? ? ? ? ? ? ? ? ? ? if(brother_ptr->right)
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr->right->color=BLACK;
? ? ? ? ? ? ? ? ? ? _left_rotate(parent_ptr);
? ? ? ? ? ? ? ? ? ? current_ptr=head->parent;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }else{
? ? ? ? ? ? ? ? rb_ptr brother_ptr = parent_ptr->left;
? ? ? ? ? ? ? ? if(brother_ptr->color ==RED){
? ? ? ? ? ? ? ? ? ? parent_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? brother_ptr->color=BLACK;
? ? ? ? ? ? ? ? ? ? _right_rotate(brother_ptr);
? ? ? ? ? ? ? ? ? ? brother_ptr=current_ptr->parent->left;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(brother_ptr->color==BLACK &&
? ? ? ? ? ? ? ? ? ? ? ? (!brother_ptr->left ||brother_ptr->left->color ==BLACK)&&
? ? ? ? ? ? ? ? ? ? ? ? (!brother_ptr->right || brother_ptr->right->color ==BLACK)){
? ? ? ? ? ? ? ? ? ? brother_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? current_ptr=parent_ptr;
? ? ? ? ? ? ? ? ? ? parent_ptr=current_ptr->parent;
? ? ? ? ? ? ? ? }else {
? ? ? ? ? ? ? ? ? ? if(brother_ptr->color==BLACK &&
? ? ? ? ? ? ? ? ? ? ? ? (!brother_ptr->right||brother_ptr->right->color==BLACK)){//右侄黑，左侄红
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr->left->color=BLACK;
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? ? ? _left_rotate(brother_ptr);
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr=parent_ptr->left;
? ? ? ? ? ? ? ? ? ? }//右侄红色
? ? ? ? ? ? ? ? ? ? brother_ptr->color=parent_ptr->color;
? ? ? ? ? ? ? ? ? ? parent_ptr->color=BLACK;
? ? ? ? ? ? ? ? ? ? if(brother_ptr->left)
? ? ? ? ? ? ? ? ? ? ? ? brother_ptr->left->color=BLACK;
? ? ? ? ? ? ? ? ? ? _right_rotate(parent_ptr);
? ? ? ? ? ? ? ? ? ? current_ptr=head->parent;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? if (current_ptr)
? ? ? ? ? ? current_ptr->color=BLACK;
? ? ? ? return true;
? ? }
? ? template
? ? typename rb_tree::rb_ptr rb_tree::_successor(rb_ptr current_ptr) const{
? ? ? ? rb_ptr right_child_ptr = current_ptr->right;
? ? ? ? if(right_child_ptr){
? ? ? ? ? ? rb_ptr left_ptr =right_child_ptr->left;
? ? ? ? ? ? rb_ptr left_remember_ptr;
? ? ? ? ? ? if(left_ptr){
? ? ? ? ? ? ? ? while(left_ptr){
? ? ? ? ? ? ? ? ? ? left_remember_ptr =left_ptr;
? ? ? ? ? ? ? ? ? ? left_ptr=left_