Ребята, я пытаюсь реализовать алгоритм удаления для дерева Red Black, и у меня возникают проблемы с пониманием третьей строки этого алгоритма (из книги "Введение в алгоритмы", второе издание):
1, если слева [z] = ноль [T] или справа [z] = ноль [T]
2 тогда y ← z
3 еще y ← ДЕРЕВО УСПЕХА (z)
4 если осталось [y] ≠ nil [T]
5 затем x ← влево [y]
6 иначе x ← вправо [у]
7 р [х] ← р [у]
8, если p [y] = ноль [T]
9 затем корень [T] ← x
Еще 10, если у = левый [р [у]]
11 затем налево [p [y]] ← x
Еще 12 прав [p [y]] ← x
13 если y 3 ≠ z
14 затем клавиша [z] ← клавиша [y]
15 скопируйте спутниковые данные y в z
16 если цвет [у] = ЧЕРНЫЙ
17 затем RB-DELETE-FIXUP (T, x)
18 возврат у
Прежде всего, нигде в этой книге не объясняется, как должен выглядеть TREE-SUCCESSOR (без алгоритма для этого), но я нашел эту страницу : и если я подпишу этот алгоритм, то 11 2,1,7,5,8,14,15,4, а затем попробуйте удалить 7, он находит предшественника , но если я пытаюсь удалить 11, он находит преемника . И это то, что я не могу понять. Почему иногда требуется предшественник, а иногда преемник? Какие критерии учитываются при принятии этого решения? Цвет узла?
Спасибо.
P.S. Я также не совсем понимаю, что написано в строке № 13. Значит ли это, что у у три цвета (ни черный, ни красный) или что-то еще?