procedure delete( key : typekey; var t : tree );
begin
if t = nil then Error {*** key not found ***}
else begin
{*** search for key to be deleted ***}
if t^.k < key then delete( key, t^.right )
else if t^.k > key then delete( key, t^.left )
{*** key found, delete if a descendant is nil ***}
else if t^.left = nil then t := t^.right
else if t^.right = nil then t := t^.left
{*** no descendant is null, rotate on heavier side ***}
else if wt( t^.left ) > wt( t^.right ) then
begin rrot( t ); delete( key, t^.right ) end
else begin lrot( t ); delete( key, t^.left ) end;
{*** reconstruct weight information ***}
if t <> nil then begin
t^.weight := wt( t^.left ) + wt( t^.right );
checkrots( t )
end
end
end;
|