HomeFreeBSD

In concluding RB_REMOVE_COLOR, in the case when the sibling of the

Description

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 is 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.

Reviewed by: markj
Differential Revision: https://reviews.freebsd.org/D25335

Details

Provenance
dougmAuthored on
Reviewer
markj
Differential Revision
D25335: Drop unneeded rotation from RB_REMOVE_COLOR
Parents
rS362449: Clarify some language. Favor primary where both master and primary were
Branches
Unknown
Tags
Unknown