}
if(z->left==nil||z->right==nil)
{
y=z;
}
else
y=InorderSuccessor(z);
if(y->left!=nil)
x=y->left;
else
x=y->right;
x->parent=y->parent;
if(x->parent==nil)
root=x;
else if(y=y->parent->left)
y->parent->left=x;
else
y->parent->right=x;
if(y!=z)
{
z->key=y->key;
}
if(y->color==0)
{
RBTreeFixup(x);
}
return 1;
}
void RBTreeFixup(BRTreeNode* x)
{
BRTreeNode*w;
while(x!=root&&x->color==0)
{
if(x==x->parent->left)
{
w=x->parent->right;
if(w->color==1)
{
w->color=0;
x->parent->color=1;
LeftRotate(x->parent);
w=x->parent->right;
}
if(w->left->color==0&&w->right->color==0)
{
w->color=1;
x=x->parent;
}
else
{
if(w->right->color==0)
{
w->color=1;
RightRotate(w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=0;
w->right->color=0;
LeftRotate(x->parent);
x=root;
}
}
else
{
w=x->parent->left;
{
w->color=0;
x->parent->color=1;
RightRotate(x->parent);
w=x->parent->left;
}
if(w->right->color==0&&w->left->color==0)
{
w->color=1;
x=x->parent;
}
else
{
if(w->left->color==0)
{
w->color=1;
LeftRotate(w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=0;
w->left->color=0;
RightRotate(x->parent);
x=root;
}
}
}
x->color=0;
}
};
#endif // BRTREE_H_INCLUDED
#ifndef BRTREE_H_INCLUDED
#define BRTREE_H_INCLUDED
#define maxSize 30
#define maxWidth 30
#include"BRTreeNode.h"
class BRTree
{
private:
BRTreeNode* root;
BRTreeNode* nil;
public:
BRTree():nil(new BRTreeNode())
{
nil->color=0;
nil->key=-1;
nil->left=nil->right=nil->parent=NULL;
root=nil;
}
~BRTree()
{
MakeEmpty(root);
delete nil;
}
//清空以node为根节点的树
void MakeEmpty(BRTreeNode*node)
{
if(node!=nil)
{
MakeEmpty(node->left);
MakeEmpty(node->right);
delete node;
}
}
int Getkey(BRTreeNode* node