497
правок
Изменения
→Счетчик нарушений
==Счетчик нарушений==
Заметим, что '''счетчик нарушений''' очень похож на '''корневой счетчик''' выше, но в отличие от второго:
*Нас теперь интересует не само число, а только значения разрядов.
*Операция фиксации тесно связана с толстой кучей.
Значение <tex>i</tex>-го разряда для счетчика нарушений интерпретируется как количество неправильных узлов ранга <tex>i</tex> , а его списочная часть — это указатели на неправильные узлы ранга <tex>i</tex> .
'''Счетчик нарушений''' состоит из расширенного избыточного двоичного представления и набора списочных элементов.
'''Счетчик нарушений''' представлен [[Саморасширяющийся массив|Саморасширяющимся массивом]], элементы которого состоят из четырех полей:
*<tex>CountViolation[i].Value</tex> {{---}} количество неправильных узлов ранга <tex>i</tex> в куче.
*<tex>CountViolation[i].SecondViolation</tex> {{---}} указатель на неправильный узел ранга <tex>i</tex>
{{Утверждение
|proof=
}}
Для '''инициализации''' нового звена в счетчике нарушений необходимо лишь занулить его значение в новом разряде. Делается это только тогда, когда мы вводим в кучу новое дерево ранга <tex>MaxRank + 1</tex>. Это первый момент появления в куче узла ранга <tex>MaxRank + 1</tex>. Для тех нарушений, которые могут возникнуть в узлах ранга меньше либо равного <tex>MaxRank + 1</tex>, соответствующие разряды счетчика нарушений уже инициализированы, а узлов большего ранга в куче пока нет.
=Основные операции=
