Алгоритм на псевдокоде
BL (p: pVertex, Уменьшение: boolean)
IF (p→Bal = -1) p→Bal := 0
ELSEIF (p→Bal = 0) p→Bal := 1, Уменьшение := ЛОЖЬ
ELSEIF (p→Bal = 1)
IF (p→Left→Bal ≥ 0) <RR1-поворот>
ELSE <RL - поворот> FI
FI
Рисунок 46 Три случая при удалении вершины из левого (для BL) поддерева
Алгоритм на псевдокоде
BR (p: pVertex, Уменьшение: boolean)
IF (p→Bal = 1) p→Bal := 0
ELSEIF (p→Bal = 0) p→Bal := -1, Уменьш := ЛОЖЬ
ELSEIF (p→Bal = -1)
IF (p→Left→Bal ≤ 0) <LL1 - поворот>
ELSE <LR - поворот> FI
FI
Рисунок 47 Три случая при удалении вершины правого (для BR) поддерева
При добавлении вершины не может быть случая, когда p→left→Bal = 0, поэтому LL – поворот необходимо изменить, чтобы учесть эту ситуацию.
Алгоритм на псевдокоде
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 поддерева, т. е. заменяет её на самую правую вершину из левого поддерева.
Дата добавления: 2022-02-05; просмотров: 268;