function insert( key : typekey; var t : tree ) : integer;
var	incr : integer;
begin
insert := 0;
if t = nil then	begin
		t := NewNode( key, nil, nil );
		t^.bal := 0;
		insert := 1
		end
else if t^.k = key then
		Error {*** Key already in table ***}
else	with t^ do	begin
	if k < key then	incr := insert( key, right )
		else	incr := -insert( key, left );
	bal := bal + incr;
	if (incr <> 0) and (bal <> 0) then
		if bal < -1 then
			{*** left subtree too tall: right rotation needed ***}
			if left^.bal < 0 then	rrot( t )
				else	begin	lrot( left ); rrot( t ) end
		else	if bal > 1 then
			{*** right subtree too tall: left rotation needed ***}
			if right^.bal > 0 then	lrot( t )
				else	begin	rrot( right ); lrot( t ) end
		else	insert := 1;
	end
end;