Change Details

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.

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.

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.