Структуры данных и модели вычислений
Вспомогательные процедуры
- Процедура обновления прямого указателя -го разряда счетчика нарушений аналогична процедуре
для корневого счетчика. Необходимо лишь учесть, что счетчик нарушений — двоичный.
- Процедура корректировки списочной части -го разряда счетчика нарушений при появлении в куче нового -рангового нарушения — назовем ее
— вставляет новый нарушенный узел, обновляя, в зависимости от значения , либо первый , либо второй указатель. Причем перед тем как вставлять в счетчик новое нарушение, необходимо проверить, не присутствует ли оно там.
- Процедура взаимной замены поддеревьев кучи с корнями в узлах и — назовем ее — подразумевает, что ранги обмениваемых деревьев одинаковы.
- Также нам необходима функция , которая возвращает указатель на брата того же ранга, что и передаваемый ей узел. Она проверяет ранги своего правого и левого братьев (если такие существуют) и возвращает указатель на брата того же ранга (он существует обязательно).
- Функция, которая связывает три толстых дерева ранга в одно толстое дерево ранга , аналогична соответствующей функции для корневого счетчика.
- Функция, которая возвращает указатель на минимальный нарушенный узел ранга среди элементов -го разряда счетчика нарушений. Если -й разряд счетчика нарушений пуст, то возвращается .
Как и в случае корневого счетчика, все операции выполняются за константное время.
Свойство регулярности. Определим свойство регулярности для счетчика нарушений. Назовем состояние счетчика нарушений регулярным, если между любыми двумя цифрами, равными двум, существует цифра, отличная от единицы. Неправильный узел ранга в дальнейшем будем называть -ранговым нарушением.
Операция фиксации. Фиксация -й цифры
соответствует либо преобразованию двух -ранговых нарушений в одно -ранговое нарушение, либо устранению обоих -ранговых нарушений. Проводить эту операцию предлагается следующим образом.
Упорядочиваем два -ранговых нарушения так, чтобы они имели одного родителя (очевидно, что в общем случае -ранговые нарушения могут иметь разных родителей).
