procedure delete( key : typekey; var t : tree );

	begin
	if t = nil then	Error {*** key not found ***}

	{*** search for key to be deleted ***}
	else 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
		{*** left side is heavier, do a right rotation ***}
		if wt( t^.left^.left ) < wt( t^.left^.right ) then
			lrot( t^.left );
		rrot( t );
		delete( key, t^.right )
		end
	else	{*** do a left rotation ***}
		begin
	 	if wt( t^.right^.left ) > wt( t^.right^.right ) then
			rrot( t^.right );
		lrot( t );
		delete( key, t^.left )
		end;

	{*** reconstruct weight information ***}
	if t<>nil then t^.weight := wt( t^.left ) + wt( t^.right );
	end;