红黑树插入操作的C++实现
红黑树插入操作的C++实现
红黑树是具有如下顺序属性的二叉查找树
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;
}
|
评论暂时关闭