Структуры данных и модели вычислений


Основные определения - часть 2


На рис. 8.1 приведены примеры тонких деревьев; числа рядом с узлами обозначают их ранги. Вверху изображено биномиальное дерево , внизу — два полученных из тонких дерева ранга три. Стрелки указывают на помеченные узлы. Заметим, что биномиальное дерево является тонким деревом, у которого все узлы не помечены.

Тонкий лес — это набор тонких деревьев, ранги которых не обязательно попарно различны.


Рис. 8.1. 

Тонкая куча — это кучеобразно нагруженный тонкий лес.

Заметим, что в тонкой куче могут встречаться тонкие деревья одинакового ранга, в то время как в биномиальной куче все деревья должны иметь попарно различные ранги.

Утверждение. Для любого натурального числа существует тонкий лес, который содержит ровно элементов и состоит из тонких деревьев попарно различных рангов.

Действительно, любой биномиальный лес является тонким, а для биномиального леса рассматриваемое утверждение справедливо.

Пусть — максимально возможный ранг узла в тонкой куче, содержащей элементов.

Теорема [22]

В тонкой куче из элементов , где — золотое сечение.

Доказательство. Сначала покажем, что узел ранга

в тонком дереве имеет не менее потомков, включая самого себя, где — -е число Фибоначчи, определяемое соотношениями , , для .

Действительно, пусть — минимально возможное число узлов, включая самого себя, в тонком дереве ранга . По свойствам и

тонкого дерева получаем следующие соотношения:

Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что для любых . Неравенство

хорошо известно.

Теперь убедимся в том, что максимально возможный ранг

тонкого дерева в тонкой куче, содержащей элементов, не превосходит числа . Действительно, выберем в тонкой куче дерево максимального ранга. Пусть — количество вершин в этом дереве, тогда .

Отсюда следует, что .




Начало  Назад  Вперед