Структуры данных и модели вычислений



             

Вспомогательные процедуры - часть 2


Сделать это предлагается заменой поддерева с корнем в нарушенном узле, чей родитель имеет меньший ключ, на поддерево с корнем в -ранговом брате нарушаемого узла, чей родитель имеет больший ключ. Легко убедиться, что такая замена не приводит к созданию новых нарушений. Пусть узел — общий родитель двух нарушаемых узлов после замены — принадлежит дереву .

Разобьем дальнейшее рассмотрение на два случая:

  1. Ранг равен . Пусть и — это толстые деревья ранга с корнями в двух нарушаемых узлах, а дерево — толстое дерево ранга , полученное из поддерева с корнем в узле

    удалением поддеревьев и .

    • Если узел не является корнем дерева , то удаляем из дерева

      поддерево . Из трех толстых деревьев ) ранга образуем одно дерево ранга , чей корень является узлом с наименьшим ключом среди корней деревьев . Вставляем в дерево вновь полученное толстое дерево с корнем в узле вместо поддерева с корнем в узле . Если узел оказывается нарушенным, инкрементируем . Значение -го разряда делаем нулевым.

    • Если узел — корень дерева , то удаляем дерево из кучи. Из трех толстых деревьев

      ранга образуем одно дерево ранга , чей корень является узлом с наименьшим ключом среди ключей корней деревьев . Вставляем вновь полученное толстое дерево с корнем в узле

      в кучу. Значение -го разряда делаем нулевым.

  2. Если ранг больше, чем , то, по условию регулярности счетчика нарушений, узел должен иметь хотя бы одного сына ранга , который не является -ранговым нарушением, и два -ранговых сына должны быть также ненарушенными. Тогда заменяем два нарушенных -ранговых сына узла на два хороших -ранговых сына узла . Тем самым мы свели задачу к случаю 1.

Можно доказать, что рассматриваемая операция не испортит регулярности счетчика.

Инкрементирование i-го разряда счетчика нарушений . Используя описанную выше операцию фиксации, можно осуществить инкрементирование -го разряда счетчика нарушений следующими операторами:

Трудоемкость операции .

Удаление нарушения из кучи. Заметим, что удаление нарушения из кучи подразумевает наличие в куче этого нарушения; пусть это нарушение ранга .Тогда значение -го разряда для счетчика нарушений не равно нулю. Следовательно, уменьшение этого значения на единицу не испортит регулярности и не потребует обновления каких-либо указателей. Необходимо лишь уменьшить на единицу значение переменной и обработать указатели и . Очевидно, что трудоемкость этой операции .

Нахождение узла с минимальным значением ключа среди всех нарушений. Для реализации этой функции предлагается перебрать все нарушения до максимального ранга и найти среди них узел с минимальным весом. Трудоемкость данной операции .




Содержание  Назад  Вперед