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