Структуры данных и модели вычислений
приведены примеры тонких деревьев;
На рис. 8. 1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево , внизу — два полученных из тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.
Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.
Рис. 8.1.
Тонкая куча — это кучеобразно нагруженный тонкий лес.
Заметим, что в тонкой куче могут встречаться тонкие деревья одинакового ранга, в то время как в биномиальной куче все деревья должны иметь попарно различные ранги.
Утверждение. Для любого натурального числа существует тонкий лес, который содержит ровно элементов и состоит из тонких деревьев попарно различных рангов.
Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.
Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.
Теорема [22]
В тонкой куче из элементов , где — золотое сечение.
Доказательство. Сначала покажем, что узел ранга
в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи, определяемое соотношениями , , для .
Действительно, пусть — минимально возможное число узлов, включая самого себя, в тонком дереве ранга . По свойствам и
тонкого дерева получаем следующие соотношения:
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что для любых . Неравенство
хорошо известно.
Теперь убедимся в том, что максимально возможный ранг
тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа . Действительно, выберем в тонкой куче дерево максимального ранга. Пусть — количество вершин в этом дереве, тогда .
Отсюда следует, что .
