Толстое дерево

Определение:

Определяем толстое дерево ранга , следующим образом:

Толстое дерево [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]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]Key[/math] — ключ элемента, приписанного узлу дерева
[math]Parent[/math] — указатель на родителя
[math]Lest[/math] — указатель на ближайшего левого брата
[math]Right[/math] — указатель на ближайшего правого брата
[math]LChild[/math] — указатель на самого левого сына
[math]Rank[/math] — ранг узла.

"Братья" связаны в двусвязный список при помощи указателей [math]Left[/math] и [math]Right[/math]. У самого левого (правого) "брата" в этом списке указатель [math]Left[/math] ([math]Right[/math]) равен [math]NULL[/math].

Пример толстого дерева

Вспомогательные структуры

Нам понадобятся понятия корневого счетчика и счетчика нарушений.

Толстую кучу будем представлять записью следующего вида: , где:

[math]RootCount[/math] — массив, соответствующий корневому счетчику

[math]CountViolation[/math] — массив, соответствующий счетчику нарушений

[math]MinPointer[/math] — указатель на элемент кучи с минимальным ключом

[math]MaxRank[/math] — наибольший ранг среди рангов деревьев, присутствующих в куче

Избыточное представление чисел

Определение:

Избыточным -арным представлением числа будем называть последовательность , такую что

где ,

Определение:

Назовем -арное избыточное представление числа регулярным, если в нем между любыми двумя цифрами, равными , найдется цифра, отличная от .

Определение:

Пусть — номер разряда, отличного от и ближайшего слева от -го разряда в регулярном -арном избыточном представлении .

Определим [math]L'(i)[/math] следующим образом:

[math]L'(i) = L(i)[/math] , если [math]d_i \in \{b-1, b-2\}[/math] и [math]d(L(i))=b[/math];
[math]L'(i)[/math] — произвольное число [math]\gt i[/math], если [math]d_i \in \{b-1, b-2\}[/math] и [math]d(L(i))\lt b-1[/math];
[math]L'(i)[/math] — не определено, если [math]d \notin \{b-1, b-2 \}[/math] .

Величину будем называть прямым указателем.

фиксация цифры

Фиксацией цифры [math]b[/math], стоящей в [math]i[/math]-м разряде представления [math]d[/math], (Fix(i)) назовем операцию, заключающуюся в обнулении цифры [math]d_i[/math] и инкрементировании цифры [math]d_{i+1}[/math], при этом если [math]i=n[/math] , то полагаем d_{i+1} = 1. При каждом выполнении операции фиксации будем обновлять значение [math]L'(i)[/math]. Очевидно, при [math]b\gt 2[/math] операцию [math]Fix(i)[/math] можно выполнить следующим образом:

Fix(i)
 if(d[i] == b)
     d[i] = 0;
     d[i + 1]++; 
 if(d[i + 1] == b - 1)
     L'[i] = L'(i + 1)
 else
     L'[i] = i + 1;

инкремент

Инкрементирование [math]i[/math]-й цифры избыточного представления [math]d[/math] [math]Inc(i)[/math] можно выполнить так:

