Красный Черное дерево вопрос

Question

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

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

                   B
           R               B
       B       B       R       R 
     R   R       R

Answer 1

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

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

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

Answer 2

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