procedure checkrots( var t : tree );
{*** check need for rotations ***}
var wl, wll, wr, wrr : integer;
begin
if t <> nil then with t^ do begin
wl := wt( left );
wr := wt( right );
if wr > wl then begin
{*** left rotation needed ***}
wrr := wt( right^.right );
if (wrr > wl) and (2*wrr >= wr) then
begin lrot( t ); checkrots( left ) end
else if wr-wrr > wl then begin
rrot( right ); lrot( t );
checkrots( left ); checkrots( right )
end
end
else if wl > wr then begin
{*** right rotation needed ***}
wll := wt( left^.left );
if (wll > wr) and (2*wll >= wl) then
begin rrot( t ); checkrots( right ) end
else if wl-wll > wr then begin
lrot( left ); rrot( t );
checkrots( left ); checkrots( right )
end
end
end
end;
|