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

АЛГОРИТМ ПРОЦЕДУРЫ 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;