497
правок
Изменения
Новая страница: «=Толстое дерево (статья пишется - ничего не трогать!)= {{Определение |id=def1. |neat = 1 |definition= Оп...»
=Толстое дерево (статья пишется - ничего не трогать!)=
{{Определение
|id=def1.
|neat = 1
|definition=
Определяем '''толстое дерево''' <tex>F_k</tex> ранга <tex>k</tex> <tex>k = 0, 1, 2, \dots </tex> следующим образом:
*Толстое дерево <tex>F_0</tex> ранга ноль состоит из единственного узла. <br>
*Толстое дерево <tex>F_k</tex> ранга <tex>k</tex>, для <tex>k = 1, 2, 3,\dots </tex>, состоит из трех деревьев <tex>F_{k-1}</tex> ранга <tex>k</tex>, связанных так, что корни двух из них являются самыми левыми потомками корня третьего.
Ранг узла <tex>x</tex> в толстом дереве определяется как ранг толстого поддерева с корнем в узле <tex>x</tex>.
}}
//[[Файл:ThickTreeExample.gif Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</tex>]]
<br> <br><br>
== Свойства Толстых деревьев ==
{{Утверждение
|id=proposal1.
|author=
|about=
|statement=
'''Свойства толстых деревьев:''' <br>
*В толстом дереве ранга <tex>k</tex> ровно <tex>3^k</tex> узлов. <br>
*Для любого натурального числа <tex>n</tex> существует лес из толстых деревьев, в котором ровно <tex>n</tex> узлов. Такой лес можно построить, включив в него столько деревьев ранга <tex>i</tex>, каково значение <tex>i</tex>-го разряда представления числа <tex>n</tex> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
*Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log(n))</tex> деревьев.
|proof=
}}
{{Определение
|id=def2
|neat =
|definition=
'''лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|id=def3
|neat =
|definition=
'''Узел''' в '''нагруженном лесе''' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
|id=def4
|neat =
|definition=
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>.
}}
=Толстые кучи=
{{Определение
|id=def5
|neat =
|definition=
'''Толстая куча''' — это '''почти кучеобразный''' '''нагруженный лес'''.
}}
{{Определение
|id=def1.
|neat = 1
|definition=
Определяем '''толстое дерево''' <tex>F_k</tex> ранга <tex>k</tex> <tex>k = 0, 1, 2, \dots </tex> следующим образом:
*Толстое дерево <tex>F_0</tex> ранга ноль состоит из единственного узла. <br>
*Толстое дерево <tex>F_k</tex> ранга <tex>k</tex>, для <tex>k = 1, 2, 3,\dots </tex>, состоит из трех деревьев <tex>F_{k-1}</tex> ранга <tex>k</tex>, связанных так, что корни двух из них являются самыми левыми потомками корня третьего.
Ранг узла <tex>x</tex> в толстом дереве определяется как ранг толстого поддерева с корнем в узле <tex>x</tex>.
}}
//[[Файл:ThickTreeExample.gif Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</tex>]]
<br> <br><br>
== Свойства Толстых деревьев ==
{{Утверждение
|id=proposal1.
|author=
|about=
|statement=
'''Свойства толстых деревьев:''' <br>
*В толстом дереве ранга <tex>k</tex> ровно <tex>3^k</tex> узлов. <br>
*Для любого натурального числа <tex>n</tex> существует лес из толстых деревьев, в котором ровно <tex>n</tex> узлов. Такой лес можно построить, включив в него столько деревьев ранга <tex>i</tex>, каково значение <tex>i</tex>-го разряда представления числа <tex>n</tex> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
*Толстый лес из <tex>n</tex> узлов содержит <tex>O(n\log(n))</tex> деревьев.
|proof=
}}
{{Определение
|id=def2
|neat =
|definition=
'''лес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|id=def3
|neat =
|definition=
'''Узел''' в '''нагруженном лесе''' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
|id=def4
|neat =
|definition=
'''Нагруженный лес''' назовем '''почти кучеобразным''', если для каждого значения <tex>k</tex> в нем имеется не более двух '''неправильных''' узлов ранга <tex>k</tex>.
}}
=Толстые кучи=
{{Определение
|id=def5
|neat =
|definition=
'''Толстая куча''' — это '''почти кучеобразный''' '''нагруженный лес'''.
}}
