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

Операция включения элемента а АВЛ-дерево выполняется в два этапа. Поскольку сбалансированное дерево является частным случаем обычного дерева поиска, то на первом этапе выполняется включение элемента в дерево точно так же, как и при включении в обычное дерево: проходом по пути поиска, получением динамической памяти и формированием в ней новой вершины дерева. Дополнительно новой вершине устанавливается признак ее сбалансированности, равный 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 – Удаление элемента из БД поиска

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

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

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

Дата добавления: 2015-07-16