Мне было интересно, всегда ли можно добавить пустые листовые вершины в сбалансированное дерево AVL, а затем раскрасить все вершины так, чтобы было правильно структурированное красно-черное дерево?
Добавление пустых листовых вершин в дерево AVL?
Ответы (1)
Очень хороший вопрос. Я думаю, что да. Следующее не является полным доказательством, но я думаю, что оно указывает на то, что ответ может быть верным. Наихудшим сбалансированным деревом AVL является дерево Фибоначчи, определяемое следующим образом:
fib(0) = EmptyLeaf()
fib(1) = Node(fib(0), fib(0))
fib(n) = Node(Fib(n-1), Fib(n-2))
Это с точностью до перестановки левого и правого дочерних элементов уникальное дерево глубины n с наименьшим количеством узлов. См. например
В таком дереве вы решаете рекурсивно раскрасить узел по следующим правилам.
1 - Root is black
2 - for each node n if parent_color is black and n is left child
then color = red
else color = black
Тогда это красно-черное дерево. См., например (спасибо этому апплету):
Также внизу этой страницы есть примечание, указывающее на то же самое.
person
hivert
schedule
22.02.2014