Inc(i)
 Fix(i);
 if (d[i] == b - 1) or (d[i] == b - 2)
     Fix(L'[i]);
 d[i]++;
 Fix(i);

Корневой счетчик

Корневой счетчик состоит из избыточного троичного представления числа элементов в куче и набора списочных элементов.

Значение его [math]i[/math]-го разряда равно количеству деревьев ранга [math]i[/math], присутствующих в куче. При таком определении избыточного корневого представления число, которое оно представляет, равно числу узлов в куче, так как толстое дерево ранга [math]i[/math] содержит ровно [math]3^i[/math] узлов. Заметим, что состояние избыточного корневого представления определяется неоднозначно. Очевидно, что для любой толстой кучи, состоящей из [math]n[/math] элементов, существует регулярное избыточное представление корневого счетчика. Списочный элемент, приписанный [math]i[/math]-му разряду избыточного корневого представления, — это указатель на список деревьев ранга [math]i[/math], присутствующих в куче, образованный посредством указателей [math]Right[/math] корневых узлов связываемых деревьев.

Утверждение (о корневом счетчике):

Из определения корневого счетчика следует:

Корневой счетчик позволяет иметь доступ к корню любого дерева ранга [math]i[/math] за время [math]O(1)[/math].
Вставка толстого дерева ранга [math]i[/math] соответствует операции инкрементирования [math]i[/math]-го разряда корневого счетчика.
Удаление толстого поддерева ранга [math]i[/math] соответствует операции декрементирования [math]i[/math]-го разряда корневого счетчика.
Операции инкрементирования и декрементирования [math]i[/math]-го разряда корневого счетчика осуществляются за время [math]O(1)[/math].

корневой счетчик представляем расширяющимся массивом [math]RootCount[/math] , каждый элемент которого — запись с тремя полями:

[math]RootCount[i].Value[/math] — [math]i[/math]-й разряд равный количеству деревьев ранга [math]i[/math].
— прямой указатель [math]i[/math]-го разряда.
[math]RootCount[i].ListPointer[/math] — указатель на список деревьев ранга [math]i[/math], присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя [math]Right[/math] корневых узлов связываемых деревьев. Если в куче нет деревьев ранга [math]i[/math] , то указатель [math]ListPointer[/math] равен NULL.

Заметим, что если значение равно нулю, то нам неважно значение указателя [math]RootCount[i].ListPointer[/math].

Инициализация

Чтобы время инициализации счетчиков было [math]O(1)[/math], используем поразрядную их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную [math]MaxRank[/math], которая показывает нам, какая часть массивов счетчиков используется в данный момент.

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

Обновление прямого указателя

Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении следующего псевдокода:

UpdateForwardPionter(i)
 if RootCount[i + 1].Value == 3 - 1
     RootCount[i].ForwardPointer = RootCount[i + 1].ForwardPointer;
 else
     RootCount[i].ForwardPointer = i + 1;

Корректировка при вставке

Корректировка списочной части [math]i[/math]-го разряда корневого счетчика при вставке в кучу нового дерева ранга [math]i[/math] ([math]InsertTree(i,p)[/math]). Эта процедура вставляет новое дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) в списочную часть [math]i[/math] -го разряда корневого счетчика [math]RootCount[/math] выглядит так:

InsertTree(i, p)
 p1 = RootCount[i].ListPointer;
 if RootCount[i].Value != 0
     p.Right = p1;
 else
     p.Right = NULL;
 p.Left = NULL;
 RootCount[i].ListPointer = p;

Корректировка при удалении

Корректировка списочной части [math]i[/math]-го разряда корневого счетчика при удалении из кучи дерева ранга [math]i[/math] ([math]DeleteTree(i,p)[/math]). Эта процедура удаляет дерево ранга [math]i[/math] (на него указывает указатель [math]p[/math]) из списочной части [math]i[/math]-го разряда корневого счетчика [math]RootCount[/math] . Будем считать, что указанное дерево присутствует в куче. Процедура заключается в выполнении следующего псевдокода:

DeleteTree(i, p)
 p1 = RootCount[i].ListPointer;
 if(p1 == p)
     RootCount[i].ListPointer = p.Right;
 j = 1;
 while(j <= RootCount[i].Value) and (p1.Right != p) do
     p1.Right = p.Right;

Связывание трех деревьев в одно

Связывание [math](Fastening (p1, p2, p3))[/math] трех толстых деревьев ранга [math]i[/math] в одно толстое дерево ранга [math]i+1[/math]. Эта функция принимает три указателя [math](p1, p2 ,p3)[/math] на три разных толстых дерева одного и того же ранга [math]i[/math] и возвращает указатель на вновь сформированное дерево ранга [math]i+1[/math] . Процедура заключается в выполнении следующего псевдокода:

Fastening (p1, p2, p3)
 if(p1.Key <= p2.Key) and (p1.Key <= p3.Key)
     MinP = p1;
     p1 = p2;
     p2 = p3;
 if(p2.Key <= p1.Key) and(p2.Key <= p3.Key)
     MinP = p2;
     p1 = p1;
     p2 = p3;
 if(p3.Key <= p1.Key) and(p3.Key <= p2.Key)
     MinP = p3;
     p1 = p1;
     p2 = p2;
 p1.Right = p2;
 p1.Left = NULL;
 p1.Parent = MinP;
 p2.Right = MinP.LChild;
 p2.Left = p1;
 p2.Parent = MinP;
 if(MinP.LChild != NULL)
     MinP.LChild.Left = p2;
 MinP.LChild = p1;
 MinP.Rank = MinP.Rank + 1;
 MinP.Right = NULL;
 MinP.Left = NULL;
 Fastening = MinP;

Значение ключа элемента по указателю

Функция [math]GetKey(p)[/math] по указателю p на элемент определяет значение его ключа:

// под [math]\infty[/math] нужно понимать нейтральный относительно минимума элемент.

GetKey(p)
 if(p = NULL)
     Min = [math]\infty[/math];
 else
     Min = p.key;
 GetKey = Min;

Узел с минимальным ключом

