3622
правки
Изменения
Нет описания правки
|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>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=
}}
|neat =
|definition=
'''лесЛес''' будем называть '''нагруженным''', если он состоит из нескольких толстых деревьев, ранги которых не обязательно попарно различны и узлам которых взаимно однозначно поставлены в соответствие элементы взвешенного множества.
}}
{{Определение
|neat =
|definition=
'''Узел''' в '''нагруженном лесе''' назовем '''неправильным''', если его ключ меньше ключа его родителя.
}}
{{Определение
*<tex>Key</tex> {{---}} ключ элемента, приписанного узлу дерева
*<tex>Parent</tex> {{---}} указатель на родителя
*<tex>LestLeft</tex> {{---}} указатель на ближайшего левого брата
*<tex>Right</tex> {{---}} указатель на ближайшего правого брата
*<tex>LChild</tex> {{---}} указатель на самого левого сына
*<tex>Rank</tex> {{---}} ранг узла.
"Братья" связаны (узлы корневых деревьев, а также сыновья каждого узла) объединены в двусвязный список при помощи указателей <tex>Left</tex> и <tex>Right</tex>. У самого левого (правого) "брата" в этом списке указатель <tex>Left</tex> (<tex>Right</tex>) равен <tex>NULL</tex>.
[[Файл:FatHeapExample.png |400px|thumb|right|Пример толстого дерева <tex>F_0, F_1, F_2, F_3</tex>Представление леса списком]]
=Вспомогательные структуры=
|neat =
|definition=
'''Избыточным ''' <tex>b</tex>-арным представлением числа <tex>x</tex> будем называть последовательность <tex>d = d_n, d_{n-1}, ... d_0</tex>, такую что
<tex dpi = "150">x = {\sum\limits^{n}_{i = 0} {d_i}}{b^i}</tex>
|neat =
|definition=
Назовем <tex>b</tex>-арное избыточное представление числа '''регулярным''', если в нем между любыми двумя цифрами, равными <tex>b</tex> , найдется цифра, отличная от <tex>b-1</tex>.
}}
<br>
Величину <tex>L'(i)</tex> будем называть прямым указателем.
}}
===фиксация цифры===
Фиксацией цифры <tex>b</tex>, стоящей в <tex>i</tex>-м разряде представления <tex>d</tex>, (Fix(i)) назовем операцию, заключающуюся в обнулении цифры <tex>d_i</tex> и инкрементировании цифры <tex>d_{i+1}</tex>, при этом если <tex>i=n</tex> , то полагаем <tex>d_{i+1} = 1</tex>. При каждом выполнении операции фиксации будем обновлять значение <tex>L'(i)</tex>. Очевидно, при <tex>b>2</tex> операцию <tex>Fix(i)</tex> можно выполнить следующим образом:
<code>
L'[i] = L'[i + 1]
</code>
Инкрементирование <tex>i</tex>-й цифры избыточного представления <tex>d</tex> <tex>Inc(i)</tex> можно выполнить так:
<code>
</code>
}}
'''корневой Корневой счетчик''' представляем расширяющимся массивом <tex>RootCount</tex> , каждый элемент которого — запись с тремя полями:
*<tex>RootCount[i].Value</tex> {{---}} <tex>i</tex>-й разряд равный количеству деревьев ранга <tex>i</tex>.
*<tex>RootCount[i].ForvardPointerForwardPointer</tex> {{---}} прямой указатель <tex>i</tex>-го разряда.*<tex>RootCount[i].ListPointer</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex> корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>ListPointer</tex> равен <tex>NULL</tex>.
''Заметим, что если значение равно нулю, то нам неважно значение указателя'' <tex>RootCount[i].ListPointer</tex>.
Обновление прямого указателя <tex>i</tex>-го разряда корневого счетчика заключается в выполнении следующего псевдокода:
<code>
</code>
===Корректировка при вставке ===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при вставке в кучу нового дерева ранга <tex>i</tex> ~(<tex>InsertTree(i,p))</tex>). Эта процедура вставляет новое дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) в списочную часть <tex>i</tex> -го разряда корневого счетчика <tex>RootCount</tex> выглядит так:
<code>
</code>
===Корректировка при удалении===
Корректировка списочной части <tex>i</tex>-го разряда корневого счетчика при удалении из кучи дерева ранга <tex>i</tex> ~(<tex>DeleteTree(i,p))</tex>). Эта процедура удаляет дерево ранга <tex>i</tex> (на него указывает указатель <tex>p</tex>) из списочной части <tex>i</tex>-го разряда корневого счетчика <tex>RootCount</tex> . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:
<code>
</code>
<code>
</code>
<code>
</code>
Функция <tex>MinKeyNodeRoot(p)</tex>, которая по указателю <tex>p</tex> на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом:
<code>
</code>
<code>
</code>
===Инкрементирование <tex>i</tex>-го разряда корневого счетчика <tex>rmIncRootCount(i,p)</tex>===
Здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
<code>
</code>
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг <tex>i</tex> . Тогда значение <tex>i</tex>-го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
<code>
</code>
<code>
</code>
<code>
</code>
