497
правок
Изменения
Нет описания правки
//[[Файл:ThickTreeExample.gif Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</tex>]]
== Свойства Толстых деревьев ==
'''Толстая куча''' — это '''почти кучеобразный''' '''нагруженный лес'''.
}}
==Представление толстой кучи==
Каждый узел толстой кучи будем представлять записью со следующими полями:
*<tex>Key</tex> {{---}} ключ элемента, приписанного узлу дерева
*<tex>Parent</tex> {{---}} указатель на родителя
*<tex>Lest</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>.
//[[Файл:ThickTreeExample.gif Пример толстых деревьев <tex>F_0, F_1, F_2, F_3</tex>]]
=Вспомогательные структуры=
=Основные операции=
* <tex>MakeHeap</tex> {{---}}<tex>O(1)</tex>
заключается в инициализации счетчиков.
* <tex>FindMin</tex> {{---}}<tex>O(1)</tex>
возвращает указатель на минимальный элемент.
* <tex>Insert(key)</tex> {{---}} <tex>O(1)</tex>
Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга <tex>0</tex> в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.
* <tex>DecreaseKey</tex> {{---}} <tex>O(1)</tex>
Чтобы выполнить эту операцию, поступим следующим образом. Пусть <tex>x</tex> — узел, на который указывает указатель <tex>p</tex> . Вычитаем <tex>\delta</tex> из ключа узла <tex>x</tex> . Если новый ключ <tex>x</tex> меньше минимального ключа кучи <tex>H</tex>, обмениваем ключ элемента <tex>p</tex> с ключом минимального элемента. Новых нарушений операция не создаст. Пусть <tex>r</tex> — ранг <tex>x</tex> . Если <tex>x</tex> — нарушаемый узел, добавляем <tex>x</tex> как новое <tex>r</tex>-ранговое нарушение инкрементированием <tex>r</tex>-й цифры <tex>d_r</tex> счетчика нарушений.
* <tex>DeleteMin</tex> {{---}} <tex>O(\log(n))</tex>
Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов.
Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.
* <tex>Delete</tex> {{---}} <tex>O(\log(n))</tex>
<tex>DecreaseKey</tex> а затем <tex>DeleteMin</tex>
* <tex>Meld(h1, h2)</tex> {{---}} <tex>O(\log(n))</tex>
Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — <tex>р2</tex> . Пройти по счетчику нарушений <tex>p2</tex> от младшей цифры к старшей, пропуская цифры со значением <tex>0</tex> . Для <tex>i</tex>-й цифры <tex>d_i != 0</tex> делаем операцию фиксирования на каждой цифре, показываемой прямым указателем <tex>d_i</tex> , если эта цифра имеет значение 2. Затем, если <tex>d_i = 2</tex> , фиксируем <tex>d_i</tex> . Если <tex>d_i = 1</tex> , преобразуем это <tex>i</tex>-ранговое нарушение в <tex>(i+1)</tex>-ранговое нарушение, как при фиксировании, используя <tex>i</tex>-рангового брата нарушенного узла вместо (несуществующего) другого <tex>i</tex> -рангового нарушения.
Как только <tex>h2</tex> не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика <tex>h2</tex> в корневой счетчик <tex>h1</tex> инкрементированием соответствующих цифр. Если минимальный узел <tex>h2</tex> содержит меньший ключ, чем минимальный узел <tex>h1</tex> , следует установить новым минимальным узлом <tex>h1</tex> минимальный узел <tex>h2</tex> . Затем нужно вернуть модифицированную кучу <tex>h1</tex> в качестве результата <tex>Meld</tex> .
* <tex>DeleteViolation</tex>
