120
правок
Изменения
decreaseKey
{{Определение
|id=thin_tree_def.
|definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
}}
{{Утверждение
|id=about_thin_tree_rank.
|statement=Ранг тонкого дерева равен количеству детей его корня.
}}
== Свойства тонкого дерева ==
{{Утверждение
|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> помечен (неполный).
{{Определение
|id=thin_forest_def.
|definition='''Тонкий лес''' (''thin forest'') {{---}} это набор ''тонких деревьев'', ранги которых не обязательно попарно различны.
}}
{{Утверждение
|id=about_thin_forest_with_n_nodes.
|statement=Для любого натурального числа <tex>n</tex> существует тонкий лес, который содержит ровно <tex>n</tex> элементов и состоит из тонких деревьев попарно различных рангов.
|proof=Действительно, любой [[Биномиальная куча#Биномиальное дерево|биномиальный]] лес является тонким, а для [[Биномиальная куча#Биномиальное дерево|биномиального]] леса рассматриваемое утверждение справедливо.
{{Определение
|id=thin_heap_def.
|definition='''Тонкая куча''' (''thin heap'') {{---}} это [[Двоичная куча|кучеобразно]] нагруженный ''тонкий лес''.
}}
{{Теорема
|id=max_rank_th.
|about=О максимальном ранге узла
|statement=В тонкой куче из <tex>n</tex> элементов <tex>D(n) \leqslant \log_{\Phi} n</tex>, где <tex dpi = "180">\Phi=\frac{1+\sqrt{5}}{2}</tex> {{---}} золотое сечение.
<tex>T_0=1,T_1=1,T_k \geqslant 1+\sum_{i=0}^{k-2}T_i</tex> для <tex>k \geqslant 2</tex>
Числа Фибоначчи удовлетворяют этому же рекуррентному соотношению, причем неравенство можно заменить равенством. Отсюда по индукции следует, что <tex>T_k \geqslant F_k</tex> для любых <tex>k</tex>. Неравенство <tex>F_k \geqslant \Phi^{k-1}</tex> [[Фибоначчиева куча#Лемма3|хорошо известно]].
Теперь убедимся в том, что максимально возможный ранг <tex>D(n)</tex> ''тонкого дерева'' в тонкой куче, содержащей <tex>n</tex> элементов, не превосходит числа <tex>\log_{\Phi}(n)+1</tex>. Действительно, выберем в тонкой куче дерево максимального ранга. Пусть <tex>n^*</tex> {{---}} количество вершин в этом дереве, тогда <tex>n \geqslant n^* \geqslant \Phi^{D(n)-1}</tex>.
Отсюда следует, что <tex>D(n)\leqslant\log_{\Phi}(n)+1</tex>.
{{Утверждение
|id=about_thin_heap_potential.
|statement=Определённый таким образом потенциал обладает свойствами:
# <tex>\Phi \geqslant 0</tex>.
=== decreaseKey ===
Стоимость <tex>O(1)</tex>.
* [http://www.intuit.ru/studies/courses/100/100/lecture/1542 Тонкие кучи — INTUIT.ru]
* [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 {{---}} Лекториум]
[[Категория: Дискретная математика и алгоритмы]]
[[Категория: Приоритетные очереди]]
