Во введении к Алгоритмам третьего издания в них реализована псевдокодная реализация удаления красно-черного дерева. Вот оно ...
RB-DELETE(T, z)
y = z
y-original-color = y.color
if z.left == T.nil
x = z.right
RB-TRANSPLANT(T, z, z.right)
elseif z.right == T.nil
x = z.left
RB-TRANSPLANT(T, z, z.left)
else
y = TREE-MINIMUM(z.right)
y-original-color = y.color
x = y.right
if y.p == z
x.p = y // <--------- why????
else
RB-TRANSPLANT(T, y, y.right)
y.right = z.right
y.right.p = y
RB-TRANSPLANT(T, z, y)
y.left = z.left
y.left.p = y
y.color = z.color
if y-original-color == BLACK
RB-DELETE-FIXUP(T, x)
TREE-MINIMUM просто находит наименьшее значение в дереве, RB-TRANSPLANT получает родительский элемент второго параметра и указывает на третий параметр, а родительский элемент третьего параметра является родительским для второго параметра.
Моим комментарием они проверяют, является ли y.p значением z, и если да, то установите x.p в значение y. Но x уже y.right, так что это все равно, что сказать y.right.p = y, а y.right.p уже y! Почему они это делают?
Вот их объяснение ...
«Однако, когда исходным родителем y является z, мы не хотим, чтобы x.p указывал на исходного родителя y, так как мы удаляем этот узел из дерева. Поскольку узел y будет двигаться вверх, чтобы занять позицию z в дереве, установка x.p в y в строке 13 заставляет x.p указывать на исходную позицию родителя y, даже если x == T.nil. ”
Итак, они хотят, чтобы родительский элемент x был y ... это уже y ...