Блог

Главная - Вопросы по программированию - Вопрос о красно-черном дереве

Вопрос о красно-черном дереве

#algorithm #tree #red-black-tree

#алгоритм #дерево #красно-черное дерево

Вопрос:

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

У меня есть следующее дерево, я указал здесь только цвета. Конечные узлы игнорируются.

                    B
           R               B
       B       B       R       R 
     R   R       R

Ответ №1:

Да, узел может иметь дочерние элементы разного цвета. Посмотрите, например, на диаграмму в самом верху статьи MathWorld о R-B деревьях; вы можете убедиться, что она удовлетворяет всем требованиям, предъявляемым к R-B дереву, и один из ее узлов имеет дочерние элементы разных цветов. Как, если уж на то пошло, и приведенный вами пример.

Комментарии:

1. Спасибо за быстрый ответ. Я столкнулся с этим при тестировании моей структуры данных и хотел подтвердить, что это возможно.

Ответ №2:

Вот хорошая статья о черных для чтения деревьях в контексте изучения структуры данных в Haskell.

http://scientopia.org/blogs/goodmath/2009/11/30/advanced-haskell-data-structures-red-black-trees/

Критерии дерева R-B, которые он дает, довольно ясны. Дочерние элементы красного узла должны быть черными, но дочерние элементы черного узла не указаны. Важным моментом является то, что все пути от данного узла к листьям под ним должны иметь одинаковое количество черных узлов. Глядя на ваше дерево, каждый путь вниз от корня имеет 1 черный узел (2, если считать корень), так что все в порядке.