当前位置: 动力学知识库 > 问答 > 编程问答 >

Red Black Tree in C++, deletion algorithm

问题描述:

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_left(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?

分享给朋友:
您可能感兴趣的文章:
随机阅读: