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

Question

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

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

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

Answer 1

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

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

Answer 2

Это возможно. Но для поддержания условия 5 иногда вам может понадобиться окрасить узел RED.

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

a 
/\ 
b c 

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

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