Алгоритм вставки элемента.После того как в дерево включен новый узел (вставка элемента производится в лист), путь из корня в лист проходится в обратном направлении. Из-за того, что двоичное дерево,

42.

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

1. Если текущий узел имеет баланс 0, то он меняется на –1, если последний шаг начинается из правого поддерева, и на 1, если он начинается из левого поддерева. Мы продолжаем следовать вверх по пути до тех пор, пока текущим узлом не станет корень, и в этом случае процедура заканчивается.

2. Если текущий узел имеет баланс 1 или –1 и последний шаг начинается из более короткого из двух поддеревьев текущего узла, то баланс меняется на 0 и процедура завершается.

3. Если текущий узел имеет баланс 1 или –1 и последний шаг начинается из более высокого из двух поддеревьев текущего узла, то

(a) если при прохождении вверх по дереву последние два шага перед узлом, в котором произошла разбалансировка, осуществлялись в одном направлении (оба из левых поддеревьев или оба из правых поддеревьев), то выполняется одно вращение;

(b) если при прохождении вверх по дереву последние два шага перед узлом, в котором произошла разбалансировка, делались в разных направлениях, то выполняется двойное вращение.

В обоих случаях процедура заканчивается.

Рассмотрим пример формирования сбалансированного по высоте дерева, последовательно вставляя в изначально пустое дерево элементы k 1, k 2, k 3, k 4, k 5 значения которых соответственно равны 10, 47, 65, 99, 82 (рис. 5).

Рис. 5. Пример построения АВЛ-дерева для последовательности элементов 10, 47, 65, 99, 82. Вставляемые узлы окрашены в серый цвет, рядом с каждым узлом указан его текущий баланс

Элемент k 1 = 10 становится корнем дерева, его баланс равен 0. После вставки элемента k 2 = 47 дерево остается сбалансированным. Разбалансировка дерева происходит в узле k 1 при вставке элемента k 3 = 65. Это соответствует случаю 3 (а) и производится одно вращение относительно узла k 1 влево, после чего дерево опять становится сбалансированным.

Добавление элемента k 4 = 99 не нарушает условий сбалансированности. При вставке элемента k 5 = 82 возникает случай 3 (б). Для восстановления баланса необходимо произвести двойное вращение: сначала относительно узла k 4 вправо, а затем относительно узла k 3 влево.

Алгоритм удаления элемента. Процесс удаления элемента из двоичного дерева поиска можно описать следующим образом. Если удаляемый узел:

1) является листом (т.е. не имеет сыновей), он удаляется и далее следует процесс балансировки;

2) имеет одного сына, то у его отца указатель на него меняется на указатель на его единственного сына, а сам узел удаляется;

3) имеет двух сыновей, то в его левом поддереве ищется максимальный элемент (либо в правом – минимальный), значение удаляемого элемента заменяется значением этого найденного максимального (минимального) элемента. Далее происходит удаление узла, в котором был найден максимальный (минимальный) элемент. Этот элемент либо лист, либо имеет единственного сына, поэтому удаление происходит в соответствии с пунктами 1) или 2). При удалении элемента поддерево, из которого удалился элемент, становится короче на 1. Необходимо произвести балансировку дерева, проходя путь от этого исключенного узла вверх до корня дерева, проверяя в каждом узле, какое влияние на большее дерево может иметь укорачивание поддерева. Действие, которое предпринимается в каждом узле, расположенном на этом восходящем пути, зависит от баланса в узле до исключения, от направления последнего шага и в некоторых случаях также от баланса второго сына узла. На приведенных ниже рисунках заштрихованные участки отображают укорачивание поддерева. В некоторых случаях преобразование восстанавливает высоту поддерева до той, которая была до исключения; если это так, то алгоритм заканчивается, поскольку исключение не влияет на баланс всех расположенных выше узлов. В других случаях сведения о том, что поддерево укорачивалось, должны быть передано вверх по пути к корню. Рассмотрим возможные случаи удаления элемента. В каждом случае симметричные варианты существуют, но не приводятся.

1. Если текущий узел A имеет баланс, равный 0, то укорачивание правого (левого) поддерева не влияет на высоту всего дерева, имеющего корнем текущий узел. Баланс текущего узла меняется на 1 (или –1). Алгоритм заканчивает работу (рис. 5).

Рис. 5. Изменение баланса узла A без нарушения сбалансированности дерева

2. Если текущий узел A имеет баланс, равный 1 или –1, и удаляемый элемент находился в более высоком из двух поддеревьев текущего узла, то высота дерева с корнем в текущем узле уменьшилась на 1. Процесс продвижения вверх по дереву продолжается, и в качестве текущего узла рассматривается узел-отец. При этом учитывается тот факт, что высота поддерева уменьшилась (рис. 6).

Рис. 6. Изменение баланса узла A с необходимостью анализа балансов вышележащих узлов

Дата добавления: 2015-08-29