Включение элементов в AVL-дерево

Бинарные деревья поиска

Бинарное дерево представляет собой упорядоченную тройку (, , ),

где – корневая вершина,

и – левое и правое поддеревья соответственно.

 

Общее число вершин составляет .

 

Бинарное дерево может быть организовано в виде упорядоченного связанного последовательного файла. Наличие дополнительного указателя в каждой хранимой записи облегчает быстрый поиск. Операции включения и удаления выполняются достаточно быстро, т.к. изменяются только значения указателей и не требуется выполнять перераспределение памяти.

Представление бинарного дерева:,

где

INFO – информационное поле,

LLINK – указатель на левое поддерево,

RLINK – указатель на правое поддерево.

 

Понятие баланса

 

Дерево называется сбалансированным, если разница уровней любых двух листьев не превышает единицы.

 

 

Более жёстким определением баланса является идеально-сбалансированное дерево – дерево, у которого для каждого узла количество узлов в левом и правом поддеревьях различается не более, чем на единицу.

 

Когда равновероятно обращение к любой из вершин, использование сбалансированного дерева минимизирует среднюю длину пути до идентификатора. По этой причине важно научиться конструировать сбалансированные деревья.

Для изменчивых баз данных была предложена ещё одна возможность организации бинарного дерева поиска с менее строгим определением баланса – AVL-дерево (дерево, сбалансированное по высоте).

 

AVL-дерево

 

AVL-дерево было предложено Г.М. Адельсоном-Вельским и Е.М. Ландисом в 1962 году.

 

Дерево с вершинами называется сбалансированным по высоте, если для любой вершины разница высот её левого и правого поддеревьев не превышает единицы ().

 

 

 

Как уже отмечалось, это определение баланса является менее строгим в сравнении с идеально-сбалансированным деревом, но оно приводит к легко выполнимой балансировке, а средняя длина пути до идентификатора остается практически такой же, как и у идеально-сбалансированного дерева.

Представление AVL-дерева:,

 

где

INFO – информационное поле,

LLINK – указатель на левое поддерево,

RLINK – указатель на правое поддерево,

BAL – поле, отражающее разность высот левого и правого поддеревьев для этой вершины:

.

Поскольку AVL-дерево представляет практический интерес, целесообразно рассмотреть наиболее типичные операции, такие как включение и удаление элементов из AVL-дерева.

 

Включение элементов в AVL-дерево

 

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

Возможны три исходных случая:

1. : и становятся неравной высоты, но критерий сбалансированности не нарушается.

2. : и приобретают равную высоту, т.е. баланс становится даже лучше.

3. : критерий сбалансированности нарушается, и дерево необходимо перестроить.

 

Алгоритм балансировки

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

Обозначим для удобства баланс в вершине «++», если он равен 2, «- -» – если равен -2 и «» – если баланс равен 0.

1. «Одинарное вращение»

 

a) (RR)

 

b) (LL)

 

 

 

2. «Двойное вращение»

 

2.1. (RL), узел имеет баланс «+2», узел – «-1»

a) (RL), узел изначально имеет баланс 0:

 

 

b) (RL), узел изначально имеет баланс -1:

 

 

c) (RL), узел изначально имеет баланс +1:

 

 

 

2.2. (RL), узел имеет баланс «-2», узел – «+1»

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

 

Таким образом, необходимые операции балансировки заключаются полностью в обмене значениями соответствующих ссылок. Фактически ссылки обмениваются «по кругу», что приводит к однократному или двукратному повороту двух или трёх узлов соответственно. Кроме «вращения» ссылок следует также пересчитать показатели сбалансированности узлов.

 

Пример: