开发者

Red Black Tree in C++, deletion algorithm [closed]

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance. Closed 11 years ago.

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:

Red Black Tree in C++, deletion algorithm [closed]

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?

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