Изменения
Нет описания правки
= Тонкое дерево =
{{Определение
|id=thin_tree_def. |definition='''Тонкое дерево''' (англ. ''thin Thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
}}
{{Утверждение
|id=about_thin_tree_rank.
|statement=Ранг тонкого дерева равен количеству детей его корня.
}}
Для любого узла <tex>x</tex> в дереве <tex>T_k</tex> обозначим:
* <tex>\mathtt{Degree(x)}</tex> {{---}} количество детей узла <tex>x</tex>.* <tex>\mathtt{Rank(x)}</tex> {{---}} ранг соответствующего узла в [[Биномиальная куча#Биномиальное дерево|биномиальном дереве]] <tex>B_k</tex>.
== Свойства тонкого дерева ==
{{Утверждение
|id=about_thin_tree.
|statement=Тонкое дерево обладает следующими свойствами:
# Для любого узла <tex>x</tex> либо <tex>\mathtt{Degree(x)=Rank(x)}</tex>, в этом случае говорим, что узел <tex>x</tex> не помечен тонкий (полныйполон); либо <tex>\mathtt{Degree(x)=Rank(x)-1}</tex>, в этом случае говорим, что узел <tex>x</tex> помечен тонкий (неполныйне полон).# Корень не помечен тонкий (полныйполон).# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>\mathtt{0,1,2,...,Degree(x)-1}</tex>.# Узел <tex>x</tex> помечен тонкий тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
}}
[[Файл:Thin_trees.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются тонкими (не имеют самого левого сына)]]<br clear="all" /> == Тонкая куча ==
{{Определение
|id=thin_forest_def. |definition='''Тонкий лес''' (англ. ''thin Thin forest'') {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
}}
{{Утверждение
|id=about_thin_forest_with_n_nodes.
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальныйлес]] лес является тонким, а для [[Биномиальная куча#Биномиальное дерево|биномиального]] леса рассматриваемое утверждение справедливо.
}}
{{Определение
|id=thin_heap_def. |definition='''Тонкая куча''' (англ. ''thin Thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный ''тонкий лес'', то есть каждое тонкое дерево удовлетворяет условиям [[Двоичная куча|кучи]].
}}
{{Теорема
|id=max_rank_th.
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phivarphi=\fracdfrac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.|proof=Сначала покажем, что узел ранга <tex>k</tex> в тонком дереве имеет не менее <tex>F_k \geqslant \Phivarphi^{k-1}</tex> потомков, включая самого себя, где <tex>F_k</tex> — <tex>k</tex>-е число Фибоначчи. Действительно, определяемое соотношениями пусть <tex>F_0=1T_k</tex>{{---}} минимально возможное число узлов, включая самого себя, в тонком дереве ранга <tex>F_1=1k</tex>, . По свойствам <tex>F_k=F_{k-2}+F_{k-1}</tex> для и <tex>k \geqslant 23</tex>.тонкого дерева получаем следующие соотношения:
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_iF_k</tex> для любых <tex>k </tex>. Неравенство <tex>F_k \geqslant 2\varphi^{k-1}</tex>[[Фибоначчиева куча#Лемма3|хорошо известно]].
Отсюда следует, что <tex>D(n)\leqslant\log_{\Phivarphi}(n)+1</tex>.
}}
== Представление тонкой кучи Структура ===== Структура узла === ''Тонкую кучу'struct' можно представить как [[Список#Односвязный список|односвязный список]] корней ''тонких деревьевNode '', причем корень с минимальным ключом должен быть первым в списке. Поскольку при работе с 'int'тонкой кучей'' ссылка на родителя требуется только у самого левого его ребенка, можно хранить ее вместо ссылки на левого брата этой вершины. key <span style="color:#008000"> // ключ</span> Таким образом, для эффективной работы '''int'тонкой кучи'' необходимы следующие поля узлаrank <span style="color:*<tex#008000">key // ранг узла</texspan> {{---}} ключ (вес) элемента;* '''Node''' child <texspan style="color:#008000">child< //tex> {{---}} указатель на самого левого ребенка узла;*<tex/span> '''Node''' right<span style="color:#008000"> //tex> {{---}} указатель на правого брата узла, либо на следующий корень, если текущий узел корень;*<tex/span> '''Node''' left<span style="color:#008000"> //tex> {{---}} указатель на левого брата узла, либо на родителя, если текущий узел самый левый, либо null, если это корень;*<tex>rank</texspan> {{---}} ранг узла (количество дочерних узлов данного узла).
Для ускорения проверки на ''тонкость'' (англ. ''thinness'') можно отдельно хранить помеченность тонкость вершины.
Также в вершине можно хранить любую дополнительную информацию.
Многие операции над ''тонкой кучей'' выполняются так же, как и над [[Фибоначчиева куча|''фиббоначиевой'']].
Для [[Амортизационный анализ|амортизационного анализа]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество ''тонких деревьев'' в куче, а <tex>m</tex> {{---}} это количество помеченных тонких вершин.
{{Утверждение
|id=about_thin_heap_potential.
|statement=Определённый таким образом потенциал обладает свойствами:
# <tex>\Phi \geqslant 0</tex>.
# Для пустой ''тонкой кучи'' <tex>\Phi = 0</tex>.
}}
Пусть <tex>\mathtt{Node}</tex> {{---}} узел тонкого дерева, а <tex>\mathtt{ThinHeap}</tex> {{---}} тонкая куча, причём <tex>\mathtt{ThinHeap}</tex> содержит ссылки на первый и последний корень <tex>\mathtt{first}</tex> и <tex>\mathtt{last}</tex> соответственно.
Также введем вспомогательную функцию проверки узла на тонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>\mathtt{Degree(x) - 1}</tex>.
<code>
'''bool''' isThin(x: '''Node'''):
'''if''' x.rank == 1
'''return''' x.child == ''null''
'''else'''
'''return''' x.child.rank + 1 != x.rank
</code>
=== makeHeap ===
Для создания новой пустой тонкой кучи нужно вернуть ссылку на новый пустой корневой список, его потенциал <tex>\Phi=0</tex>.
<code>
'''ThinHeap''' makeHeap():
H.first = ''null''
H.last = ''null''
'''return''' H
</code>
Стоимость <tex>O(1)</tex>.
=== insert ===
Для вставки элемента в тонкую кучу нужно создать новое тонкое дерево из единственного узла <tex>x</tex> с ключом <tex>x.key</tex>, добавить его в корневой список на первое место, если этот ключ минимален, иначе либо на второепоследнее. Потенциал <tex>\Phi</tex> увеличивается на 1. <code> '''void''' insert(H: '''ThinHeap''', x: '''Node'''): '''if''' H.first == ''null'' H.first = x H.last = x '''else''' '''if''' x.key < H.first.key x.right = H.first H.first = x '''else''' H.last.right = x H.last = x </code>
Стоимость <tex>O(1)</tex>.
Для обращения к минимальному элементу в тонкой куче нужно обратиться к первому корневому узлу списка и вернуть его ключ, потенциал <tex>\Phi</tex> не меняется.
<code>
'''Node''' getMin(H: '''ThinHeap'''):
'''return''' H.first
</code>
Стоимость <tex>O(1)</tex>.
=== meld merge ===
Для объединения тонких куч нужно слить их корневые списки, ставя первым тот список, у которого ключ первого корня минимален. Суммарный потенциал <tex>\Phi</tex> не меняется.
<code>
'''ThinHeap''' merge(H1: '''ThinHeap''', H2: '''ThinHeap'''):
'''if''' H1.first == ''null''
'''return''' H2
'''else'''
'''if''' H2.first == ''null''
'''return''' H1
'''else'''
'''if''' H1.first.key < H2.first.key
H1.last.right = H2.first
H1.last = H2.last
'''return''' H1
'''else'''
H2.last.right = H1.first
H2.last = H1.last
'''return''' H2
</code>
Стоимость <tex>O(1)</tex>.
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
# Удалить корень с минимальным ключом из корневого списка.
# Уменьшить ранг для всех его помеченных тонких детей.
# Cлить детей с корневым списком.
# Объединять, пока возможно, тонкие деревья одного ранга.
При добавлении нового дерева мы, если дерево такого ранга уже есть в массиве, связываем его с существующим и пытаемся добавить новое дерево с рангом на <tex>1</tex> больше.
=== decreaseKey ===
Стоимость <tex>O(1)</tex>.
=== delete ===
Чтобы удалить элемент из тонкой кучи нужно сначала выполнить <tex>\mathtt{decreaseKey}</tex> этого элемента до <tex>-\infty</tex>, а затем выполнить <tex>\mathtt{extractMin}</tex>. <code> '''void''' delete(H: '''ThinHeap''', x: '''Node'''): decreaseKey(H, x, <tex>-\infty</tex>) extractMin() </code>
Стоимость <tex>O(\log(n))</tex>.
= Источники =
* [http://dl.acm.org/citation.cfm?id=1328914 ''Каплан Х.'', ''Тарьян А. Р..'', Thin Heaps, Thick Heaps // ACM Transactions on Algorithms. {{---}} 2008. {{---}} Т.4. {{---}} №1. {{---}} C. 1{{---}}14. {{---}} ISSN: 1549-6325]
* [http://www.lektorium.tv/lecture/?id=14233 ''Станкевич А. С.'', Дополнительные главы алгоритмов, лекция 1 {{---}} Лекториум]
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи — INTUIT.ru]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Структуры данных]]
[[Категория: Приоритетные очереди]]