Ответ 1
В тексте они указывают, что x также может быть Nil, т.е. когда y.right - Nil. Кажется, что Nil в этом коде также представлен node, и они не хотят оставлять свисающий указатель.
Упрощение избыточности красного черного дерева
Во введении к алгоритму Third Edition у них есть реализация псевдокода удаления красно-черного дерева. Вот оно...
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, мы не хотим, чтобы xp указывал на исходный родительский элемент, так как мы удаляем этот node из дерева. Поскольку node y будет перемещаться вверх, чтобы взять позицию z в дерево, устанавливающее xp на y в строке 13, заставляет xp указывать исходную позицию y родителя, даже если x == T.nil."
Поэтому они хотят, чтобы x родительский был y... это уже y...