В Red Black Tree Properties не содержится никакого правила для цвета узла вставки, как всегда мы добавляем узлы красного цвета.Вставка красного черного дерева: зачем делать узлы красными при вставке?
Если мы вставляем узел черного цвета, он нарушает любые свойства (любое правило из 4)?
Да! Предположим, у вас есть один узел в дереве:
5 (black)
Теперь вставьте новый черный узел в дерево:
5 (black)
\
9 (black)
Теперь инвариант, что каждый корень-нуль путь в дереве имеет тот же номер черных узлов сломан, так как путь от корня слева имеет один черный узел, а пути от корня справа имеют два.
Надеюсь, это поможет!
Вы, кажется, задавая два вопроса
1) Почему делают узлы красные, когда вставленные (в названии)?
2) Вкладывается ли в черный цвет какие-либо предметы?
Вы также, кажется, ошибаетесь, что ответ «Да» для 2) является автоматическим оправданием для 1).
Это не так! Вставка узла как красного также может нарушить одно из свойств дерева RB. Например, если вы сделаете красный узел дочерним элементом другого красного узла, вы только что нарушили свойство, что красные узлы могут иметь только черные дети.
Причина, по которой это делается красным, заключается в том, что «легче» установить свойства дочернего узла (путем поворота и перерисовки родительских/бабушек и дедушек) вместо того, чтобы пытаться исправить свойства длины пути. Возможно, еще одна причина заключается в том, что авторы придумали.
Возможно, также будет возможно установить дерево, вставив черный узел и не перекрасив красный. Наверное, никто еще не подумал об этом.