? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? return left_remember_ptr;

? ? ? ? ? ? }

? ? ? ? ? ? return right_child_ptr;

?

? ? ? ? }else{

? ? ? ? ? ? rb_ptr parent_ptr=current_ptr->parent;

? ? ? ? ? ? while(current_ptr ==parent_ptr->right){

? ? ? ? ? ? ? ? current_ptr=parent_ptr;

? ? ? ? ? ? ? ? parent_ptr=parent_ptr->parent;

? ? ? ? ? ? }

? ? ? ? ? ? return parent_ptr;

? ? ? ? }

? ? ? ? return nullptr;

? ? }
? ? template
? ? typename rb_tree::rb_ptr rb_tree::_get_node(const Value& e) const {
? ? ? ? rb_ptr insert_ptr = new tree_node();
? ? ? ? link_type(insert_ptr)->data=e;
? ? ? ? insert_ptr->parent=nullptr;
? ? ? ? insert_ptr->left=nullptr;
? ? ? ? insert_ptr->right=nullptr;
? ? ? ? insert_ptr->color=RED;
? ? ? ? return insert_ptr;
? ? }
? ? template
? ? bool rb_tree::_right_rotate(rb_ptr root){
? ? ? ? if(root->left!=nullptr){
? ? ? ? ? ? rb_ptr left_child_ptr=root->left;

? ? ? ? ? ? root->left=left_child_ptr->right;
? ? ? ? ? ? if(left_child_ptr->right !=nullptr)
? ? ? ? ? ? ? ? left_child_ptr->right->parent=root;

? ? ? ? ? ? left_child_ptr->right=root;
? ? ? ? ? ? left_child_ptr->parent=root->parent;
? ? ? ? ? ? if(root->parent->left ==root)
? ? ? ? ? ? ? ? root->parent->left=left_child_ptr;
? ? ? ? ? ? else if(root->parent->right==root)
? ? ? ? ? ? ? ? root->parent->right=left_child_ptr;

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

? ? ? ? ? ? ? ? root->parent->parent=left_child_ptr;

? ? ? ? ? ? }

? ? ? ? ? ? root->parent=left_child_ptr;
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? return false;
? ? }
? ? template
? ? bool? rb_tree< Value >::_left_rotate(rb_ptr root){
? ? ? ? if(root->right!=nullptr){
? ? ? ? ? ? rb_ptr right_child_ptr=root->right;

? ? ? ? ? ? root->right=right_child_ptr->left;
? ? ? ? ? ? if(right_child_ptr->left != nullptr)
? ? ? ? ? ? ? ? right_child_ptr->left->parent=root;

? ? ? ? ? ? right_child_ptr->left=root;
? ? ? ? ? ? right_child_ptr->parent=root->parent;
? ? ? ? ? ? if(root->parent->left ==root)
? ? ? ? ? ? ? ? root->parent->left=right_child_ptr;
? ? ? ? ? ? else if(root->parent->right ==root)
? ? ? ? ? ? ? ? root->parent->right=right_child_ptr;

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

? ? ? ? ? ? ? ? root->parent->parent=right_child_ptr;

? ? ? ? ? ? }
? ? ? ? ? ? root->parent=right_child_ptr;

? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? return false;
? ? }
? ? template
? ? void? rb_tree::levelOrder() const {
? ? ? ? rb_ptr root =head->parent;
? ? ? ? queue q;
? ? ? ? if(head->parent !=head){
? ? ? ? ? ? q.push(root);
? ? ? ? ? ? while(!q.empty()){
? ? ? ? ? ? ? ? rb_ptr visit_ptr = q.front();
? ? ? ? ? ? ? ? cout<<"data: "<data<<"? color: "<<((visit_ptr->color==0)?"RED":"BLACK")<? ? ? ? ? ? ? ? if(visit_ptr->left)
? ? ? ? ? ? ? ? ? ? q.push(visit_ptr->left);
? ? ? ? ? ? ? ? if(visit_ptr->right)
? ? ? ? ? ? ? ? ? ? q.push(visit_ptr->right);
? ? ? ? ? ? ? ? q.pop();
? ? ? ? ? ? }
? ? ? ? }
? ? }
? ? template
? ? void rb_tree:: _preOrder(rb_ptr root) const{
? ? ? ? if(root){
? ? ? ? ? cout<<"data: "<data<<"? color: "

? ? ? ? ? ? <<((root->color==0)?"RED":"BLACK")<? ? ? ? ? ? _preOrder(root->left);
? ? ? ? ? ? _preOrder(root->right);
? ? ? ? }
? ? }
? ? template
? ? void rb_tree:: preOrder() const{
? ? ? ? _preOrder(head->parent);
? ? }
}

//#include "rbtree.cpp"
#endif /* SRC_RBTREE_H_ */