我已经为 RBT 实现了删除功能(基于 Cormen),它看起来很有效,但是预先测试删除 + 打印树给了我错误的答案。我花了几个小时寻找可能出了什么问题,但找不到任何东西......
这是按顺序打印树的功能:
void print_out(rbt_node *root, rbt_node *NIL)
{
if(root != NIL)
{
printf("%d %s ", root->key, root->data.c_str());
if(root->color == BLACK)
printf("black ");
else
printf("red ");
if(root->parent != NIL)
printf("%d ",root->parent->key);
else
printf("- ");
if(root->left != NIL)
printf("%d ",root->left->key);
else
printf("- ");
if(root->right != NIL)
printf("%d ",root->right->key);
else
printf("- ");
printf("\n");
print_out(root->left, NIL);
if(root->right != NIL)
{
print_out(root->right, NIL);
}
}
}
以下是要删除的其他重要内容:
rbt_node *NIL = new rbt_node;
NIL->color = BLACK;
NIL->left = NIL->parent = NIL->right = NIL;
rbt_node *tree_minimum(rbt_node *node, rbt_node *NIL)
{
while(node->left != NIL)
node = node->left;
return node;
}
rbt_node *tree_succesor(rbt_node *node, rbt_node *NIL)
{
if(node->right != NIL)
return tree_minimum(node->right, NIL);
rbt_node *helper = node->parent;
while(helper != NIL && node == helper->right)
{
node = helper;
helper = helper->parent;
}
return helper;
}
void delete_fixup(rbt_node *&root, rbt_node *&target, rbt_node *NIL)
{
rbt_node *helper = NIL;
while(target != root && target->color == BLACK)
{
if(target == target->parent->left)
{
helper = target->parent->right;
if(helper->color == RED)
{
helper->color = BLACK;
target->parent->color = RED;
left_rotate(root, target->parent, NIL);
helper = target->parent->right;
}
if(helper->left->color == BLACK && helper->right->color == BLACK)
{
helper->color = RED;
target = target->parent;
}
else if(helper->right->color== BLACK)
{
helper->left->color = BLACK;
helper->color = RED;
right_rotate(root, helper, NIL);
helper = target->parent->right;
}
else
{
helper->color = target->parent->color;
target->parent->color = BLACK;
helper->right->color = BLACK;
left_rotate(root, target->parent, NIL);
target = root;
}
}
else
{
helper = target->parent->left;
if(helper->color == RED)
{
helper->color = BLACK;
target->parent->color = RED;
right_rotate(root, target->parent, NIL);
helper = target->parent->left;
}
if(helper->right->color == BLACK && helper->left->color == BLACK)
{
helper->color = RED;
target = target->parent;
}
else if(helper->left->color== BLACK)
{
helper->right->color = BLACK;
helper->color = RED;
left_rotate(root, helper, NIL);
helper = target->parent->left;
}
else
{
helper->color = target->parent->color;
target->parent->color = BLACK;
helper->left->color = BLACK;
right_rotate(root, target->parent, NIL);
target = root;
}
}
}
target->color = BLACK;
}
void rbt_delete(rbt_node *&root, int key, rbt_node *NIL)
{
rbt_node *victim = to_delete(root, key, NIL);
if(victim != NIL)
{
rbt_node *help_one = NIL;
rbt_node *help_two = NIL;
if(victim->left == NIL || victim->right == NIL)
help_one = victim;
else
help_one = tree_succesor(victim, NIL);
if(help_one->left != NIL)
help_two = help_one->left;
else
help_two = help_one->right;
help_two->parent = help_one->parent;
if(help_one->parent == NIL)
root = help_two;
else if(help_one == help_one->parent->left)
help_one->parent->left = help_two;
else
help_two->parent->right = help_two;
if(help_one != victim)
{
victim->key = help_one->key;
victim->data = help_one->data;
}
if(help_one->color == BLACK)
delete_fixup(root, help_two, NIL);
}
root->color = BLACK;
}