Функция [math]MinKeyNodeRoot(p)[/math], которая по указателю [math]p[/math] на списочную часть разряда корневого счетчика возвращает указатель на корневой узел с минимальным ключом: MinKeyNodeRoot(p)

 p1 = p;
 MinP = p1;
 while p1 != NULL 
     if(p1.Key < MinP.Key)
         MinP = p1;
         p1 = p1.Right;
 MinKeyNodeRoot = MinP;

Операция фиксации [math]rmFixRootCount(i)[/math]

Операция фиксации [math]i[/math]-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга [math]i[/math], состоящий ровно из трех деревьев. При выполнении этой операции значение в [math]i[/math]-м разряде — должно стать равным нулю, а значение в [math]i[/math]-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга [math]i[/math], а количество деревьев ранга [math]i+1[/math] должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга [math]i[/math] , связать их в дерево ранга [math]i+1[/math] и вставить вновь полученное дерево в кучу. Следует учесть, что ранг нового дерева может стать больше, чем [math]MaxRank[/math], что потребует инициализации нового разряда. Для этого необходимо увеличить значение [math]MaxRank[/math] на единицу и заполнить новое поле, а также провести инициализацию нового разряда.

if(MaxRank = i)
    maxRank := i + 1;
    RootCount[i+1].Value := 0;
    CountViolation[i+1].Value := 0;
else
    UpdateForwardPointer(i+1);
RootCount[i].Value := 0;
p1 := RootCount[i].ListPointer;
p2 := p1.Right;
p3 := p2.Right;
p := Fastening(p1, p2, p3);
RootCount[i].ListPointer := NULL;
InsertTree(i+1, p);
RootCount[i+1].Value := RootCount[i+1].Value + 1;

Инкрементирование i-го разряда корневого счетчика [math]rm IncRootCount(i,p)[/math]

Здесь мы должны учесть работу со списочной частью и обновить прямые указатели.

