Толстая куча на избыточном счётчике — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Новая страница: «=Толстое дерево (статья пишется - ничего не трогать!)= {{Определение |id=def1. |neat = 1 |definition= Оп...»)
(нет различий)

Версия 21:16, 20 мая 2013

Толстое дерево (статья пишется - ничего не трогать!)

Определение:
Определяем толстое дерево [math]F_k[/math] ранга [math]k[/math] [math]k = 0, 1, 2, \dots [/math] следующим образом:
  • Толстое дерево [math]F_0[/math] ранга ноль состоит из единственного узла.
  • Толстое дерево [math]F_k[/math] ранга [math]k[/math], для [math]k = 1, 2, 3,\dots [/math], состоит из трех деревьев [math]F_{k-1}[/math] ранга [math]k[/math], связанных так, что корни двух из них являются самыми левыми потомками корня третьего.
Ранг узла [math]x[/math] в толстом дереве определяется как ранг толстого поддерева с корнем в узле [math]x[/math].


//[[Файл:ThickTreeExample.gif Пример толстых деревьев [math]F_0, F_1, F_2, F_3[/math]]]



Свойства Толстых деревьев

Утверждение:
Свойства толстых деревьев:
  • В толстом дереве ранга [math]k[/math] ровно [math]3^k[/math] узлов.
  • Для любого натурального числа [math]n[/math] существует лес из толстых деревьев, в котором ровно [math]n[/math] узлов. Такой лес можно построить, включив в него столько деревьев ранга [math]i[/math], каково значение [math]i[/math]-го разряда представления числа [math]n[/math] в троичной системе счисления. Заметим, что для построения такого леса можно использовать и избыточные троичные представления.
  • Толстый лес из [math]n[/math] узлов содержит [math]O(n\log(n))[/math] деревьев.


Определение:
лес будем называть нагруженным, если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.


Определение:
Узел в нагруженном лесе назовем неправильным, если его ключ меньше ключа его родителя.


Определение:
Нагруженный лес назовем почти кучеобразным, если для каждого значения [math]k[/math] в нем имеется не более двух неправильных узлов ранга [math]k[/math].


Толстые кучи

Определение:
Толстая куча — это почти кучеобразный нагруженный лес.