497
правок
Изменения
→Корневой счетчик
p1 := p1.Right;
MinKeyNodeRoot := MinP;
</code>
===Операция фиксации <tex>rmFixRootCount(i)</tex>===
Операция фиксации <tex>i</tex>-го разряда корневого счетчика подразумевает, что его значение равно трем, а списочная часть содержит указатель на список деревьев ранга <tex>i</tex>, состоящий ровно из трех деревьев. При выполнении этой операции значение в <tex>i</tex>-м разряде — должно стать равным нулю, а значение в <tex>i</tex>-м разряде увеличиться на единицу. То есть в куче не должно остаться деревьев ранга <tex>i</tex>, а количество деревьев ранга <tex>i+1</tex> должно увеличиться на единицу. Для этого следует удалить из кучи три присутствующих в ней дерева ранга <tex>i</tex> , связать их в дерево ранга <tex>i+1</tex> и вставить вновь полученное дерево в кучу.
Следует учесть, что ранг нового дерева может стать больше, чем <tex>MaxRank</tex>, что потребует инициализации нового разряда. Для этого необходимо увеличить значение <tex>MaxRank</tex> на единицу и заполнить новое поле, а также провести инициализацию нового разряда.
<code>
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;
</code>
===Инкрементирование i-го разряда корневого счетчика <tex>rm IncRootCount(i,p)</tex>===
Здесь мы должны учесть работу со списочной частью и обновить прямые указатели.
<code>
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);
</code>
===удаление дерева из кучи===
Процедура удаления дерева из кучи подразумевает наличие в куче этого дерева. Пусть удаляемое дерево имеет ранг . Тогда значение -го разряда избыточного корневого представления не равно нулю. То есть уменьшение этого значения на единицу не испортит регулярности представления и не потребует обновления каких-либо указателей. Необходимо лишь соответствующим образом обработать списочную часть.
<code>
DeleteTree(i,p);
RootCount[i].Value := RootCount[i].Value -1;
</code>
===Нахождение дерева с минимальным ключом в корне (<tex>MinKey</tex>)===
<code>
MinP := NULL;
for(i := 0 to MaxRank) do
p1:=MinKeyNodeRoot(RootCount[i].ListPointer);
if(GetKey(p1)<GetKey(MinP))
MinP := p1;
MinKey := MinP;
</code>
