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;