Изменения

Перейти к: навигация, поиск

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

54 байта добавлено, 22:10, 10 апреля 2016
Счетчик нарушений
'''Счетчик нарушений''' представлен [[Саморасширяющийся массив|саморасширяющимся массивом]], элементы которого состоят из четырех полей:
*<tex>\mathtt{countViolation[i].Value}</tex> {{---}} количество неправильных узлов ранга <tex>i</tex> в куче.*<tex>\mathtt{countViolation[i].forvardPointer}</tex> {{---}} прямой указатель <tex>i</tex>-го разряда*<tex>\mathtt{countViolation[i].firstViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>*<tex>\mathtt{countViolation[i].secondViolation}</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
{{Утверждение
}}
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>maxRank + 1</tex>. Это первый момент появления в куче узла ранга <tex>\mathtt{maxRank + 1}</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>\mathtt{maxRank + 1}</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
==Основные операции==
635
правок

Навигация