红黑树C++实现

最近一直在复习面试的内容，会不断的记录相关自己看过或者写过的内容，这也是自己的收获或经历，以后查询也比较方便。红黑树的性质不说了，直接贴代码上传。/*
* rbtree.h
* 1. 每个节点是红色或者黑色
* 2. 根节点是黑色
* 3. 每个叶子节点是黑色（该叶子节点就空的节点）
* 4. 如果一个节点是红色，则它的两个子节点是黑色的
* 5.对每个节点，从该节点道其他所有后代的叶子节点的简单路径上，均包含相同数目的黑色节点
*
*/#ifndef SRC_RBTREE_H_
#define SRC_RBTREE_H_
#include<iostream>
#include<queue>using namespace std;
enum colors{ RED,BLACK};
typedef int color_type;
namespace red_black_tree{
struct rb_tree_base{
struct rb_tree_base * parent;
struct rb_tree_base * left;
struct rb_tree_base * right;
color_type color;
}; template<class T>
struct rb_tree_node:public rb_tree_base{
T data;
typedef rb_tree_node<T>* link_type;
};
template<class Value>
class rb_tree{
public:
typedef rb_tree_base* rb_ptr;
typedef typename rb_tree_node<Value>::link_type link_type;
typedef rb_tree_node<Value> tree_node;
private:
rb_ptr head;
private:
bool _right_rotate（rb_ptr root）;
bool _left_rotate（rb_ptr root）;
rb_ptr _get_node（const Value& e） const;
bool _insert_fix_up（rb_ptr current_ptr）; bool _erase_fix_up（rb_ptr current_ptr,rb_ptr parent_ptr）; void _preOrder（rb_ptr root） const; rb_ptr _successor（rb_ptr current_ptr） const;
public:
rb_tree（）;
~rb_tree（）;
bool insert（const Value &e）;
bool empty（） const;
bool erase（const Value &e）;
rb_ptr find（const Value &e）;
void levelOrder（） const;
void preOrder（） const;
};
template<class Value>
rb_tree<Value>::rb_tree（） {
head = new tree_node（）;
head->left=head;
head->right=head;
head->parent=head; head->color=BLACK;
} template<class Value>
rb_tree<Value>::~rb_tree（） {
} template<class Value>
bool rb_tree<Value>::insert（const Value& e） {
rb_ptr insert_ptr =_get_node（e）;
if（head->parent ==head）{
head->parent=insert_ptr;
insert_ptr->parent=head;
insert_ptr->color=BLACK;
return true;
}
rb_ptr root_ptr=head->parent;
rb_ptr root_remember=nullptr;
while（root_ptr）{
root_remember=root_ptr;
if（link_type（insert_ptr）->data<=link_type（root_ptr）->data）
root_ptr=root_ptr->left;
else
root_ptr=root_ptr->right;
}
insert_ptr->parent=root_remember;
if（link_type（insert_ptr）->data <= link_type（root_remember）->data ）
root_remember->left=insert_ptr;
else if（link_type（insert_ptr）->data >link_type（ root_remember）->data）
root_remember->right=insert_ptr;
bool ret =_insert_fix_up（insert_ptr）;
return ret;
}
template<class Value>
bool rb_tree<Value>::empty（） const { return head->parent==head;
} template<class Value>
bool rb_tree<Value>::erase（const Value& e） { rb_ptr erase_ptr = find（e）; if（！erase_ptr） return false; int erase_color =erase_ptr->color; rb_ptr fix_up_ptr=nullptr; rb_ptr fix_up_parent_ptr=nullptr; if（erase_ptr）{ if（！erase_ptr->left&&！erase_ptr->right）{//叶子节点 if（erase_ptr==erase_ptr->parent->left）{ erase_ptr->parent->left=nullptr; fix_up_parent_ptr= erase_ptr->parent; } if（erase_ptr==erase_ptr->parent->right）{ erase_ptr->parent->right=nullptr; fix_up_parent_ptr= erase_ptr->parent; } if（erase_ptr==head->parent）{ head->parent=head; fix_up_parent_ptr=head; } erase_color =erase_ptr->color; delete erase_ptr; }else if（erase_ptr->right）{ rb_ptr successor_ptr =_successor（erase_ptr）;//left一定为空 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<class Value>
typename rb_tree<Value>::rb_ptr rb_tree<Value>::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<class Value>
bool rb_tree<Value>:: _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）; }
}else{
rb_ptr uncle_ptr=parent_ptr->parent->left;
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->left）{//uncle_ptr->color 是BLACK,或者uncle_ptr为空
current_ptr=parent_ptr;
_right_rotate（current_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<class Value> bool rb_tree<Value>::_erase_fix_up（rb_ptr current_ptr,rb_ptr parent_ptr）{ while（（！current_ptr||current_ptr->color==BLACK）&&current_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<class Value> typename rb_tree<Value>::rb_ptr rb_tree<Value>::_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_ptr->left; } 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<class Value>
typename rb_tree<Value>::rb_ptr rb_tree<Value>::_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<class Value>
bool rb_tree<Value>::_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<class Value>
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<class Value>
void rb_tree<Value>::levelOrder（） const {
rb_ptr root =head->parent;
queue<rb_ptr> q;
if（head->parent ！=head）{
q.push（root）;
while（！q.empty（））{
rb_ptr visit_ptr = q.front（）;
cout<<"data: "<<link_type（visit_ptr）->data<<" color: "<<（（visit_ptr->color==0）？"RED":"BLACK"）<<endl;
if（visit_ptr->left）
q.push（visit_ptr->left）;
if（visit_ptr->right）
q.push（visit_ptr->right）;
q.pop（）;
}
}
}
template<class Value>
void rb_tree<Value>:: _preOrder（rb_ptr root） const{
if（root）{
cout<<"data: "<<link_type（root）->data<<" color: " <<（（root->color==0）？"RED":"BLACK"）<<endl;
_preOrder（root->left）;
_preOrder（root->right）;
}
}
template<class Value>
void rb_tree<Value>:: preOrder（） const{
_preOrder（head->parent）;
}
}
//#include "rbtree.cpp"
#endif /* SRC_RBTREE_H_ */本文永久更新链接地址：http://www.linuxidc.com/Linux/2015-09/123379.htm