497
правок
Изменения
→Корневой счетчик
*<tex>RootCount[i].ListPointer</tex> {{---}} указатель на список деревьев ранга <tex>i</tex>, присутствующих в толстой куче. Деревья в этом списке связаны при помощи указателя <tex>Right</tex> корневых узлов связываемых деревьев. Если в куче нет деревьев ранга <tex>i</tex> , то указатель <tex>ListPointer</tex> равен NULL.
''Заметим, что если значение равно нулю, то нам неважно значение указателя'' <tex>RootCount[i].ListPointer</tex>.
===Инициализация===
Чтобы время инициализации счетчиков было <tex>O(1)</tex>, используем '''поразрядную''' их инициализацию. То есть будем добавлять новые разряды только тогда, когда возникает такая необходимость, и при этом инициализировать новый разряд сразу в обоих счетчиках. Для этого мы вводим переменную <tex>MaxRank</tex>, которая показывает нам, какая часть массивов счетчиков используется в данный момент.
При начальной инициализации необходимо установить счетчики в состояние, которое отвечает '''пустой куче'''. Очевидно, что в пустой куче не может быть никаких нарушений.
===Обновление прямого указателя===
Обновление прямого указателя i-го разряда корневого счетчика заключается в выполнении следующего псевдокода:
<code>
if (RootCount[i+1].Value=3-1)
RootCount[i].ForwardPointer := RootCount[i+1].ForwardPointer;
else
RootCount[i].ForwardPointer := i + 1;
</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>
p1 := RootCount[i].ListPointer;
if(RootCount[i].Value != 0)
p.Right = p1;
else
p.Right = NULL;
p.Left := NULL;
RootCount[i].ListPointer := p;
</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>
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;
</code>
===Связывание трех деревьев в одно===
'''Связывание''' <tex>(Fastening (p1, p2, p3))</tex> трех толстых деревьев ранга <tex>i</tex> в одно толстое дерево ранга <tex>i+1</tex>. Эта функция принимает три указателя <tex>(p1, p2 ,p3)</tex> на три разных толстых дерева одного и того же ранга <tex>i</tex> и возвращает указатель на вновь сформированное дерево ранга <tex>i+1</tex> .
Процедура заключается в выполнении следующего псевдокода:
<code>
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;
</code>
==Счетчик нарушений==
