Алгоритм процедуры balance_l

Дано: бинарное дерево, в левом поддереве которого было произведено удаление элемента.

Задан: указатель p на место удаленного элемента.

Алгоритм производит балансировку бинарного дерева и корректировку показателей сбалансированности.

P1 и P2 - вспомогательные указатели, b1 и b2 - вспомогательные показатели сбалансированности.

_Начало. Balance_L:

1. Корректировка показателей сбалансированности:

_Если. BAL(p)=-1

_то.: BAL(p)=0; { перевеш. -> сбалансир. }

_конец

_Если. BAL(p)=0

_то.: BAL(p)=1; h=false; { сбалансир. -> перевеш. }

_конец

p1=RPTR(p); b1=BAL(p1); { BAL(p)=1 - критическая. }

2. Однократный RR-поворот:

_Если. b1 >= 0

_то.:

_Если. p=ROOT _то. ROOT=RPTR(p); _.{ перенос корня }

RPTR(p)=LPTR(p1); LPTR(P1)=p;

{ корректировка показателей сбалансированности }

_если. b1=0

_то.: BAL(p)=1; BAL(p1)=-1; h=false;

_иначе.: BAL(p)=0; BAL(p1)=0;

p=p1;

_конец

2. Двукратный RL-поворот:

_если. b1 < 0

_если. p1=ROOT _то. ROOT=RPTR(p); { перенос корня }

p2=LPTR(p1); b2=BAL(p2);

LPTR(p1)=RPTR(p2); RPTR(p2)=p1;

RPTR(p)=LPTR(p2); LPTR(p2)=p;

{ корректировка показателей сбалансированности }

_если. b2=1 _то. BAL(p)=-1 _иначе. BAL(p)=0;

_если. b2=-1 _то. BAL(p1)=1 _иначе. BAL(p1)=0;

p=p2; BAL(p2)=0;

_конец

_Конец. Balance_L;

ОПИСАНИЕ РАБОТЫ АЛГОРИТМА:

· П.1 - если вершина не является критической, то производится изменение показателей сбалансированности. Если вершина критическая - создаются вспомогательные указатели.

· П.2 и 3 - производят балансировку дерева однократным RR(п.2) и двукратным RL- (п.3) поворотами и изменение показателей сбалансированности.