120
правок
Изменения
м
ЗаметимОграничение на принадлежность внутренним узлам вызвано тем, что у листьев детей нет, а если у корня <tex>B_k</tex> удалить самого левого сына, то <tex>B_k</tex> превратится в <tex>B_{k-1}</tex>. Ранг тонкого дерева равен количеству детей корня.
Отдельно должен храниться односвязный список корней, корень с минимальным ключом должне быть первым в этом списке.
Также в вершине можно хранить любую дополнительную информациюДля работы с ''тонкой кучей'' достаточно иметь ссылку на ее первый корень.
Нет описания правки
}}
{{Утверждение|id=about_thin_tree_rank. |statement=Ранг тонкого дерева равен количеству детей его корня.}} Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим: * <tex>Degree(x)</tex> {{---}} количество детей узла <tex>x</tex>; .* <tex>Rank(x)</tex> {{---}} ранг соответствующего узла в биномиальном дереве <tex>B_k</tex>.
== Свойства тонкого дерева ==
{{Утверждение
|id=about_thin_tree.
|statement=Тонкое дерево обладает следующими свойтсвамисвойствами:
# Для любого узла <tex>x</tex> либо <tex>Degree(x)=Rank(x)</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен (полный); либо <tex>Degree(x)=Rank(x)-1</tex>, в этом случае говорим, что узел <tex>x</tex> помечен (неполный).
# Корень не помечен (полный).
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
# Узел <tex>x</tex> помечен тогда и только тогда, если когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1 , и он не имеет детей.
}}
== Представление тонкой кучи ==
''Тонкую кучу'' можно представить как односвязный список корней ''тонких деревьев'', причем корень с минимальным ключом должен быть первым в списке. Поскольку при работе с ''тонкой кучей'' ссылка на родителя требуется только у самого левого ее его ребенка, можно хранить ее вместо ссылки на левого сына брата этой вершины.
Таким образом, для эффективной работы ''тонкой кучи'' необходимы следующие поля узла:
*<tex>child</tex> {{---}} указатель на самого левого ребенка узла;
*<tex>right</tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;
*<tex>left</tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это первый корень списка;
*<tex>rank</tex> {{---}} ранг узла (количество дочерних узлов данного узла).
Для ускорения проверки на ''тонкость'' (''thinness'') можно отдельно хранить помеченность вершины.
Также в вершине можно хранить любую дополнительную информацию.
== Операции над тонкой кучей ==
Рассмотрим операции, которые можно производить над ''тонкой кучей''. Время работы указано в таблице:
{| border="1"
|-align="center"
|}
Многие операции над ''тонкой кучей '' выполняются так же, как и над ''фиббоначиевой''.
Для амортизационного анализа применим метод потенциалов.
|statement=Определённый таким образом потенциал обладает свойствами:
# <tex>\Phi \geqslant 0</tex>.
# Для пустой ''тонкой кучи '' <tex>\Phi = 0</tex>.
}}
=== makeHeap ===
Возвращаем ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
Стоимость <tex>O(1)</tex>.
=== meld ===
Сливаем корневые списки, ставя первым тот список, где у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
Стоимость <tex>O(1)</tex>.
# Cливаем детей с корневым списком.
# Объединяем, пока возможно, тонкие деревья одного ранга.
Это можно сделать, например, с помощью вспомогательного массива размером <tex>O(D(n))</tex>, в <tex>i</tex>-ой ячейке которго которого хранится корень тонкого дерева <tex>T_i</tex> ранга <tex>i</tex>.
Изначально массив пуст, а мы добавляем в него все деревья нашего корневого списка.
При добавлении нового дерева мы, пока возможноесли дерево такого ранга уже есть в массиве, связываем его с деревом такого же ранга, а затем существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
Пусть мы сделали <tex>ls</tex> ''связывающих шагов'' (''linking steps'') во время добавления в массив.
Мы удалили корень из списка за <tex>O(1)</tex>, затем за <tex>O(D(n))</tex> нормализовали детей корня и добавили в корневой список, а затем далее за <tex>O(D(n))+O(ls)</tex> получили новый корневой список, в котором за <tex>O(D(n))</tex> нашли минимальный корень и подвесили список за него.
Получили фактическую стоимость <tex>O(D(n))+O(ls)</tex>. С другой стороны, при добавлении детей в список мы увеличили потенциал <tex>\Phi</tex> не более чем на <tex>O(D(n))</tex>, а каждый связывающий шаг уменьшает наш потенциал <tex>\Phi</tex> на <tex>1</tex>.