if(RootCount[i].Value = 1) or (RootCount[i].Value = 2)
    if(RootCount[Rootcount[i].ForwardPointer)
if(RootCount[i].Value = 3)
    FixRootCount(i);
InsertTree(i,p);
RootCount[i].Value := RootCount[i].Value + 1;
UpdateForwardPointer(i);
if(rootcount[i].Value = 3)
    FixRootCount(i);

удаление дерева из кучи

Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг . Тогда значение -го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.

DeleteTree(i,p);
RootCount[i].Value := RootCount[i].Value -1;

Нахождение дерева с минимальным ключом в корне ([math]MinKey[/math])

MinP := NULL;
for(i := 0 to MaxRank) do
    p1:=MinKeyNodeRoot(RootCount[i].ListPointer);
    if(GetKey(p1)<GetKey(MinP))
        MinP := p1;
MinKey := MinP;

Счетчик нарушений

Заметим, что счетчик нарушений очень похож на корневой счетчик выше, но в отличие от второго:

Нас теперь интересует не само число, а только значения разрядов.
Операция фиксации тесно связана с толстой кучей.

Значение [math]i[/math]-го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга [math]i[/math] , а его списочная часть — это указатели на неправильные узлы ранга [math]i[/math] .

Счетчик нарушений состоит из расширенного избыточного двоичного представления и набора списочных элементов.

Счетчик нарушений представлен Саморасширяющимся массивом, элементы которого состоят из четырех полей:

[math]CountViolation[i].Value[/math] — количество неправильных узлов ранга [math]i[/math] в куче.
— прямой указатель [math]i[/math]-го разряда
— указатель на неправильный узел ранга [math]i[/math]
— указатель на неправильный узел ранга [math]i[/math]

Утверждение (о счетчике нарушений):

из определения счетчика нарушений следует:

Наличие счетчика нарушений позволяет иметь доступ к любому неправильному узлу ранга [math]i[/math] за время [math]O(1)[/math] .
Уменьшение ключа у элемента ранга [math]i[/math] соответствует операции инкрементирования [math]i[/math]-го разряда счетчика нарушений (естественно, лишь в случае, когда новое значение ключа у изменяемого узла становится меньше значения ключа его родителя).
Операции инкрементирования и декрементирования [math]i[/math]-го разряда осуществляются за время [math]O(1)[/math].

Для инициализации нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга [math]MaxRank + 1[/math]. Это первый момент появления в куче узла ранга [math]MaxRank + 1[/math]. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного [math]MaxRank + 1[/math], соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.

Основные операции

[math]MakeHeap[/math] —[math]O(1)[/math]

заключается в инициализации счетчиков.

[math]FindMin[/math] —[math]O(1)[/math]

возвращает указатель на минимальный элемент.

[math]Insert(key)[/math] — [math]O(1)[/math]

Чтобы выполнить эту операцию, делаем новый элемент отдельным деревом и выполняем процедуру вставки нового элемента ранга [math]0[/math] в корневой счетчик. После этого, если необходимо, корректируем значение указателя на минимальный элемент.

[math]DecreaseKey[/math] — [math]O(1)[/math]

Чтобы выполнить эту операцию, поступим следующим образом. Пусть [math]x[/math] — узел, на который указывает указатель [math]p[/math] . Вычитаем [math]\delta[/math] из ключа узла [math]x[/math] . Если новый ключ [math]x[/math] меньше минимального ключа кучи [math]H[/math], обмениваем ключ элемента [math]p[/math] с ключом минимального элемента. Новых нарушений операция не создаст. Пусть [math]r[/math] — ранг [math]x[/math] . Если [math]x[/math] — нарушаемый узел, добавляем [math]x[/math] как новое [math]r[/math]-ранговое нарушение инкрементированием [math]r[/math]-й цифры [math]d_r[/math] счетчика нарушений.

[math]DeleteMin[/math] — [math]O(\log(n))[/math]

Удаляем поддерево с корнем в минимальном узле из леса. Минимальность этого элемента гарантирует нам, что среди его детей нарушений порядка кучи не было. То есть нет необходимости работать со счетчиком нарушений. Затем вставляем в кучу все деревья с корнями, расположенными в детях удаляемого узла. Очевидно, что новый минимальный ключ — либо в корне дерева леса, либо в нарушенном узле. Выполняем поиск нового минимального элемента среди корней деревьев и нарушенных узлов. Если минимальный элемент оказался в нарушенном узле, то обмениваем его с элементом, хранимым в корне этого дерева, корректируя корневой счетчик, если это необходимо. После замены новый минимум — в корне дерева леса. Этот корень будет новым минимальным узлом.

[math]Delete[/math] — [math]O(\log(n))[/math]

выполняем [math]DecreaseKey[/math] а затем [math]DeleteMin[/math]

[math]Meld(h1, h2)[/math] — [math]O(\log(n))[/math]

Первый шаг — фиксируются все нарушения в куче с меньшим максимальным рангом (разрывая связь произвольно). Не уменьшая общности, считаем, что эта куча — [math]р2[/math] . Пройти по счетчику нарушений [math]p2[/math] от младшей цифры к старшей, пропуская цифры со значением [math]0[/math] . Для [math]i[/math]-й цифры [math]d_i != 0[/math] делаем операцию фиксирования на каждой цифре, показываемой прямым указателем [math]d_i[/math] , если эта цифра имеет значение 2. Затем, если [math]d_i = 2[/math] , фиксируем [math]d_i[/math] . Если [math]d_i = 1[/math] , преобразуем это [math]i[/math]-ранговое нарушение в [math](i+1)[/math]-ранговое нарушение, как при фиксировании, используя [math]i[/math]-рангового брата нарушенного узла вместо (несуществующего) другого [math]i[/math] -рангового нарушения. Как только [math]h2[/math] не будет содержать каких-либо нарушений, нужно вставить корни из корневого счетчика [math]h2[/math] в корневой счетчик [math]h1[/math] инкрементированием соответствующих цифр. Если минимальный узел [math]h2[/math] содержит меньший ключ, чем минимальный узел [math]h1[/math] , следует установить новым минимальным узлом [math]h1[/math] минимальный узел [math]h2[/math] . Затем нужно вернуть модифицированную кучу [math]h1[/math] в качестве результата [math]Meld[/math] .

[math]DeleteViolation[/math]

для освобождения кучи от нарушений достаточно выполнить следующий псевдокод:

for i:=0 to h2.MaxRank do
if (CountViolation[i].Value = 2)
    FixCountViolation(i);
for i:=0 to h2.MaxRank do 
    if(CountViolation[i].Value = 1)
        IncCountViolation(i, SearchBrother(CountViolation[i].rmFirstviolation));
        FixCountViolation(i);

Источники

Толстые кучи — INTUIT.ru

Толстая куча на избыточном счётчике

Толстое дерево

Толстые кучи

Представление толстой кучи

Вспомогательные структуры

Избыточное представление чисел

фиксация цифры

инкремент

Корневой счетчик

Инициализация

Обновление прямого указателя

Корректировка при вставке

Корректировка при удалении

Связывание трех деревьев в одно

Значение ключа элемента по указателю

Узел с минимальным ключом

Операция фиксации [math]rmFixRootCount(i)[/math]

Инкрементирование i-го разряда корневого счетчика [math]rm IncRootCount(i,p)[/math]

удаление дерева из кучи

Нахождение дерева с минимальным ключом в корне ([math]MinKey[/math])

Счетчик нарушений

Основные операции

Источники

Навигация

Персональные инструменты

Пространства имён

Варианты

Просмотры

Ещё

Поиск

Навигация

Инструменты