Вставка Red Black Tree: зачем делать узлы красными при вставке?

В Red Black Tree Properties не содержится никакого правила для цвета узла вставки, как всегда мы вставляем узлы красного цвета.

Если мы вставим узел черного цвета, он нарушает какие-либо свойства (любое правило из 4)?

Источник

2 ответа

Решение

Ага! Предположим, у вас есть один узел в вашем дереве:

    5 (black)

Теперь вставьте новый черный узел в дерево:

    5 (black)
     \
      9 (black)

Теперь инвариант, что каждый корень-нулевой путь в дереве имеет одинаковое количество черных узлов, нарушается, поскольку путь от левого корневого узла имеет один черный узел, а у путей из корневого справа - два.

Надеюсь это поможет!

Источник

Вы, кажется, задаете два вопроса

1) Зачем делать узлы красными при вставке (в заголовке)?

2) нарушает ли вставка как черный цвет какие-либо свойства?

Вы также, похоже, ошибочно полагаете, что ответ "да" для 2) является автоматическим обоснованием для 1).

Это не так! Вставка узла в красный цвет также может нарушить одно из свойств дерева RB. Например, если вы делаете красный узел дочерним по отношению к другому красному узлу, вы только что нарушили свойство, что красные узлы могут иметь только черных дочерних элементов.

Причина, по которой он становится красным, состоит в том, что "проще" исправить свойства дочернего узла (путем поворота и перерисовки родителя / дедушки и бабушки), чем пытаться исправить свойства длины пути. Возможно, другая причина в том, что это то, что авторы придумали.

Также возможно исправить дерево, вставив черный узел и не перекрашивая красный. Возможно, никто еще не задумывался об этом.

Источник
Другие вопросы по тегам