Red Black Tree in C++, deletion algorithm [closed]
From "Introduction to alghorithms, 2nd edition": Implementation of the deletion algorithm in C++ looks like this:
template<class Tree_T, class Node_T>
void rb_delete(Tree_T* t,Node_T* z)
{
Node_T* y = nullptr;
Node_T* x = nullptr;
if (!get_left(z) || !get_right(z))
{
y = z;
}
else
{
//y = rb_successor(z);
y = rb_predecessor(z);
}
if (get_left(y))
{
x = get_left(y);
}
else
{
x = get_right(y);
}
set_parent(x,get_parent(y));
if (!get_parent(y))
{
set_root(t,x);
}
else
{
if (y == get_left(get_parent(y)))
{
set_left(get_parent(y),x);
}
else
{
set_right(get_parent(y),x);
}
}
if (y != z)
{
set_key(z,get_key(y));
set_value(z,get_value(y));
}
if(get_color>(y) == Black)
{
rb_delete_fixup(t,x);
}
}
template<class Tree_T, class Node_T>
void rb_delete_fixup(Tree_T* t, Node_T* x)
{
while (x != get_root(t) && get_color(x) == Black)
{
//more code here but it never gets executed!
}
set_color(x,Black);
}
The problem is that when I create tree in order 1,2,3,4,5,6,7,8 the tree looks like this:
If I were to delete root from this tree I'm getting:
void rb_delete(Tree_T* t,Node_T* z)//t is the tree, z is a node with key 4
{
Node_T* y = nullptr;
Node_T* x = nullptr;
if (!get_lef开发者_运维知识库t(z) || !get_right(z))//z has left && right so this will get skipped
{
y = z;
}
else
{
//y = rb_successor(z);
y = rb_predecessor(z);//to here where y will be set to 3
}
if (get_left(y))//this is false
{
x = get_left(y);
}
else//so we skipping to this place
{
x = get_right(y);//and here x goes set to nullptr!
}
set_parent(x,get_parent(y));//cannot set, x == nullptr
if (!get_parent(y))//this is false
{
set_root(t,x);
}
else
{
if (y == get_left(get_parent(y)))//this is false
{
set_left(get_parent(y),x);
}
else
{
set_right(get_parent(y),x);//so here we set right of parent y to nullptr
}
}
if (y != z)//this is true
{
set_key(z,get_key(y));
set_value(z,get_value(y));
}
if(get_color>(y) == Black)//this is true aswell
{
rb_delete_fixup(t,x);//here we attempting to do fixup but x == nullptr!
}
}
//So we are going into rb_delete_fixup
template<class Tree_T, class Node_T>
void rb_delete_fixup(Tree_T* t, Node_T* x)//x == nullptr
{
while (x != get_root(t) && get_color(x) == Black)//this will get skipped because x == nullptr so no code will be executed within while loop!
{
//more code here but it never gets executed!
}
set_color(x,Black);//here x which is nullptr will get colored to Black
}
This code obviously doesn't work, bear in mind it is implemented line by line from book mentioned at the beginning of this question.
Could anyone help me and explain to me how shall I fix it?
精彩评论