Red Black Search Trees

Question

I'm implementing a red-black search tree as described Introduction To Algorithms 3rd Edition.

I have a problem where the tree doesn't get properly recolored after deleting a node with no children. On page 324 is described the RB-DELETE function. If a node is a leaf node, it's child pointers point to a special null node.

What I don't understand is, that when this function is run on a leaf node, it assigns the null node to x, then replaces the node with the subtree of null, thus altering the parent pointer of null. In the end, it runs the fixup method on null.

Shouldn't editing the null node be illegal? And what am I not understanding, why doesn't it work?

Before delete of 2:

After delete of 2:

Answer 1

Looking at the two PNGs you posted something doesn't add up.

In your picture, a number of things have changed after deleting 2. The root has been change from 5 to 7 and 7 went from red to black.

The original.. leaf (null) node's aren't shown.

            5(B)
    3(R)             7(R)
2(B)    4(B)     6(B)        9(B)
                         8(R)    11(R)

When you delete node 2:

The sub-tree goes from...

    3(R)
   /   \
2(B)    4(B) 

to...

       3(R)
      /   \
null(B)    4(B) 

After removing 2:

            5(B)
    3(R)             7(R)
        4(B)     6(B)        9(B)
                         8(R)    11(R)

Case 4 of delete: Sibling and Sibling's children are black, but Parent is red. In this case, we simply exchange the colors of Sibling (to red) and Parent (to black).

After re-coloring sibling and parent:

            5(B)
    3(B)             7(R)
        4(R)     6(B)        9(B)
                         8(R)    11(R)

As you can see, simply removing a node with two leaf-node children is a simple re-coloring and doesn't change the shape of the tree.