红黑树删除操作的疑问
我照着<算法导论>上关于红黑树删除操作的伪代码编写了一个红黑树删除操作,但是测试的时候发现一直出现指针为空操作的异常,算法是完全照着书上的,不知道是书上的算法有问题还是怎么回事.以下是红黑树的相关代码:#define and &&
#define or ||
#define NIL NULL
class Node
{
public:
int key;
Node* left; //左孩子
Node* right;//右孩子
Node* parent; //父节点
// int item;
int color;
Node()
{
left=NIL;
right=NIL;
parent=NIL;
color=-1;
}
Node(int key)
{
this->key=key;
left=NIL;
right=NIL;
parent=NIL;
color=-1;
}
};
class RedBlackTree
{
public:
Node *root;
Node* Successor(Node* node);
void Insert(Node* node);
void LeftRotate(Node* node);
void RightRotate(Node* node);
Node* Delete(Node* node);
void InsertFixUp(Node* node);
void DeleteFixUp(Node *node);
Node* Search(int key);
int getNodeNum()
{
return totalNodes;
}
RedBlackTree()
{
root=NIL;
}
};
树的相关操作Node* RedBlackTree::Successor(Node* node)
{
Node* x=node;
Node* y;
if(node->right!=NIL)
return Minimum(node->right);
y=x->parent;
while(y!=NIL and x==y->right)
{
x=y;
y=y->parent;
}
return y;
}
Node* RedBlackTree::Search(int key)
{
Node* x=root;
while((x!=NIL) and (x->key!=key))
{
if(key<x->key)
x=x->left;
else
x=x->right;
}
return x;
}
void RedBlackTree::LeftRotate(Node* node)
{
Node* x=node;
Node* y=node->right;
if(x->right!=NIL and y!=NIL)
x->right=y->left;//Turn y's left subtree into x's subtree
if(y!=NIL and y->left!=NIL)
y->left->parent=x;
if(y!=NIL)
y->parent=x->parent;//Link x's parent to y
if(x->parent==NIL)
root=y;
else
{
if(x==x->parent->left)
x->parent->left=y;
else x->parent->right=y;
}
y->left=x;
x->parent=y;
}
void RedBlackTree::RightRotate(Node* node)
{
Node* y=node;
Node* x=node->left;
y->left=x->right;
if(x->right!=NIL)
x->right->parent=y;
x->parent=y->parent;
if(y->parent==NIL)
root=x;
else
{
if(y==y->parent->left)
y->parent->left=x;
else y->parent->right=x;
}
x->right=y;
y->parent=x;
}
void RedBlackTree::Insert(Node* node)
{
Node* x=root;
Node* y=NIL;
while(x!=NIL)
{
y=x;
if(node->key<x->key)
x=x->left;
else x=x->right;
}
node->parent=y;
if(y==NIL)
root=node;
else
{
if(node->key<y->key)
y->left=node;
else y->right=node;
}
node->left=NIL;
node->right=NIL;
node->color=RED;
InsertFixUp(node);
totalNodes++;
}
void RedBlackTree::InsertFixUp(Node* node)
{
Node* z=node;
Node* y;
while(z->parent!=NIL and z->parent->color==RED)
{
if(z->parent==z->parent->parent->left)
{
y=z->parent->parent->right;
if(y!=NIL and y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else
{
if(z==z->parent->right)
{
z=z->parent;
LeftRotate(z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
RightRotate(z->parent->parent);
}
}
else
{
y=z->parent->parent->left;
if(y!=NIL and y->color==RED)
{
z->parent->color=BLACK;
y->color=BLACK;
z->parent->parent->color=RED;
z=z->parent->parent;
}
else
{
if(z==z->parent->left)
{
z=z->parent;
RightRotate(z);
}
z->parent->color=BLACK;
z->parent->parent->color=RED;
LeftRotate(z->parent->parent);
}
}
}
root->color=BLACK;
}
Node* RedBlackTree::Delete(Node* node)
{
Node* z=node;
Node* x;
Node* y;
if(z->left==NIL or z->right==NIL)
y=z;
else y=Successor(z);
if(y->left!=NIL)
x=y->left;
else x=y->right;
if(x!=NIL)
x->parent=y->parent;
if(y->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;
z->color=y->color;
//copy y's satellite data into z
}
if(y->color==BLACK)
DeleteFixUp(x);
totalNodes--;
return y;
}
void RedBlackTree::DeleteFixUp(Node* node)
{
Node* x=node;
Node* w;
while(x!=root and x->color==BLACK)
{
if(x==x->parent->left)
{
w=x->parent->right;
if(w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
LeftRotate(x->parent);
w=x->parent->right;
}
if(w->left->color==BLACK and w->right->color==BLACK)
{
w->color=RED;
x=x->parent;
}
else
{
if(w->right->color==BLACK)
{
w->left->color=BLACK;
w->color=RED;
RightRotate(w);
w=x->parent->right;
}
w->color=x->parent->color;
x->parent->color=BLACK;
w->right->color=BLACK;
LeftRotate(x->parent);
x=root;
}
}
else
{
w=x->parent->left;
if(w->color==RED)
{
w->color=BLACK;
x->parent->color=RED;
RightRotate(x->parent);
w=x->parent->left;
}
if(w->right->color==BLACK and w->left->color==BLACK)
{
w->color=RED;
x=x->parent;
}
else
{
if(w->left->color==BLACK)
{
w->right->color=BLACK;
w->color=RED;
LeftRotate(w);
w=x->parent->left;
}
w->color=x->parent->color;
x->parent->color=BLACK;
w->left->color=BLACK;
RightRotate(x->parent);
x=root;
}
}
x->color=BLACK;
}
}
测试函数:void main()
{
Node *node;
Node *x;
RedBlackTree t;
//BinarySearchTree t;
int key[]={5,3,8,2,4,7,9,1,6,10};
int i,j,k;
int n=sizeof(key)/sizeof(*key);
for(i=0;i<n;i++)
{
node=new Node(key);
t.Insert(node);
}
printf("root->key=%d\n",t.root->key);
printf("\n");//i=0;
for(i=0;i<n;i++)
{
x=t.Delete(t.Search(i+1));
printf("delete key=%d\n",x->key);
printf("root->key=%d\n",t.root->key);
printf("\n\n");
}
}
每次运行循环进行了两次就出现了异常,通过Debug发现在第2轮循环DeleteFixUp操作中node为空指针,由此出现了异常.以上的DeleteFixUp是照着书上编的, 估计伪代码也有问题, 不知道如何改正 昨天在测试Insert操作时也出现了同样的情况,但是今天重新运行昨天的代码却又没有问题了.但是Delete操作一直有问题. 以下是仅能正常输出的部分,由于输出树形结构的代码很长,所以这里给出的代码仅输出根结点
页:
[1]