120
правок
Изменения
Нет описания правки
|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> помечен тонкий (не полон).# Корень не помечен тонкий (полон).
# Для любого узла <tex>x</tex> ранги его детей от самого правого к самому левому равны соответственно <tex>0,1,2,...,Degree(x)-1</tex>.
# Узел <tex>x</tex> помечен тонкий тогда и только тогда, когда его ранг на 2 больше, чем ранг его самого левого сына, или его ранг равен 1, и он не имеет детей.
}}
[[Файл:Thin_trees.png|200x200px|слева|frame|Из [[Биномиальная куча#Биномиальное дерево|биномиального дерева]] ранга 3 получены два тонких дерева. Числа обозначают ранги узлов, закрашенные вершины являются помеченными тонкими (не имеют самого левого сына)]]
<br clear="all" />
*<tex>rank</tex> {{---}} ранг узла.
Для ускорения проверки на тонкость (''thinness'') можно отдельно хранить помеченность тонкость вершины.
Также в вершине можно хранить любую дополнительную информацию.
Для [[Амортизационный анализ|амортизационного анализа]] операций применим [[Амортизационный анализ#Метод потенциалов|метод потенциалов]].
Пусть функция потенциала определена как <tex>\Phi = n + 2 \cdot m</tex> где <tex>n</tex> {{---}} это количество тонких деревьев в куче, а <tex>m</tex> {{---}} это количество помеченных тонких вершин.
{{Утверждение
Пусть <tex>Node</tex> {{---}} узел тонкого дерева, а <tex>ThinHeap</tex> {{---}} тонкая куча, причем <tex>ThinHeap</tex> содержит ссылки на первый и последний корень <tex>first</tex> и <tex>last</tex> соответственно.
Также введем вспомогательную функцию проверки узла на помеченностьтонкость, для этого воспользуемся тем, что у левого сына узла <tex>x</tex> ранг равен <tex>Degree(x) - 1</tex>.
<code>
bool isMarkedisThin(x)
if x.rank == 1
return x.child == null
Чтобы извлечь минимальный элемент из тонкой кучи нужно:
# Удалить корень с минимальным ключом из корневого списка.
# Уменьшить ранг для всех его помеченных тонких детей.
# Cлить детей с корневым списком.
# Объединять, пока возможно, тонкие деревья одного ранга.
H.first = H.first.right
if H.first == null H.last = null
// Снимаем пометки тонкость с его детей и добавляем их в корневой список
x = tmp.first.child
while x != null
if isMarkedisThin(x)
x.rank = x.rank - 1
x.left = null
# Ранг узла <tex>y</tex> на три больше, чем ранг его самого левого сына.
# Ранг узла <tex>y</tex> равен двум, и он не имеет детей.
# Узел <tex>y</tex> есть помеченный тонкий корень дерева.
Пусть узел <tex>y</tex> — это узел локализации братского нарушения.
* Узел <tex>y</tex> не помечентонкий, тогда помещаем поддерево с корнем в самом левом сыне узла <tex>y</tex> на место пропущенного в братском списке. Узел <tex>y</tex> становится помеченнымтонким, дерево становится корректным, процедура исправления завершается.* Узел <tex>y</tex> помечентонкий, тогда уменьшаем ранг узла <tex>y</tex> на единицу. Теперь узлом локализации нарушения будет либо левый брат узла <tex>y</tex>, либо его родитель, тогда нарушение станет родительским.
С помощью этих действий мы избавились от братских нарушений, теперь разберем родительские.
Переместим все поддерево с корнем в <tex>y</tex> в корневой список и уменьшим ранг <tex>y</tex>.
* Узел <tex>z</tex> не был помечентонким, пометим егокак тонкий, тогда дерево станет корректным.* Узел <tex>z</tex> был помечентонким, тогда <tex>z</tex> {{---}} новый узел локализации родительского нарушения, переходим к нему.
Продолжая эту процедуру, мы или остановимся, или дойдем до корня дерева, тогда достаточно сделать ранг корня на 1 больше ранга его самого левого сына.
Каждый промежуточный шаг рекурсии уменьшает количество помеченных тонких узлов на 1 и добавляет не более одного дерева в корневой список, тогда на каждом промежуточном шаге потенциал уменьшается минимум на 1, отсюда амортизированная стоимость <tex>O(1)</tex>.
Стоимость <tex>O(1)</tex>.
