Page MenuHomeFreeBSD

Drop unneeded rotation from RB_REMOVE_COLOR
ClosedPublic

Authored by dougm on Jun 18 2020, 3:45 AM.

Details

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.

Diff Detail

Repository
rS FreeBSD src repository
Lint
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

Event Timeline

dougm requested review of this revision.Jun 18 2020, 3:45 AM
dougm created this revision.

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

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.

Drop redundant assignments.

dougm added a reviewer: danfe.

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
This revision is now accepted and ready to land.Jun 20 2020, 4:49 PM

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.