红黑树插入操作的C++实现 - linux编程基础

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(datavalue)
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 outQueue;
outQueue.push_back(root);
int level=0;
while(outQueue.size()>0)
{
vector tempQueue=outQueue;
outQueue.clear();
os<<"[ level= "<for(int i=0;i{
TreeNode* node=tempQueue[i];
TreeNode* parent=node->parent;
Color color=tempQueue[i]->getColor();
int value=node->getValue();
cout<<" [ "<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 ="<value;
if(node==parent->lchild)
cout<<" left ";
else
cout<<" right ";
}
else
cout<<" root";
cout<<" ] ";
}
os<<" }"<level++;
tempQueue.clear();
}
return os;
}
/*
检查树是否符合红黑树的五条规定
同时还检查父子节点之间的数值大小是否符合二叉查找树的规定
父子节点之间的指针是否指向正确
*/
bool Tree::check_tree()
{
vector nodes;
/*
保存所有的指向叶子节点的节点，用于计算比较从此节点往上是否符合规则5
由于NIL是一个共享的节点，所以这里用指向NIL的节点来验证规则5
*/
vector leafs;
bool result=true;
if(!root)
return result;
nodes.push_back(root);
int i=0;
while(result&&i{
TreeNode* p=nodes[i];
if(p->lchild==TreeNode::NIL) //如果左子树为叶子
{
leafs.push_back(p);
/*如果右子树不为叶子。右子树也为叶子的情况在上一条语句中已经包含*/
if(p->rchild!=TreeNode::NIL)
{
nodes.push_back(p->rchild)

红黑树插入操作的C++实现(二)