Алгоритм на псевдокоде

Добавление в АВЛ – дерево (D: данные; Var p: pVertex);

Обозначим

Рост – логическая переменная, которая показывает выросло дерево или нет.

IF (p = NIL)

new(p), p→Data := D, p→Left := NIL, p→Right := NIL

p→Balance := 0, Рост := ИСТИНА

ELSE

IF (p→Data > D)

Добавление в АВЛ – дерево (D, p→Left)

IF (Рост = ИСТИНА) {выросла левая ветвь}

IF (p→Balance > 0) p→Balance := 0, Рост := ЛОЖЬ

ELSE IF (p→Balance = 0) p→Balance := -1

ELSE

IF (p→Left→Balance < 0) <LL – поворот>

ELSE <LR – поворот> Рост := ЛОЖЬ

FI

FI

ELSE IF (p→Data < D)

<аналогичные действия для правого поддерева

ELSE {p→Data = D, такая вершина уже есть}

FI

FI

FI

Пример: Построение АВЛ-дерева с вершинами B 9 2 4 1 7 E F A D C 3 5 8 6

Рисунок 45 Построение АВЛ-дерева

12.4 Удаление вершины из дерева

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

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

Как и в случае добавления вершин, введём логическую переменную Уменьшение, показывающую уменьшилась ли высота поддерева. Балансировка идёт, только если Уменьшение = истина. Это значение присваивается переменной Уменьшение, если обнаружена и удалена вершина или высота поддерева уменьшилась в процессе балансировки.

Введём две симметричные процедуры балансировки, т. к. они будут использоваться несколько раз в алгоритме удаления:

BL – используется при уменьшении высоты левого поддерева,

BR – используется при уменьшении высоты правого поддерева.

Рисунки 46 и 47 иллюстрируют три случая, возникающие при удалении вершины из левого (для BL) или правого (для BR) поддерева, в зависимости от исходного состояния баланса в вершине по адресу p.