算法导论-红黑树C++实现 - c++编程基础

ack[top]=p.right;
level[top][0]=n+width;
level[top][1]=2;

}
if(p.left!=NULL)
{
top++;
stack[top]=p.left;
level[top][0]=n+width;
level[top][1]=1;
}
}
}
}
//左旋节点node
bool LeftRotate(BRTreeNode* node)
{
BRTreeNode*y;
if(node->right==nil)
{
cout<<"can't left rotate!"< return 0;
}
y=node->right;
node->right=y->left;
if(y->left!=nil)
{
y->left->parent=node;
}
y->parent=node->parent;
if(node->parent==nil)
{
root=y;
}
else if(node->parent->left==node)
{
node->parent->left=y;
}
else
{
node->parent->right=y;
}
y->left=node;
node->parent=y;
return 1;
}
//右旋节点
bool RightRotate(BRTreeNode* node)
{
if(node->left==nil)
{
cout<<"can't rightrotate!"< return 0;
}
BRTreeNode* x;
x=node->left;
node->left=x->right;
if(x->right!=nil)
{
x->right->parent=node;
}
x->parent=node->parent;
if(node->parent==nil)
{
root=x;
}
else if(node->parent->left==node)
{
node->parent->left=x;
}
else
{

node->parent->right=x;
}
node->parent=x;
x->right=node;
return 1;
}
void Insert(int num)
{
BRTreeNode* node=new BRTreeNode(num,1);
node->left=nil;
node->right=nil;
node->parent=nil;
BRTreeNode* p=root,*q=nil;
if(root==nil)
{
node->color=0;
root=node;
root->left=root->right=root->parent=nil;
return ;
}
while(p!=nil)
{
if(p->key==num)
{
cout< return ;
}
else if(p->key>num)
{
q=p;
p=p->left;
}
else
{
q=p;
p=p->right;
}
}
if(q->key>num)
{
q->left=node;
node->parent=q;
}
else
{
q->right=node;
node->parent=q;
}
RBInsertAdjust(node);
}
void RBInsertAdjust(BRTreeNode* node)
{
BRTreeNode* y;
while(node->parent->color==1)
{
if(node->parent==node->parent->parent->left)
{
y=node->parent->parent->right;
if(y->color==1)
{
node->parent->color=0;
y->color=0;
y->parent->color=1;
node=node->parent->parent;
}
//此时y的颜色是黑色
else
{
//第二种情况
if(node==node->parent->right)
{
no

算法导论-红黑树C++实现 (三)