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:

enter image description here

After delete of 2:

enter image description here

I understand RB Trees but I'm not quite sure what you are asking, can you give an example in diagram form? — Justin
<i.imgur.com/nnyh8IX.png> This is the tree before deleting a node. The node to be deleted is 2. <i.imgur.com/EnMULSy.png> This is after the delete and delete-fixup function. If I try walking through the pseudocode, I can't see why this shouldn't happen, but the resulting tree is an illegal red black tree, as the paths from the root to the null node don't contain the same amount of black nodes. — Boz0r
I think your misunderstanding the "deleting a node with no children". All leafs have null value (and cannot be deleted technically) and are black. You are deleting node 2 which does have children (two null children). See my answer below. — Justin

Justin Justin · Accepted Answer · 2013-11-17T12:58:22

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.

Red Black Search Trees

1 Answers