Алгоритм на псевдокоде. IF (q→Bal = 0) p→Bal := -1, q→Bal := 1, Уменьш := false

LL1 – поворот

q:= p→Left

IF (q→Bal = 0) p→Bal:= -1, q→Bal:= 1, Уменьш:= false

ELSE p→Bal:= 0, q→Bal:= 0

p→Left:= q→Right

q→Right:= p

p:= q

Аналогично изменяется RR – поворот, LR и RL – повороты не изменяются.

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

RR1 – поворот

q:= p→Right

IF (q→Bal = 0) p→Bal:= 1, q→Bal:= -1, Уменьшение:= ЛОЖЬ

ELSE p→Bal:= 0, q→Bal:= 0

FI

p→ Right:= q→ Left

q→ Left:= p

p:= q

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

Удаление из АВЛ-дерева (x: Данные, p: pVertex, Уменьшение: boolean)

IF (p = NIL) {ключа в дереве нет}

ELSE IF (p→Data > x) Удаление (x, p→Left, Уменьшение)

IF Уменьшение BL (p, Уменьш) FI

ELSE IF (p→Data < x) Удаление (x, p→Right, Уменьшение)

IF Уменьшение BR (p, Уменьшение) FI

ELSE IF {удаление вершины по адресу p}

q:= p

IF (q→Right = NIL) p:= q→Left, Уменьшение:= ИСТИНА

ELSE IF (q→Left = NIL) p:= q→Right, Уменьшение:= ИСТИНА

ELSE del (q→Left, Уменьшение)

IF Уменьшение BL (p, Уменьшение) FI

FI

dispose(q)

FI

Используемая при удалении процедура del удаляет вершину, имеющую 2 поддерева, т. е. заменяет её на самую правую вершину из левого поддерева.


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



double arrow
Сейчас читают про: