function NewNode( k1 : typekey; p0, p1 : btree ) : btree;

var t : btree;
begin
     new( t );
     t^.p[0] := p0;
     t^.p[1] := p1;
     t^.k[1] := k1;
     t^.d := 1;
     NewNode := t
end;

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

var  ins : typekey;
     NewTree : btree;

   function InternalInsert( t : btree ) : typekey;
   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 ***}
        InternalInsert := key;
        NewTree := nil
   end
   else with t^ do begin
        InternalInsert := 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 := InternalInsert( 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, ins, NewTree )
                  else     {*** Present node has to be split ***}
                  begin
                    {*** Create new node ***}
                    if i<=M+1 then begin
                        tempr := NewNode( k[2*M], nil, p[2*M] );
                        d := d-1;
                        InsInNode( t, ins, NewTree )
                    end
                    else tempr := NewNode( ins, nil, NewTree );
                    {*** move keys and pointers ***}
                    for j:=M+2 to 2*M do
                         InsInNode( tempr, k[j], p[j] );
                    d := M;
                    tempr^.p[0] := p[M+1];
                    InternalInsert := k[M+1];
                    NewTree := tempr
                  end
             end
        end
   end;

begin
     ins := InternalInsert( t );
     {*** check for growth at the root ***}
     if ins <> NoKey then t := NewNode( ins, t, NewTree)
end;