In RB_REMOVE, when the removed node has non-NULL children, we have to replace the removed node with either its predecessor or successor. We always choose the successor. When the successor is the right child of the removed node, this may immediately produce imbalance, and that imbalance is handled with a rotation in RB_REMOVE_COLOR that moves the successor from its new position with a left child back down where it started, without a left child.
To avoid unnecessary rotation, and an invocation of RB_AUGMENT for a successor node that hasn't actually changed, this change has the implementation choose between the predecessor and successor in order to preserve balance, for those cases where the right child of the removed node is its successor.