) We begin by replacing M with its child C. We will call (or "label"—that is, "relabel") this child (in its new position) N, and its sibling (its new parent's other child) S. (S was previously the sibling of M.)In the diagrams below, we will also use P for N's new parent (M's old parent), SL for S's left child, and SR for S's right child (S cannot be a leaf because if M and C were black, then P's one subtree which included M counted two black-height and thus P's other subtree which includes S must also count two black-height, which cannot be the case if S is a leaf node).
)Мы начнем с замены узла M своим потомком C. Будем называть этот потомок (в своем новом положении) N, а его «брата» (другого потомка его нового предка) — S. (До этого S был «братом» M.)На рисунках ниже мы также будем использовать обозначение P для нового предка N (старого предка M), SL для левого потомка S и SR для правого потомка S (S не может быть листовым узлом, так как если N по нашему предположению является чёрным, то поддерево P, которое содержит N, чёрной высоты два и поэтому другое поддерево P, которое содержит S должно быть также чёрной высоты два, что не может быть в случае, когда S — лист).