Если вы посмотрите объяснение алгоритма удаления в Википедии , вы можете отобразить их имена узлов в ваше дерево следующим образом:
M = 0012,черный узел для удаления
C = лист NIL ниже 0012 (NIL всегда считаются черными)
Далее в статье говорится о вашем фактическом случае:
Сложный случай, когда оба M и C являются черными.[...] Мы начинаем с замены M его дочерним элементом C .[...] Мы будем relbel этот ребенок C (в новой позиции) N и его брат (другой ребенок его нового родителя) S [...] мы также будем использовать P для нового родителя N , S L для S левый ребенок и S R для S правый ребенок
Так что теперь мы имеемпосле удаления, но перед перекрашиванием:
P = 0019 (красный)
N = лист NIL, левый потомок 0019
S = 0031, правый потомок 0019
В описании указаны несколько случаев, и рассматриваемый случай представляет собойследующий:
Случай 4: дети S и S черные, а P красные.В этом случае мы просто меняем цвета S и P .
Объясняется причина этого цветового обмена:
Это не влияет на количество черных узлов на путях, проходящих через S , но этодобавляет один к числу черных узлов на путях, проходящих через N , компенсируя удаленный черный узел на этих путях.
Напомним, что в красно-черных деревьях этот инвариант должен поддерживаться ( свойство 5 ):
Каждый путь от данного узла к любому из егонисходящие узлы NIL содержат такое же количество черных узлов.
Этот инвариант был бы нарушен, если бы вышеприведенный обмен цвета был опущен.