Дети в красном / черном дереве?

Question

Согласно этому объяснению красного черного дерева, дерево должно иметь следующие свойства:

1. Узел красный или черный.
2. Корень черный. (Это правило иногда опускается. Поскольку корень всегда можно изменить с красного на черный, но не обязательно наоборот, это правило мало влияет на анализ.)
3. Все листья (ноль) черные. (Все листья одного цвета с корнем.)
4. Оба потомка каждого красного узла черные.
5. Каждый простой путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов.

Что мешает кому-то сделать каждый узел черным?

Answer 1

Это возможно. Но для поддержания условия 5 иногда вам может потребоваться покрасить узел в КРАСНЫЙ.

Например, рассмотрим следующий пример.

  a
 / \
b   c

Здесь все узлы могут быть ЧЕРНЫМИ

Теперь, если вы хотите вставить новый узел, какой цвет вы выберете? RED. если вы выберете черный цвет, условие 5 не будет выполнено. Таким образом, вы можете продолжать вставлять КРАСНЫЕ узлы, если ни одно из условий (1-4) не нарушено

Answer 2

Последнее правило, которое вы процитировали: "Каждый простой путь от данного узла к любому из его дочерних листьев содержит одинаковое количество черных узлов".

Если все узлы черные, то путь от корня к любому листу должен содержать одинаковое количество узлов. Другими словами, все листья находятся на одной глубине - так что это возможно только для идеального бинарного дерева.