Главная

Популярная публикация

Научная публикация

Случайная публикация

Обратная связь

ТОР 5 статей:

Методические подходы к анализу финансового состояния предприятия

Проблема периодизации русской литературы ХХ века. Краткая характеристика второй половины ХХ века

Ценовые и неценовые факторы

Характеристика шлифовальных кругов и ее маркировка

Служебные части речи. Предлог. Союз. Частицы

КАТЕГОРИИ:






Вставка элемента в АВЛ-дерево




Операция включения элемента а АВЛ-дерево выполняется в два этапа. Поскольку сбалансированное дерево является частным случаем обычного дерева поиска, то на первом этапе выполняется включение элемента в дерево точно так же, как и при включении в обычное дерево: проходом по пути поиска, получением динамической памяти и формированием в ней новой вершины дерева. Дополнительно новой вершине устанавливается признак ее сбалансированности, равный 0, т.к. новая вершина не имеет поддеревьев. Второй этап выполняется при обратном движении по дереву и заключается в восстановлении сбалансированности в узлах дерева, если она была нарушена. При этом учитывается, откуда (слева или справа) осуществляется возврат в вершину, каков показатель сбалансированности в ней, выросла ли высота поддерева. Возникающие ситуации и особенности восстановления сбалансированности рассмотрим на примерах.

Пусть имеется дерево с вершинами 3 и 2 (рис. 32, первое дерево). Высота левого поддерева вершины 3 равна 1, высота правого поддерева вершины 3 равна 0, сбалансированность У вершины 2 Добавим вершину 1, у нее Возвращаемся в вершину 2, теперь у нее но критерий сбалансированности поддерева соблюдается. В вершине 3 стало т.е. критерий сбалансированности нарушен и дерево нужно перестраивать (среднее дерево на рис. 32). Это достигается однократным LL-поворотом, в результате получаем сбалансированное дерево с вершиной 2 (правое дерево на рис. 32). Необходимые операции балансировки заключаются в обмене указателями и Т по кругу по часовой стрелке. Кроме этого, необходимо изменить показатели сбалансированности вершин.

Рис. 32 – Вставка элемента в АВЛ-дерево и его балансировка

LL-поворотом

 

Теперь в дерево с вершинами 4 и 5 включим вершину 6. Для балансировки в вершине 4 выполняются RR-поворот, обмен указателями по кругу против часовой стрелки (рис. 33).

Более сложные ситуации приводят к двукратным поворотам: направо и налево – RL-поворот; налево и направо – LR-поворот. Пример двукратного RL-поворота демонстрируется включением в дерево с вершинами 5 и 7 новой вершины 6 (рис. 34). Возникла несбалансированность в вершине 5. Поэтому вначале выполняется правый поворот трех вершин, затем левый поворот двух вершин (7 и 6).

 

Рис. 33 – Вставка элемента в АВЛ-дерево и его балансировка

RR-поворотом

 

Рис. 34 – Вставка элемента в АВЛ-дерево и его балансировка RL-поворотом

 

При включении в дерево с вершинами 9 и 3 новой вершины 8 возникает несбалансированность поддерева с корнем. Она устраняется двукратным LR-поворотом: сначала левым поворотом трех вершин, а затем правым поворотом двух вершин – 3 и 8 (рис. 35).

Рис. 35 – Вставка элемента в АВЛ-дерево и его балансировка

LR-поворотом

 

Порядок построения сбалансированного дерева из набора элементов с ключами: 4, 5, 7, 2, 1, 3, 6, показан на рисунке 36.

 

Рис. 36 – Порядок построения сбалансированного дерева

 

Обработка данных в вершине дерева. Различают два вида обработки: выборочную обработку отдельной вершины и последовательную обработку всех вершин. Выборочная обработка включает поиск элемента, и если он найден, то обработку данных в вершине. Обработка данных зависит от решаемой задачи и может сводиться к извлечению данных без их изменения либо обновлению данных в вершине дерева. При последовательной обработке осуществляется обход дерева.

Удаление элемента из дерева. Особенности операции удаления зависят от вида дерева. Операция удаления из дерева поиска сложнее, чем операция добавления элемента в него. После удаления элемента дерева поиска должно сохранить свое главное свойство – обеспечение поиска оставшихся в нем элементов. Действия по удалению определяются тем, в каком месте дерева находится удаляемый элемент. В процедуре удаления различают следующие ситуации.

1. Элемента с искомым ключом нет, дерево не изменяется, возврат с признаком отсутствия ключа.

2. Удаляемый элемент – лист, в родительском узле указатель на удаляемый элемент обнуляется, память из-под элемента освобождается.

3. Удаляемый элемент только с одним указателем. Указатели корректируются, память освобождается.

4. Удаляемый элемент имеет два поддерева. В этом случае необходимо спуститься вдоль самой правой ветви левого поддерева до конца и изменить удаляемый элемент конечным элементом с корректировкой указателей. Память освобождается. Вместо этого можно спуститься до конца дерева вдоль самой левой ветви правого поддерева и заменить удаляемый элемент конечным элементом, скорректировать указатели и освободить память.

На рис. 37 показан пример удаления из дерева поиска узла с ключом 13, имеющим два поддерева. Узел 13 заменен узлом 10. Если бы спускались по левой ветви правого поддерева, то узел 13 был бы заменен узлом 14.

 

Рис. 37 – Удаление элемента из БД поиска

 

В случае удаления элемента из сбалансированного АВЛ-дерева поиска дополнительно выполняется балансировка дерева, если сбалансированность была нарушена в результате удаления элемента. Это может произойти из-за уменьшения высоты дерева.

Сохранение и восстановление дерева. Выполняется нисходящий обход дерева с сохранением ключа и данных каждого узла. Указатели сохранять не требуется. По сохраненным ключам и данным узлов строится БД.

Уничтожение дерева. Для уничтожения БД достаточно выполнить обход дерева и при посещении каждого узла освободить занимаемую им память. При этом нельзя допускать, чтобы был уничтожен узел, имеющий поддеревья, т.к. занятая им память не будет освобождена и станет недоступной для повторного использования. Это требования обеспечивается при восходящем обходе дерева. После освобождения всей занятой памяти указатель дерева необходимо обнулить.

Лекция 13

План лекции:

1. Основные определения ориентированных графов.

2. Представление ориентированных графов.

3. Операторы над ориентированными графами.

4. Нахождение кратчайшего пути на ориентированном графе.

5. Нахождение кратчайших путей между парами вершин

 






Не нашли, что искали? Воспользуйтесь поиском:

vikidalka.ru - 2015-2024 год. Все права принадлежат их авторам! Нарушение авторских прав | Нарушение персональных данных