红黑树C++实现
红黑树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)&¤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<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_ */
本文永久更新链接地址：
评论暂时关闭