Приложение А
Function max(a, b : THeight) : THeight ; { функция вычисления максимума }
begin if( a>b) then max:=a else max := b end ;
Procedure GetNewHeight( q : lpList) ;
{ функция вычисления изменившейся}
var a, b : THeight ; { высоты поддерева }
begin
if( q^.left <> nil) then a := q^.left^.height else a := 0 ;
if( q^.right <> nil) then b := q^.right^.height else b := 0 ;
q^.height := max(a, b) + 1 ;
end ;
Function GetBallance( q : lpList) :
ShortInt ; {вычисление разницы высот }
var a, b : THeight ; { левого и правого потомков узла}
begin
if( q^.left <> nil) then a := q^.left^.height else a := 0 ;
if( q^.right <> nil) then b := q^.right^.height
else b := 0 ;
GetBallance := b – a ;
end ;
Procedure Ballance( var
q : lpList) ; { собственно балансировка}
var bal : ShortInt ;
old_height : LongInt ;
begin
old_height := q^.height ; { сохранение высоты для последующего сравнения}
GetNewHeight( q) ; { вычисление новой высоты, учитывая изменения}
bal := GetBallance( q) ;
{ вычисление разницы высот}
if( bal > 1) then begin { правое поддерево выше допустимого уровны}
if( GetBallance(q^.right) < 0) then TurnLL( q^.right) ;
TurnRR( q) ;
{ выполняется правый поворот с предшествующей проверкой на наличие узла для заимствования}
if( q^.height = old_height) then h := false ; { сбрасывание флага}
end else
if( bal < – 1)then begin { левое поддерево выше допустимого}
if( GetBallance(q^.left) > – 0) then
TurnRR( q^.left) ;
TurnLL( q) ;
{ выполняется правый поворот с предшествующей проверкой на наличие узла для заимствования}
if( q^.height = old_height) then h := false ; {сброс флага}
end ;
end ;
Приложение Б
Procedure Insert( x : LongInt ; var q : lpList) ;
Var t1, t2 : lpList ;
Bal : ShortInt ;
Begin
If( q = nil) then begin {место для вставки узла найдено}
new(q) ;
with q^ do begin
value := x ;
left := nil ;
right := nil ;
height := 1 ;
end ;
End
else
If x < q^.value then { новый узел должен принадлежать }
Insert( x, q^.left) { левому поддереву данного узла }
Else Insert( x, q^.right) ; { или правому }
End ;
Приложение В
Procedure Insert( x : Byte ; var
q : lpList) ;
var t1, t2 : lpList ;
bal : ShortInt ;
begin
if( q = nil) then begin
new(q) ;
h := true
;
with Q^ do
begin
value := x ;
left := nil ;
right := nil ;
height := 1 ;
end ;
end else
if x < q^.value then begin
Insert( x, q^.left) ;
if( h) then Ballance( q) ;
end else
begin
Insert( x, q^.right{, h}) ;
if( h) then Ballance( q) ;
end ;
end ;
Приложение Г
Procedure Search( x : Integer ; var
p : ref ; var
h : boolean) ;
Var p1, p2 : ref ;
Begin
If( p = nil) then begin
New(p) ; h := true ;
With p^ do
begin
Key := x ;
Count := 1 ;
Left := nil ;
Right := nil;
Bal := 0 ;
End
End else
If( x < p^.key) then begin
Search( x, p^.left, h) ;
If( h) then
Case p^.bal of
1 : begin p^.bal := 0 ; h := false end ;
0 : p^.bal := – 1 ;
- 1:
begin p1 := p^.left ;
if p1^.bal = – 1 then
begin
p^.left:=p1^.right; p1^.right:=p;
p^.bal := 0 ;
p := p1 ;
end else begin p2 := p1^.right;
p1^.right := p2^.left ; p2^.left:=p1 ;
p^.left:=p2^.right; p2^.right := p ;
if p2^.bal=-1 then p^.bal:=1 else p^.bal:=0;
if p2^.bal=1 then p1^.bal:=-1 else p1^.bal:=0;
p := p2 ;
end ;
p^.bal := 0 ; h := false ;
end ;
end ;
end else
if x > p^.key then begin
search(x, p^.right, h) ;
If( h) then
Case p^.bal of
- 1:
begin p^.bal := 0 ; h := false
end ;
0 : p^.bal := 1 ;
1 : begin p1 := p^.right ;
if p1^.bal = 1 then begin
p^.right:=p1^.left; p1^.left:=p;
p^.bal := 0 ;
p := p1 ;
end else begin p2 := p1^.left;
p1^.left:= p2^.right; p2^.right:=p1 ;
p^.right:=p2^.left; p2^.left := p ;
if p2^.bal=1 then p^.bal:=-1 else p^.bal:=0;
if p2^.bal=-1 then p1^.bal:=1 else p1^.bal:=0;
p := p2 ;
end ;
p^.bal := 0 ; h := false ;
end ;
end ;
end else begin p^.count := p^.count + 1 ; h := false end ;
End ;
Приложение Д
If( x < p^.key) then begin
Search( x, p^.left, h) ;
If( h) then
Case p^.bal of
1 : begin p^.bal := 0 ; h := false
end ;
0 : p^.bal := – 1 ;
- 1:
begin p1 := p^.left ;
if p1^.bal = – 1 then
begin
p^.left:=p1^.right; p1^.right:=p;
p^.bal := 0 ;
p := p1 ;
end else begin p2 := p1^.right;
p1^.right := p2^.left ; p2^.left:=p1 ;
p^.left:=p2^.right; p2^.right := p ;
if p2^.bal=-1 then p^.bal:=1 else p^.bal:=0;
if p2^.bal=1 then p1^.bal:=-1 else p1^.bal:=0;
p := p2 ;
end ;
p^.bal := 0 ; h := false ;
end ;
end ;
Похожие статьи
- формирование штат расписания
- безэквивалентная лексика лингвистика
- квитовка платежа
- теорема дирихле
- ритмичность продаж