635
правок
Изменения
→Толстое дерево
*Толстое дерево <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-1</tex>,таких, что корни двух из них являются самыми левыми потомками корня третьего.
}}
[[Файл:FatTreesExample.png |400px|thumb|center|Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</tex>]]
{{Определение
|id=def3
|neat =
|definition=
'''Ранг узла''' <tex>x</tex> в толстом дереве определяется как ранг толстого поддерева с корнем в узле <tex>x</tex>.
}}
==Свойства толстых деревьев==
{{Утверждение
|id=proposal1.
|author=
|about=
|statement=
В толстом дереве ранга <tex>k</tex> ровно <tex>3^k</tex> узлов.
|proof=
}}
{{Определение
|id=thin_forest_def
|definition='''Толстый лес''' (англ. ''Thick forest'') {{---}} это набор толстых деревьев, ранги которых не обязательно попарно различны.
}}
{{Утверждение
|id=proposal1.
|author=
|about=
|statement=
Для любого натурального числа <tex>n</tex> существует лес из толстых деревьев, в котором ровно <tex>n</tex> узлов.
|proof= Действительно, такой лес можно построить, включив в него столько деревьев ранга <tex>i</tex>, каково значение <tex>i</tex>-го разряда представления числа <tex>n</tex> в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
}}
{{Утверждение
|about=
|statement=
|proof=
}}
