|
<![CDATA[
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;
]]> |
![[Home]](../../images/home_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (342.ins.c) 