c++ - C ++の赤黒木、削除アルゴリズム

Question

「アルゴリズム入門、第2版」から：C++での削除アルゴリズムの実装は次のようになります。

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);
}

問題は、1、2、3、4、5、6、7、8の順序でツリーを作成すると、ツリーが次のようになることです。

このツリーからルートを削除すると、次のようになります。

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
        }

このコードは明らかに機能しません。この質問の冒頭で述べた本から1行ずつ実装されていることに注意してください。

誰かが私を助けて、どうやってそれを修正するのか説明してもらえますか？