procedure InsInNode( t : btree; i : integer; key : typekey );

var	j : integer;
begin
with t^ do begin
	for j:=d downto i do begin
		k[j+1] := k[j];
		p[j+1] := p[j]
		end;
	d := d+1;
	k[i] := key;
	p[i] := newnode
	end
end;

function rinsert( key : typekey; t : btree ) : integer;

var	i, j : integer;
	ins : typekey;
	tempr : btree;
begin
if t=nil then begin	{*** The bottom of the tree has been reached:
				indicate insertion to be done ***}
		rinsert := key;
		newnode := nil
		end
else	with t^ do begin
	rinsert := NoKey;
	i := 1;
	while ( i<d ) and ( key>k[i] ) do	i := i+1;
	if key = k[i] then
		Error {*** Key already in table ***}
	else 	begin
		if key > k[i] then i := i+1;
		ins := rinsert( key, p[i-1] );
		if ins <> NoKey then
		{*** the key in "ins" has to be inserted in present node ***}
			if d<2*M then	InsInNode( t, i, ins )
		else	begin
			{*** Present node has to be split ***}
			new( tempr );
			if i<=M+1 then begin
				{*** New insertion is in left node ***}
				for j:=M+1 to 2*M do begin
					tempr^.k[j-M] := k[j];
					tempr^.p[j-M] := p[j]
					end;
				tempr^.d := M;
				d := M;
				InsInNode( t, i, ins )
				end
			else	begin
				{*** New insertion is in right node ***}
				for j:=M+2 to 2*M do begin
					tempr^.k[j-M-1] := k[j];
					tempr^.p[j-M-1] := p[j]
					end;
				tempr^.d := M-1;
				InsInNode( tempr, i-M-1, ins)
				end;
			tempr^.p[0] := p[M+1];
			rinsert := k[M+1];
			d := M;
			newnode := tempr
			end
		end
	end
end;

procedure insert( key : typekey; var t : btree );

var	ins : typekey;
	tempr : btree;
begin
	ins := rinsert( key, t );
	if ins <> NoKey then begin
		new( tempr );
		with tempr^ do begin
			d := 1;
			k[1] := ins;
			p[0] := t;
			p[1] := newnode;
			t := tempr
			end
		end
end;