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