Метод определения высоты бинарного дерева

Дерево
поиска называется АВЛ
– деревом,
если для каждой его вершины высоты
левого и правого поддеревьев отличаются
не более чем на 1.

Авл – дерево

Высота
AVL-деревьев оценивается сверху
логарифмически в зависимости от числа
вершин: h hR, то баланс нарушиться и дерево необходимо перестраивать.

Введём
в каждую вершину дополнительный параметр
Balance
(показатель баланса), принимающий
следующие значения: -1, если левое
поддерево на единицу выше правого;0,
если высоты обоих поддеревьев одинаковы;1,
если правое поддерево на единицу выше
левого.

eToro - Popular Investor

Если
в какой-либо вершине баланс высот
нарушается, то необходимо так перестроить
имеющееся дерево, чтобы восстановить
баланс в каждой вершине. Для восстановления
баланса будем использовать процедуры
поворотов АВЛ-дерева.

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

LL
– поворот

q
:= p→Left

q→Balance
:= 0

p→Balance
:= 0

p→Left
:= q→Right

q→Right
:= p

p
:= q

LR
– поворот

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

LR
– поворот

q
:= p→Left,
r
:= q→Right

IF
(r→Balance0) q→Balance := –1 ELSE q→Balance := 0 FI

r→Balance
:= 0

p→Left
:= r→Right, q→Right := r→Left

r→Left
:= q, r→Right := p, p := r

RR
– поворот

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

RR
– поворот

q
:= p→Right

q→Balance
:= 0

p→Balance
:= 0

p→
Right:= q→ Left

q→
Left := p

p:= q

RL
– поворот

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

RL
– поворот

q
:= p→ Right, r := q→ Left

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

IF
(r→Balance

Метод определения высоты бинарного дерева – Видео