Red Black Tree ~ 1 Child Deletes

Question

Возможно ли, чтобы красный родительский узел имел только один черный дочерний узел? Я играю с симулятором Red/Black Tree онлайн, и я не могу получить случай, чтобы это произошло.

Причина прошу это я считаю, у меня есть нет необходимости, если в моем коде ...

if (temp_node->color == BLACK && node->color == RED) 
{ 
    node->color = BLACK; 
    global_violation = false; 
} 

Спасибо за любую обратную связь !!

Answer 1

Нет, это невозможно.

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

Если у вас есть красный узел x с одним черным ребенком y, у него не может быть другого красного ребенка (так как это нарушает красный/черный инвариант, что красные узлы не могут иметь красных детей).

Это означает, что путь через x на пропавший ребенок будет проходить через по крайней мере один меньше черному узлу, чем путь через x, затем y, а затем с дерева оттуда, ломая красную/черное дерево инварианты.