紅黑樹是具有如下順序屬性的二叉查找樹
1、每個節點要麼是紅色，要麼是黑色
2、根是黑色
3、所有葉子節點都是黑色(葉子是NIL節點)
4、每個紅色節點的兩個孩子節點都是黑色（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
5、從根節點到NIL指針的每條路徑必須包含相同數目的黑色節點
對NIL節點的理解是它不包含數據只充當樹在此結束的指示
紅黑樹的插入的時候，把新插入的節點設置成紅色，這樣不會造成某一個分子的黑色節點數目超過其它分支的數目。但這樣可能會違背性質4的要求，之所以選擇違背性質4，是因為如果某一個分支多了一個黑色的節點很難進行調整。但如果只是顏色不符合規定，則相對容易調整。
刪除操作太過復雜，未做實現。以後待定
用父代表當前插入節點的父節點，用祖父代表當前插入節點的父節點的父節點
調整的規則如下
1、父為黑，不需做額外的調整，設置好父子關系即可
2、父為紅。父為紅時，必定有祖父節點，用叔父代表其父節點的兄弟節點。
根據叔父節點顏色的不同，分兩種情況討論
2.1 叔父為紅。（將其父和叔父變黑，將其祖父變紅，然後遞歸向上檢查。）
2.2 叔父為黑。根據子在父的方向與父在祖父方向的不同，又分兩種情況
2.2.1 子在父與父在祖父的左右方向不同。
通過對子和父進行旋轉，使得變成情況2.2.2
(子在父右則左旋，子在父左則右旋)
2.2.2 子在父與父在祖父的左右方向相同。
左旋或者右旋，使得父變成祖父和當前插入節點的父節點
然後將父節點變黑，祖父節點變紅即可
(都在左，則右旋；都在右，則左旋)
下面是實現代碼
/*
紅黑樹是具有如下順序屬性的二叉查找樹
1、每個節點要麼是紅色，要麼是黑色
2、根是黑色
3、所有葉子節點都是黑色(葉子是NIL節點)
4、每個紅色節點的兩個孩子節點都是黑色（從每個葉子到根的所有路徑上不能有兩個連續的紅色節點）
4、從根節點到NIL指針的每條路徑必須包含相同數目的黑色節點
對NIL節點的理解是它不包含數據只充當樹在此結束的指示
*/
#include<iostream>
using std::ostream;
enum Color{red,black};
class TreeNode
{
private:
int value;
Color color;
TreeNode* lchild;
TreeNode* rchild;
TreeNode* parent;
/*構造一個專門的葉子節點*/
static TreeNode* NIL;
public:
TreeNode();
Color getColor()const;
TreeNode* getLeftChild()const;
TreeNode* getRightChild()const;
TreeNode* getParent() const;
int getValue() const;
private:
/*輔助函數，用來計算從當前節點開始，直到根節點總共有多少個黑色節點*/
int get_black_num();
friend class Tree;
friend ostream& operator<<(ostream&,const Tree&);
};
class Tree
{
private:
TreeNode* root;
public:
TreeNode* getRoot() const;
Tree();
void insert(int);
/*連續插入*/
void insert(int[] ,int);
void remove(int);
/*檢查樹的性質是否符合要求*/
bool check_tree();
/*給出要查詢的值。找到返回0，否則返回-1*/
//int find(int);
private:
//插入過程中的一些輔助函數
/*對數進行調整*/
void updateTree(TreeNode*);
/*左旋*/
void leftRotate(TreeNode*);
/*右旋*/
void rightRotate(TreeNode*);
friend ostream& operator<<(ostream&,const Tree&);
};
/*打印紅黑樹用*/
ostream& operator<<(ostream& os,const Tree& tree);
#include"red_black_tree.h"
#include<vector>
using std::vector;
using std::cout;
using std::endl;
/*
TreeNode類的相關定義
*/
TreeNode* TreeNode::NIL=NULL;
TreeNode::TreeNode()
{
lchild=rchild=parent=NULL;
color=black;
}
int TreeNode::get_black_num()
{
int num=0;
TreeNode* p=this;
while(p)
{
if(p->color==black)
num++;
p=p->parent;
}
return num;
}
Color TreeNode::getColor() const
{
return color;
}
TreeNode* TreeNode::getLeftChild() const
{
return lchild;
}
TreeNode* TreeNode::getRightChild() const
{
return rchild;
}
TreeNode* TreeNode::getParent() const
{
return parent;
}
int TreeNode::getValue() const
{
return value;
}
/*
Tree類的函數定義
*/
Tree::Tree()
{
root=NULL;
if(!TreeNode::NIL)
{
TreeNode::NIL=new TreeNode;
TreeNode::NIL->color=black;
TreeNode::NIL->parent=NULL;
TreeNode::NIL->lchild=NULL;
TreeNode::NIL->rchild=NULL;
}
}
TreeNode* Tree::getRoot() const
{
return root;
}
void Tree::insert(int array[] ,int num)
{
for(int i=0;i<num;i++)
{
/*
cout<<"before insert "<<array[i]<<endl;
cout<<*this<<endl;
*/
insert(array[i]);
/*
cout<<"after insert "<<array[i]<<endl;
cout<<"check tree "<<this->check_tree()<<endl;
if(!this->check_tree())
break;
cout<<*this<<endl;
cout<<"..........................."<<endl;
*/
}
}
void Tree::updateTree(TreeNode* node)
{
if(node==root)
node->color=black;
else
{
//父為黑，返回即可。父子關系的設置在insert裡面已經完成。本身節點為黑也可以直接返回即可
if(node->parent->color==black||node->color==black)
return;
else //父為紅，必有祖父節點
{
TreeNode* grand=node->parent->parent;
TreeNode* parent=node->parent;
TreeNode* uncle=grand->lchild==parent?grand->rchild:grand->lchild;
if(uncle->color==red) //叔父節點也為紅
{
uncle->color=black;
parent->color=black;
grand->color=red;
updateTree(grand);
}
else //父為紅，叔父為黑
{
enum Dir{left,right};
Dir pDir=(parent==grand->lchild)?left:right;
Dir dir=(node==parent->lchild)?left:right;
if(pDir==dir) //子父同向
{
if(dir==left)
rightRotate(parent);
else
leftRotate(parent);
parent->color=black;
grand->color=red;
}
else //子父不同向
{
if(dir==left)
rightRotate(node);
else
leftRotate(node);
/*左旋或者右旋之後，從其子節點開始調整*/
updateTree(node->lchild);
updateTree(node->rchild);
}
}
}
}
}
void Tree::insert(int data)
{
if(!root) //如果樹為空，就新建根節點
{
root=new TreeNode;
root->parent=NULL;
root->lchild=TreeNode::NIL;
root->rchild=TreeNode::NIL;
root->value=data;
root->color=black;
}
else
{
TreeNode* p=root; //用p來指向待插入節點的父節點
TreeNode* temp=data>(p->value)?p->rchild:p->lchild;
while(temp!=TreeNode::NIL)
{
p=temp;
temp=data>(p->value)?p->rchild:p->lchild;
}
/*新建一個紅節點作為p的子節點插入，然後對樹進行調整*/
TreeNode* newNode=new TreeNode;
newNode->color=red;
newNode->parent=p;
newNode->value=data;
newNode->lchild=newNode->rchild=TreeNode::NIL;
if(data<p->value)
p->lchild=newNode;
else
p->rchild=newNode;
updateTree(newNode);
}
}
/*
左旋
左旋之後的效果便是使p的父節點成為p左孩子節點。
p的左孩子節點成為p的父節點的孩子節點
*/
void Tree::leftRotate(TreeNode* node)
{
TreeNode* cur_left=node->lchild;
TreeNode* parent=node->parent;
TreeNode* grand=parent->parent;
/*代表其父節點在祖父節點的方向 1代表左，2代表右*/
if(grand)
{
int i=grand->lchild==parent?1:2;
/*對grand來說，改變的是左孩子或右孩子*/
if(i==1)
grand->lchild=node;
else
grand->rchild=node;
}
else
root=node;
/*對noe來說改變的是它的左孩子，和父節點*/
node->lchild=parent;
node->parent=grand;
/*對parent來說，改變的是父節點，右孩子*/
parent->parent=node;
parent->rchild=cur_left;
/*對cur_left來說，改變的是它的父節點*/
cur_left->parent=parent;
}
void Tree::rightRotate(TreeNode* node)
{
TreeNode* cur_right=node->rchild;
TreeNode* parent=node->parent;
TreeNode* grand=parent->parent;
/*若grand為NULL，則說明parent是root*/
if(grand)
{
/*代表其父節點在祖父節點的方向 1代表左，2代表右*/
int i=0;
i=grand->lchild==parent?1:2;
/*grand改變左子樹或者右子樹*/
if(i==1)
grand->lchild=node;
else
grand->rchild=node;
}
else
root=node;
/*node節點改變右子樹和父節點*/
node->rchild=parent;
node->parent=grand;
/*parent節點改變父節點和左子樹*/
parent->parent=node;
parent->lchild=cur_right;
/*cur_right改變父節點*/
cur_right->parent=parent;
}
/**/
void Tree::remove(int data)
{
}
/*
將一棵紅黑樹按照層次結構輸出
*/
ostream& operator<<(ostream& os,const Tree& tree)
{
TreeNode* root=tree.getRoot();
if(!root)
return os;
vector<TreeNode*> outQueue;
outQueue.push_back(root);
int level=0;
while(outQueue.size()>0)
{
vector<TreeNode*> tempQueue=outQueue;
outQueue.clear();
os<<"[ level= "<<level<<" ] { ";
for(int i=0;i<tempQueue.size();i++)
{
TreeNode* node=tempQueue[i];
TreeNode* parent=node->parent;
Color color=tempQueue[i]->getColor();
int value=node->getValue();
cout<<" [ "<<value;
if(node->getLeftChild()!=TreeNode::NIL)
outQueue.push_back(node->getLeftChild());
if(node->getRightChild()!=TreeNode::NIL)
outQueue.push_back(node->getRightChild());
if(color==red)
cout<<" red ";
else
cout<<" black ";
if(parent)
{
cout<<" parent ="<<parent->value;
if(node==parent->lchild)
cout<<" left ";
else
cout<<" right ";
}
else
cout<<" root";
cout<<" ] ";
}
os<<" }"<<endl;
level++;
tempQueue.clear();
}
return os;
}
/*
檢查樹是否符合紅黑樹的五條規定
同時還檢查父子節點之間的數值大小是否符合二叉查找樹的規定
���子節點之間的指針是否指向正確
*/
bool Tree::check_tree()
{
vector<TreeNode*> nodes;
/*
保存所有的指向葉子節點的節點，用於計算比較從此節點往上是否符合規則5
由於NIL是一個共享的節點，所以這裡用指向NIL的節點來驗證規則5
*/
vector<TreeNode*> leafs;
bool result=true;
if(!root)
return result;
nodes.push_back(root);
int i=0;
while(result&&i<nodes.size())
{
TreeNode* p=nodes[i];
if(p->lchild==TreeNode::NIL) //如果左子樹為葉子
{
leafs.push_back(p);
/*如果右子樹不為葉子。右子樹也為葉子的情況在上一條語句中已經包含*/
if(p->rchild!=TreeNode::NIL)
{
nodes.push_back(p->rchild);
result=result&&(p==p->rchild->parent);
result=result&&(p->value<=p->rchild->value);
}
}
else //如果左子樹不為葉子
{
nodes.push_back(p->lchild);
result=result&&(p==p->lchild->parent);
result=result&&(p->value>=p->lchild->value);
if(p->rchild==TreeNode::NIL) //如果右子樹為葉子
leafs.push_back(p);
else //左右子樹都不是葉子
{
result=result&&(p==p->rchild->parent);
result=result&&(p->value<=p->rchild->value);
nodes.push_back(p->rchild);
}
}
if(p->color==red)
result=result&&(p->lchild->color==black)&&(p->rchild->color==black);
i++;
}
int num=-1;
for(i=0;result&&(i<leafs.size());i++)
{
if(num==-1)
num=leafs[i]->get_black_num();
else
result=result&&(num==leafs[i]->get_black_num());
}
return result;
}
int main()
{
Tree tree;
int testData[]={15,13,2,34,53,12,21,23,52,75,46,72,19,24,87,98,1,3,31,28,123,214,512,5,78,98};
tree.insert(testData,sizeof(testData)/sizeof(int));
cout<<tree<<endl;
}
