Я ввел несколько цифр на красно-черное дерево. (41; 38; 31; 12; 19; 8) после удаления 8 и 12 (1-й скриншот) он перешел в тип второго скриншота. Я не могу понять, почему этот 31 стал красным. Пожалуйста, помогите мне с этим? Не могли бы вы упомянуть случай, связанный с этим. Спасибо !
Если вы проверите объяснение алгоритма удаления в Википедии, вы можете сопоставить их имена узлов своему дереву следующим образом:
M = 0012, черный узел для удаления
C = NIL-лист ниже 0012 (NIL всегда считаются черными)
В статье говорится о вашем фактическом случае:
Сложный случай - это когда и M, и C черные. [...] Мы начинаем с замены M его дочерним элементом C. [...] Мы изменим метку этого дочернего элемента 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 содержит одинаковое количество черных узлов.
Этот инвариант был бы нарушен, если бы вышеуказанная замена цвета была опущена.
0031остался черным, удовлетворяло бы дерево ограничениям? (Ответ: нет.) Почему бы и нет? - person ruakh schedule 08.12.2018