Red Black Tree in C++, deletion algorithm
<p>From "Introduction to alghorithms, 2nd edition": Implementation of deletion algorithm in C++ looks like this:  </p>

<pre><code>template&lt;class Tree_T, class Node_T&gt;
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&gt;(y) == Black)
    {
        rb_delete_fixup(t,x);
    }
}

template&lt;class Tree_T, class Node_T&gt;
void rb_delete_fixup(Tree_T* t, Node_T* x)
{
    while (x != get_root(t) &amp;&amp; get_color(x) == Black)
    {
        //more code here but it never gets executed!
    }
    set_color(x,Black);
}
</code></pre>

<p>The problem is that when I create tree in order 1,2,3,4,5,6,7,8 
the tree looks like this<img src="http://i.stack.imgur.com/NVXqd.png" alt="enter image description here">
If I were to delete root from this tree I'm getting:  </p>

<pre><code>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 &amp;&amp; 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&gt;(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&lt;class Tree_T, class Node_T&gt;
        void rb_delete_fixup(Tree_T* t, Node_T* x)//x == nullptr
        {
            while (x != get_root(t) &amp;&amp; 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
        }
</code></pre>

<p>This code obviously doesn't work, bear in mind it is implemented line by line from book mentioned at the beginning of this question.<br>
Could anyone help me and explain to me how shall I fix it?</p>
