? ? ? ? ? ? ? ? link_type(erase_ptr)->data=link_type(successor_ptr)->data;

? ? ? ? ? ? ? ? if(successor_ptr==successor_ptr->parent->left)

? ? ? ? ? ? ? ? ? ? successor_ptr->parent->left=successor_ptr->right;

? ? ? ? ? ? ? ? if(successor_ptr==successor_ptr->parent->right)

? ? ? ? ? ? ? ? ? ? successor_ptr->parent->right=successor_ptr->right;

? ? ? ? ? ? ? ? if(successor_ptr->right)

? ? ? ? ? ? ? ? ? ? successor_ptr->right->parent=successor_ptr->parent;

?

? ? ? ? ? ? ? ? fix_up_ptr=successor_ptr->right;

? ? ? ? ? ? ? ? fix_up_parent_ptr=successor_ptr->parent;

? ? ? ? ? ? ? ? erase_color=successor_ptr->color;

? ? ? ? ? ? ? ? delete successor_ptr;

? ? ? ? ? ? }else{//直接用左子树代替，或者找到后继节点代替也行，但比较麻烦，效果一样。

? ? ? ? ? ? ? ? if(erase_ptr ==erase_ptr->parent->left)

? ? ? ? ? ? ? ? ? ? erase_ptr->parent->left=erase_ptr->left;

? ? ? ? ? ? ? ? else

? ? ? ? ? ? ? ? ? ? erase_ptr->parent->right=erase_ptr->left;

? ? ? ? ? ? ? ? erase_ptr->left->parent=erase_ptr->parent;

? ? ? ? ? ? ? ? fix_up_ptr=erase_ptr->left;

? ? ? ? ? ? ? ? fix_up_parent_ptr=erase_ptr->parent;

? ? ? ? ? ? ? ? erase_color=erase_ptr->color;

? ? ? ? ? ? ? ? delete erase_ptr;

? ? ? ? ? ? }

? ? ? ? ? ? if(erase_color==BLACK)

? ? ? ? ? ? ? ? return _erase_fix_up(fix_up_ptr,fix_up_parent_ptr);

? ? ? ? }
? ? ? ? return false;
? ? }

? ? template
? ? typename rb_tree::rb_ptr rb_tree::find(const Value& e) {

? ? ? ? rb_ptr root=head->parent;

? ? ? ? if(head->parent !=head){

? ? ? ? ? ? while(root){

? ? ? ? ? ? ? ? if(link_type(root)->data == e)

? ? ? ? ? ? ? ? ? ? return root;

? ? ? ? ? ? ? ? else if( e<=link_type(root)->data){

? ? ? ? ? ? ? ? ? ? root=root->left;

? ? ? ? ? ? ? ? }else

? ? ? ? ? ? ? ? ? ? root=root->right;

? ? ? ? ? ? }

? ? ? ? }
? ? ? ? return nullptr;
? ? }
? ? /**
? ? * current_ptr节点的祖父节点一定是黑色，因为它的父节点是红色的，所以性质4只在插入节点和该父节点被破坏
? ? *? 情况1：叔节节点uncle_ptr是红色；
? ? *? ? ? ? ? 1）父节点parent_ptr和叔节点uncle_ptr的颜色改为黑色,祖父节点grandfather_ptr的颜色改为红色
? ? *? ? ? ? ? 2）把current_ptr节点设置为grandfather，因为只有祖父节点和祖父节点的父节点之间会违法性质。

? ? *? 情况2：叔父节点uncle_ptr是黑色，或者unclue_ptr为空；

? ? *? ? ? ? 1）根据根据当前节点的位置，把当前节点current_ptr设置为parent_ptr,对其左旋或右旋。

? ? *? 情况3：叔父节点存在或者叔父节点颜色为黑色，且父右儿右关系（或父左儿左）

? ? ? ? ? ? ? 1）把父节点颜色设为黑色，把祖父颜色设为红色

? ? ? ? ? ? ? 2）对祖父节点进行左旋（或右旋）
? ? *
? ? */
? ? template
? ? bool rb_tree:: _insert_fix_up(rb_ptr current_ptr){
? ? ? ? while(current_ptr->parent->color ==RED){

? ? ? ? ? ? rb_ptr parent_ptr =current_ptr->parent;
? ? ? ? ? ? rb_ptr? grandfather_ptr=parent_ptr->parent;
? ? ? ? ? ? if(parent_ptr ==grandfather_ptr->left){
? ? ? ? ? ? ? ? rb_ptr? uncle_ptr=parent_ptr->parent->right;
? ? ? ? ? ? ? ? if(uncle_ptr && uncle_ptr->color==RED){
? ? ? ? ? ? ? ? ? ? parent_ptr->color=BLACK;
? ? ? ? ? ? ? ? ? ? uncle_ptr->color=BLACK;
? ? ? ? ? ? ? ? ? ? grandfather_ptr->color=RED;
? ? ? ? ? ? ? ? ? ? current_ptr=grandfather_ptr;
? ? ? ? ? ? ? ? }else if(current_ptr ==parent_ptr->right){
? ? ? ? ? ? ? ? ? ? current_ptr=parent_ptr;
? ? ? ? ? ? ? ? ? ? _left_rotate(current_ptr);
? ? ? ? ? ? ? ? }else{

? ? ? ? ? ? ? ? ? ? current_ptr->parent->color=BLACK;
? ? ? ? ? ? ? ? ? ? current_ptr->parent->parent->color=RED;
? ? ? ? ? ? ? ? ? ? _right_rotate(current_ptr->parent->parent);