120
правок
Изменения
Изменено изображение
{{Определение
|id=thin_tree_def
|definition='''Тонкое дерево''' (''thin tree'') <tex>T_k</tex> ранга <tex>k</tex> {{---}} это дерево, которое может быть получено из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] <tex>B_k</tex> удалением самого левого сына у нескольких внутренних, то есть не являющихся корнем или листом, узлов самого левого сына.
}}
Ограничение на принадлежность внутренним узлам вызвано тем, что у листьев детей нет, а если у корня <tex>B_k</tex> удалить самого левого сына, то <tex>B_k</tex> превратится в <tex>B_{k-1}</tex>.
# Узел <tex>x</tex> помечен тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
}}
[[Файл:Thin_tree_examples.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются помеченными (не имеют самого левого сына)]]
<br clear="all" />
= Тонкая куча =
