|
<![CDATA[
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 );
Rots := Rots-1;
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 );
Rots := Rots-1;
checkrots( left ); checkrots( right )
end
end
end
end;
procedure insert( key : typekey; var t : tree );
begin
if t = nil then begin
t := NewNode( key, nil, nil );
t^.weight := 2
end
else if t^.k = key then
i:=i-1
else with t^ do begin
if k < key then insert( key, right )
else insert( key, left );
weight := wt( left ) + wt( right );
checkrots( t )
end
end;
]]> |
Pascal source (3415.ins.p) 