Drop unneeded rotation from RB_REMOVE_COLOR

[dougm]

Summary

In concluding RB_REMOVE_COLOR, in the case when the sibling of the root of the too-short tree is black and at least one of the children of that sibling are red, either one or two rotations finish the rebalancing. In the case when both of the children are red, the current implementation uses two rotations where only one is necessary. This change removes that extra rotation, and in that case also removes a needless black-to-red-to-black recoloring.

Any fan of dichromatic trees is welcome to review.

[dougm]

A little test program. Enter a positive number to insert into the tree and a negative number to remove its inverse from the tree.

treetest.c1 KBDownload

If you want to see the effect of this patch, try entering this sequence into the test program

6 4 8 2 5 7 9 10 -10 -9 -8 -7

and you'll see that the patch changes the resulting tree in the last operation, but doesn't violate red-black properties.

[dougm]

Drop redundant assignments.

[markj]

If I understand correctly, with the original code, the intermediate state of the tree prior to the second rotation after removing 7 is:

B6:17
    B5:11
        B4:6
            R2:2

[dougm]

In D25335#559767, @markj wrote:

If I understand correctly, with the original code, the intermediate state of the tree prior to the second rotation after removing 7 is:

B6:17
    B5:11
        B4:6
            R2:2

That's right.