红黑树满足1下性质:
*1.节点非红即黑。
*2.根节点是黑色。
*3.所有NULL结点称为叶子节点,且认为色彩为黑。
*4.所有红节点的子节点都为黑色。
*5.从任1节点到其叶子节点的所有路径上都包括相同数目的黑节点。
因此红黑树插入的所有节点都是红的,然后根据规则进行调剂
再删除的时候,也需要将有两个孩子的节点进行前后的替换,然后删除,最后调剂
/*****************************************************************************
* 红黑色:
* 或是1颗空树,或是1颗2叉树,满足以下性质
*1.节点非红即黑。
*2.根节点是黑色。
*3.所有NULL结点称为叶子节点,且认为色彩为黑。
*4.所有红节点的子节点都为黑色。
*5.从任1节点到其叶子节点的所有路径上都包括相同数目的黑节点。
*
*红黑树具有较好的自平衡性,性能优于BST,但是低于AVL,在linux中用于内存管理
*
*因此红黑色在插入节点必定是红节点,由于黑节点会破坏性质5,但是会出现以下问题
*****************************************************************************/
#ifndef REDBLACK_H_
#define REDBLACK_H_
#include <iostream>
#define BLACK 1
#define RED 0
using namespace std;
/**************每一个节点的信息***********************/
class Node
{
public:
int value;/******节点寄存的值******/
bool color;/***节点色彩****/
Node *leftTree, *rightTree, *parent;/*******左右子树,父节点**********/
Node(void):color(RED),leftTree(NULL),rightTree(NULL),parent(NULL),value(0) {}
/**********获得祖父节点************/
Node* grandparent(void)
{
return parent==NULL?NULL:parent->parent;
}
/***********获得叔节点***********/
Node* uncle(void)
{
if (grandparent() == NULL)
{
return NULL;
}
if (parent == grandparent()->rightTree)
return grandparent()->leftTree;
else
return grandparent()->rightTree;
}
/******获得兄弟节点*********/
Node* sibling(void)
{
return parent->leftTree==this?parent->rightTree:parent->leftTree;
}
};
/******************红黑色类*********************/
class RedBlackTree
{
private:
void rotate_right(Node *p);/*******右旋********/
void rotate_left(Node *p);/*******左旋********/
void inorder(Node *p);/********先序遍历***********/
string outputColor(bool color);/********输出色彩**********/
Node* getSmallestChild(Node *p);/**********获得最小子树***********/
bool delete_child(Node *p, int data);/*********删除子树************/
void delete_one_child(Node *p);/*********删除1个孩子************/
void delete_case(Node *p);/*********删除情况************/
void insert(Node *p, int data);/********插入*********/
void insert_case(Node *p);/********插入情况***********/
void DeleteTree(Node *p);/********删除树***********/
bool find_data(Node* p,int data);/*********查找节点************/
public:
RedBlackTree(void);/********构造接口***********/
~RedBlackTree();/********烧毁接口***********/
void InOrderTraverse();/********遍历接口***********/
void Insert(int x);/********插入接口***********/
bool Delete(int data);/********删除接口***********/
bool Find(int data);/********查找接口***********/
private:
Node *root, *NIL;
};
//*******************************************************************
// Method: rotate_right
// FullName: RedBlackTree::rotate_right
// Access: private
// Returns: void
// Qualifier: 右旋转
// Parameter: Node * p
//*******************************************************************
//*******************GP********************GP************************
//******************/********************/*************************
//****************FA****x****************P****X**********************
//***************/******--->***********/***************************
//*************P*****U*****************L**FA*************************
//************/*************************Y**************************
//***********L***Y***************************U***********************
//*******************************************************************
void RedBlackTree::rotate_right(Node *p)
{
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->rightTree;
fa->leftTree = y;
if (y != NIL)
y->parent = fa;
p->rightTree = fa;
fa->parent = p;
if (root == fa)
root = p;
p->parent = gp;
if (gp != NULL)/******判读父节点与祖父节点的关系,从而修复关系********/
{
if (gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
//*******************************************************************
// Method: rotate_left
// FullName: RedBlackTree::rotate_left
// Access: private
// Returns: void
// Qualifier: 左旋
// Parameter: Node * p
//*******************************************************************
//*******************************************************************
//*******************GP********************GP************************
//******************/********************/*************************
//****************FA****x****************P****X**********************
//***************/******--->***********/***************************
//**************X****P*****************FA**R*************************
//******************/****************/*****************************
//*****************Y***R*************X****Y**************************
//*******************************************************************
void RedBlackTree::rotate_left(Node *p)
{
if (p->parent == NULL)
{
root = p;
return;
}
Node *gp = p->grandparent();
Node *fa = p->parent;
Node *y = p->leftTree;
fa->rightTree = y;
if (y != NIL)
y->parent = fa;
p->leftTree = fa;
fa->parent = p;
if (root == fa)
root = p;
p->parent = gp;
if (gp != NULL)/******判读父节点与祖父节点的关系,从而修复关系********/
{
if (gp->leftTree == fa)
gp->leftTree = p;
else
gp->rightTree = p;
}
}
//************************************
// Method: inorder
// FullName: RedBlackTree::inorder
// Access: private
// Returns: void
// Qualifier: 中序遍历节点
// Parameter: Node * p
//************************************
void RedBlackTree::inorder(Node *p)
{
if (p == NIL)
return;
if (p->leftTree)
inorder(p->leftTree);
cout << p->value << " ";
if (p->rightTree)
inorder(p->rightTree);
}
//************************************
// Method: outputColor
// FullName: RedBlackTree::outputColor
// Access: private
// Returns: std::string
// Qualifier: 输出色彩
// Parameter: bool color
//************************************
string RedBlackTree::outputColor(bool color)
{
return color ? "BLACK" : "RED";
}
//************************************
// Method: getSmallestChild
// FullName: RedBlackTree::getSmallestChild
// Access: private
// Returns: Node*
// Qualifier: 获得最小孩子
// Parameter: Node * p
//************************************
Node* RedBlackTree::getSmallestChild(Node* p)
{
if (p->leftTree == NIL)
return p;
return getSmallestChild(p->leftTree);
}
//************************************
// Method: delete_child
// FullName: RedBlackTree::delete_child
// Access: private
// Returns: bool
// Qualifier: 删除孩子
// Parameter: Node * p
// Parameter: int data
//************************************
bool RedBlackTree::delete_child(Node *p, int data)
{
if (p->value > data)/*****在左侧*******/
{
if (p->leftTree == NIL)/*****没有找到元素*******/
{
return false;
}
return delete_child(p->leftTree, data);
}
else if (p->value < data)/*****在右侧*******/
{
if (p->rightTree == NIL)
{
return false;
}
return delete_child(p->rightTree, data);
}
else if (p->value == data)/*****找到*******/
{
if (p->rightTree == NIL)
{/******如果节点右子树空了,这样最多只有1个孩子,否则需要替换节点,再进入单节点删除*******/
delete_one_child(p);
return true;
}
Node *smallest = getSmallestChild(p->rightTree);/*找打后继节点,然后交换,后删除*/
swap(p->value, smallest->value);
delete_one_child(smallest);
return true;
}
return false;
}
//************************************
// Method: delete_one_child
// FullName: RedBlackTree::delete_one_child
// Access: private
// Returns: void
// Qualifier: 删除最多只有1个孩子的节点
// Parameter: Node * p
//************************************
void RedBlackTree::delete_one_child(Node *p)
{
Node *child = p->leftTree == NIL ? p->rightTree : p->leftTree;
if (p->parent == NULL && p->leftTree == NIL && p->rightTree == NIL)
{/****只有根节点*******/
p = NULL;
root = p;
return;
}
if (p->parent == NULL)/****根节点****/
{
delete p;
child->parent = NULL;/**重置根节点*/
root = child;
root->color = BLACK;
return;
}
if (p->parent->leftTree == p)/**替换掉该节点**/
{
p->parent->leftTree = child;
}
else
{
p->parent->rightTree = child;
}
child->parent = p->parent;
if (p->color == BLACK)
{/*****如果删除的节点是黑节点,需要调剂树,如果是红节点,那末子树也是不冲突的,则直接删除便可********/
if (child->color == RED)/****子树是红节点的话,则直接退换成黑节点,并且性质没有遭到破坏****/
{
child->color = BLACK;
}
else/*******否则需要调剂性质*******/
delete_case(child);
}
delete p;
}
//************************************
// Method: delete_case
// FullName: RedBlackTree::delete_case
// Access: private
// Returns: void
// Qualifier: 删除情况
// Parameter: Node * p
//************************************
void RedBlackTree::delete_case(Node *p)
{
if (p->parent == NULL)/***为根节点,直接染黑色***/
{
p->color = BLACK;
return;
}
if (p->sibling()->color == RED)/****情况1:如果兄弟节点是红色的话,调剂色彩后旋转,最后依照2,3,4处理****/
{
p->parent->color = RED;
p->sibling()->color = BLACK;
if (p == p->parent->leftTree)
rotate_left(p->sibling());
else
rotate_right(p->sibling());
}
if (p->parent->color == BLACK && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
{/****情况2.1:父节点黑色,兄弟节点是黑色,而且兄弟有两个黑色的子节点,这样可以染红兄弟,然后调剂父节点****/
p->sibling()->color = RED;
delete_case(p->parent);
}
else if (p->parent->color == RED && p->sibling()->color == BLACK
&& p->sibling()->leftTree->color == BLACK && p->sibling()->rightTree->color == BLACK)
{/****情况2.2:如果兄弟节点是红色的话,而且兄弟有两个黑色的子节点,这样可以染红兄弟,然后调剂父节点****/
p->sibling()->color = RED;
p->parent->color = BLACK;
}
else
{
if (p->sibling()->color == BLACK)
{/****情况3.1:如果兄弟节点是黑色的话,而且兄弟左孩子红色,右孩子黑色,交换兄弟节点和左孩子色彩变成第第4种情况****/
if (p == p->parent->leftTree && p->sibling()->leftTree->color == RED
&& p->sibling()->rightTree->color == BLACK)
{
p->sibling()->color = RED;
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling()->leftTree);
}
else if (p == p->parent->rightTree && p->sibling()->leftTree->color == BLACK
&& p->sibling()->rightTree->color == RED)
{/****情况3.2:如果兄弟节点是黑色的话,而且兄弟左孩子黑色,右孩子红色****/
p->sibling()->color = RED;
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling()->rightTree);
}
}
/****情况4:如果兄弟节点是黑色的话,而且兄弟对面节点孩子为红色****/
p->sibling()->color = p->parent->color;
p->parent->color = BLACK;
if (p == p->parent->leftTree)
{/****情况4.1:节点为左子树,那末兄弟右孩子为红色****/
p->sibling()->rightTree->color = BLACK;
rotate_left(p->sibling());
}
else
{/****情况4.2:节点为右子树,那末兄弟左孩子为红色****/
p->sibling()->leftTree->color = BLACK;
rotate_right(p->sibling());
}
}
}
//************************************
// Method: insert
// FullName: RedBlackTree::insert
// Access: private
// Returns: void
// Qualifier: 插入数据
// Parameter: Node * p
// Parameter: int data
//************************************
void RedBlackTree::insert(Node *p, int data)
{
if (p->value >= data)/**插入数据比data小(含等于)的话,进入左侧,否则进入右侧**/
{
if (p->leftTree != NIL)
insert(p->leftTree, data);
else
{
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->leftTree = tmp;
insert_case(tmp);
}
}
else
{
if (p->rightTree != NIL)
insert(p->rightTree, data);
else
{
Node *tmp = new Node();
tmp->value = data;
tmp->leftTree = tmp->rightTree = NIL;
tmp->parent = p;
p->rightTree = tmp;
insert_case(tmp);
}
}
}
//************************************
// Method: insert_case
// FullName: RedBlackTree::insert_case
// Access: private
// Returns: void
// Qualifier: 插入情况,1共有5种情况
// Parameter: Node * p
//************************************
void RedBlackTree::insert_case(Node *p)
{
if (p->parent == NULL)/****情形1:直接染黑色*****/
{
root = p;
p->color = BLACK;
return;
}
if (p->parent->color == RED)
{
if (p->uncle()->color == RED)
{/*情形3:父节点和叔节点都是红色,将祖父,父、叔全换色,最后递归处理祖父节点*/
p->parent->color = p->uncle()->color = BLACK;
p->grandparent()->color = RED;
insert_case(p->grandparent());
}
else/*父节点和叔节点都是红色,叔叔节点黑色*/
{
if (p->parent->rightTree == p && p->grandparent()->leftTree == p->parent)
{/**情形4:p是父节点的右孩子,父节点是祖父节点的左孩子**/
/********这类情况先调剂父节点,使得其和祖父和父亲均在1条线上,注意,这里旋转后p成新的父节点********/
rotate_left(p);
rotate_right(p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
}
else if (p->parent->leftTree == p && p->grandparent()->rightTree == p->parent)
{/**情形5:p是父节点的左孩子,父节点是祖父节点的右孩子**/
/********这类情况先调剂父节点,使得其和祖父和父亲均在1条线上,注意,这里旋转后p成新的父节点********/
rotate_right(p);
rotate_left(p);
p->color = BLACK;
p->leftTree->color = p->rightTree->color = RED;
}
else if (p->parent->leftTree == p && p->grandparent()->leftTree == p->parent)
{/**情形5.2:p是父节点的右孩子,父节点是祖父节点的左孩子**/
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_right(p->parent);
}
else if (p->parent->rightTree == p && p->grandparent()->rightTree == p->parent)
{/**情形4.2:p是父节点的右孩子,父节点是祖父节点的左孩子**/
p->parent->color = BLACK;
p->grandparent()->color = RED;
rotate_left(p->parent);
}
}
}
/*******最后斟酌case2:情况,由于父节点是黑色,所以可以直接退出********/
}
//************************************
// Method: DeleteTree
// FullName: RedBlackTree::DeleteTree
// Access: private
// Returns: void
// Qualifier: 删除树
// Parameter: Node * p
//************************************
void RedBlackTree::DeleteTree(Node *p)
{
if (!p || p == NIL)
{
return;
}
DeleteTree(p->leftTree);
DeleteTree(p->rightTree);
delete p;
}
//************************************
// Method: find_data
// FullName: RedBlackTree::find_data
// Access: public
// Returns: bool
// Qualifier: 查找值
// Parameter: int data
//************************************
bool RedBlackTree::find_data(Node* p,int data)
{
if(p==NULL||p==NIL)
return false;
if(data>p->value)
return find_data(p->rightTree,data);
else if(data<p->value)
return find_data(p->leftTree,data);
return true;
}
/**************************************接口部份********************************/
//************************************
// Method: RedBlackTree
// FullName: RedBlackTree::RedBlackTree
// Access: public
// Returns:
// Qualifier: 初始化
// Parameter: void
//************************************
RedBlackTree::RedBlackTree(void)
{
NIL = new Node();
NIL->color = BLACK;
root = NULL;
}
RedBlackTree::~RedBlackTree(void)
{
if (root)
DeleteTree(root);
delete NIL;
}
//************************************
// Method: inorder
// FullName: RedBlackTree::inorder
// Access: public
// Returns: void
// Qualifier: 遍历节点
// Parameter: void
//************************************
void RedBlackTree::InOrderTraverse(void)
{
if (root == NULL)
return;
inorder(root);
cout << endl;
}
//************************************
// Method: insert
// FullName: RedBlackTree::insert
// Access: public
// Returns: void
// Qualifier: 插入值
// Parameter: int x
//************************************
void RedBlackTree::Insert(int x)
{
if (root == NULL)
{
root = new Node();
root->color = BLACK;
root->leftTree = root->rightTree = NIL;
root->value = x;
}
else
{
insert(root, x);
}
}
//************************************
// Method: delete_value
// FullName: RedBlackTree::delete_value
// Access: public
// Returns: bool
// Qualifier: 删除值
// Parameter: int data
//************************************
bool RedBlackTree::Delete(int data)
{
return delete_child(root, data);
}
//************************************
// Method: Find
// FullName: RedBlackTree::Find
// Access: public
// Returns: bool
// Qualifier: 查找值
// Parameter: int data
//************************************
bool RedBlackTree::Find(int data)
{
return find_data(root,data);
}
#endif /*redblaock.h*/