LeftRotate(node);
}
//第三种情况
node->parent->color=0;
node->parent->parent->color=1;
RightRotate(node->parent->parent);
}
}
else
{
y=node->parent->parent->left;
if(y->color==1)
{
node->parent->color=0;
y->color=0;
y->parent->color=1;
node=node->parent->parent;
}
else
{
if(node==node->parent->left)
{
node=node->parent;
RightRotate(node);
}
node->parent->color=0;
node->parent->parent->color=1;
LeftRotate(node->parent->parent);
}
}
}
root->color=0;
}
BRTreeNode* Search(int num)
{
BRTreeNode* p=root;
while(p!=nil)
{
if(p->key==num)
{
return p;
}
else if(p->key>num)
{
p=p->left;
}
else
{
p=p->right;
}
}
cout<<"there is no "<
}
//获取以node节点为根节点的树的最小元素，并返回该最小值
int Minnum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->left!=nil)
{
p=p->left;
}
return p->key;
}
//获取以node节点为根节点的树的最da元素，并返回该最da值
int Maxnum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->right!=nil)
p=p->right;
}
return p->key;
}
//获取以node节点为根节点的树的最小元素，并返回该节点
BRTreeNode* MinNum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->left!=nil)
{
p=p->left;
}
return p;
}
//获取以node节点为根节点的树的最大元素
BRTreeNode* MaxNum(BRTreeNode*node)
{
BRTreeNode*p=node;
while(p->right!=nil)
{
p=p->right;
}
return p;
}
BRTreeNode*InorderSuccessor(BRTreeNode*node)
{
if(node->right!=nil)
{
return MinNum(node->right);
}
else
{
BRTreeNode*p=GetParent(node);
while(p&&node==p->right)
{
node=p;
p=GetParent(node);
}
return p;
}
}
//中序遍历的前趋
BRTreeNode*InordePredecessor(BRTreeNode*node)
{
if(node->left!=nil)
{
return MaxNum(node->left);
}
else
{
BRTreeNode*p=GetParent(node);
while(p&&node==p->left)
{
node=p;
p=GetParent(node);
}
return p;
}
}
bool Delete(int num)
{
BRTreeNode*z,*y,*x;
//寻找key值为num的节点p
z=Search(num);
//如果没有该节点则返回0
if(z==nil)
{
r