Как узнать, является ли дерево окрашенным

Question

Я не могу понять, почему следующее дерево RB не окрашено.

Я думал, что единственным требованием было:

Путь от корня до самого дальнего листа не более чем в два раза длиннее пути от корня до ближайшего листа.

Но на изображении вы видите, что самый короткий путь (оранжевый) равен 2, а самый длинный путь (синий) - 4, что означает, что он должен быть окрашен в соответствии с приведенным выше правилом.

Answer 1

Действительно, это красочно. Красное черное дерево всегда должно следовать этим правилам:

• Каждый узел имеет красный или черный цвет.

• Корень дерева всегда черный.

• Нет двух смежных красных узлов (красный узел не может иметь красного родителя или красного ребенка).

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

Дерево не может быть окрашено, потому что и 2-синий, и 3-синий должны быть красного цвета, что нарушает правило 3.

Путь от корня до самого дальнего листа не более чем в два раза Пока путь от корня до ближайшего листа.

Это не совсем требование, а общее свойство RB Trees. Пропустив математическое доказательство, рассмотрим дерево, в котором на одной ветви у вас есть только черные узлы, а на другой ветви чередуются красные и черные узлы. В этой ситуации у вас максимальный дисбаланс, если это не так, по крайней мере одно из вышеуказанных правил нарушено.

Теоретически у вас есть 2 типа высоты в дереве РБ:

• Высота черного , которая является общей для всех веток вашего дерева (в противном случае нарушается правило 4)
• «Общая высота» (это не существующий термин), который представляет собой максимальное количество красных узлов + черных узлов на одном пути от корня до NIL.

Answer 2

Я думаю, вам не нужно считать NIL. Таким образом, самый короткий путь равен 1, а самый длинный путь равен 3, что означает, что указанное вами правило применимо, поскольку двойной путь от корня до ближайшего листа равен 1 * 2, а 3 (фактический самый длинный путь) больше => нет раскраска.