Структуры данных и модели вычислений
к корню дерева, для каждого
Рис. 5.11.
Следуем от узла к корню дерева, для каждого узла этого пути восстанавливаем свойство левизны и ранг. Сначала проверяем узел : его детей надо поменять местами, так как ранг узла с ключом
(он равен ) меньше ранга узла с ключом (он равен ). После этого обновляется ранг узла : он равен рангу правого сына плюс , то есть . Получилось дерево, изображенное на рис. 5.12.
Рис. 5.12.
Следующий узел на пути к корню — это родитель узла
с ключом, равным 2. Ранги его сыновей равны, значит менять их местами не нужно. Однако его собственный ранг, возможно, требует обновления, новое значение равно рангу его правого сына плюс 1, т.е. старому: . В результате получается дерево, изображенное на рис. 5.13.
Рис. 5.13.
Поскольку узел с ключом является корнем дерева, операция УДАЛЕНИЕ завершена.
Реализация операции УДАЛЕНИЕ
Операция УМЕНЬШИТЬ_КЛЮЧ. Ключ узла , находящегося в дереве в позиции , уменьшается на положительное число . Это действие может нарушить кучеобразный порядок лишь таким образом, что уменьшенный ключ узла будет меньше ключа его родителя. Уменьшение ключа может быть проведено в несколько этапов.
От исходной кучи отрывается подкуча с корнем в узле . Оставшаяся куча не обязательно будет левосторонней. Затем ключ узла уменьшается на заданное число . Куча при этом все еще остается левосторонней.
В куче восстанавливается свойство левизны, как — показано далее. Фактически свойству левизны могут не удовлетворять только узлы, находящиеся на пути от ( — родитель узла ) до корня . Длина этого пути в худшем случае линейно зависит от . Но на самом деле нам нужно проверить только первые не более чем узлов на этом пути. Наконец, куча сливается с за время . Таким образом, время выполнения данной операции — .
Рассмотрим пример. Пусть в куче, изображенной на рис. 5.14, необходимо уменьшить ключ узла от
до .
Рис. 5.14.
Делается это следующим образом. От исходной кучи отрывается подкуча с корнем в удаляемом узле . Теперь куча не является левосторонней, так как в узле нарушено свойство левизны (рис. 5.15).
