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




Операции с левосторонними кучами - часть 4



Рис. 5.11. 

Следуем от узла к корню дерева, для каждого узла этого пути восстанавливаем свойство левизны и ранг. Сначала проверяем узел : его детей надо поменять местами, так как ранг узла с ключом

(он равен ) меньше ранга узла с ключом (он равен ). После этого обновляется ранг узла : он равен рангу правого сына плюс , то есть . Получилось дерево, изображенное на рис. 5.12.


Рис. 5.12. 

Следующий узел на пути к корню — это родитель узла

с ключом, равным 2. Ранги его сыновей равны, значит менять их местами не нужно. Однако его собственный ранг, возможно, требует обновления, новое значение равно рангу его правого сына плюс 1, т.е. старому: . В результате получается дерево, изображенное на рис. 5.13.


Рис. 5.13. 

Поскольку узел с ключом является корнем дерева, операция УДАЛЕНИЕ завершена.

Реализация операции УДАЛЕНИЕ

Операция УМЕНЬШИТЬ_КЛЮЧ. Ключ узла , находящегося в дереве в позиции , уменьшается на положительное число . Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ узла будет меньше ключа его родителя. Уменьшение ключа может быть проведено в несколько этапов.

От исходной кучи отрывается подкуча с корнем в узле . Оставшаяся куча не обязательно будет левосторонней. Затем ключ узла уменьшается на заданное число . Куча при этом все еще остается левосторонней.

В куче восстанавливается свойство левизны, как — показано далее. Фактически свойству левизны могут не удовлетворять только узлы, находящиеся на пути от ( — родитель узла ) до корня . Длина этого пути в худшем случае линейно зависит от . Но на самом деле нам нужно проверить только первые не более чем узлов на этом пути. Наконец, куча сливается с за время . Таким образом, время выполнения данной операции — .

Рассмотрим пример. Пусть в куче, изображенной на рис. 5.14, необходимо уменьшить ключ узла от

до .


Рис. 5.14. 

Делается это следующим образом. От исходной кучи отрывается подкуча с корнем в удаляемом узле . Теперь куча не является левосторонней, так как в узле нарушено свойство левизны (рис. 5.15).




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