Red Black Tree вопрос

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

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

                   B
           R               B
       B       B       R       R 
     R   R       R

algorithm tree red-black-tree
person smahesh    schedule 12.04.2011    source источник

Ответы (2)


arrow_upward
1
arrow_downward

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

person Gareth McCaughan    schedule 12.04.2011
comment
Спасибо вам за быстрый ответ. Я столкнулся с этим при тестировании своей структуры данных и хотел подтвердить, что это возможно. - person smahesh; 12.04.2011

arrow_upward
1
arrow_downward

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

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

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

person Andrew Cooper    schedule 12.04.2011