|
<![CDATA[
btree insert( key, t )
typekey key;
btree t;
{
typekey ins;
extern btree NewTree;
typekey InternalInsert();
ins = InternalInsert( key, t );
/*** check for growth at the root ***/
if ( ins != NoKey ) return( NewNode( ins, t, NewTree) );
return( t );
};
typekey InternalInsert( key, t )
typekey key;
btree t;
{int i, j;
typekey ins;
btree tempr;
extern btree NewTree;
if ( t == NULL ) { /*** the bottom of the tree has been reached:
indicate insertion to be done ***/
NewTree = NULL;
return( key );
}
else {
for ( i=0; i<t->d && key>t->k[i]; i++ );
if ( i<t->d && key == t->k[i] )
Error; /*** Key already in table ***/
else {
ins = InternalInsert( key, t->p[i] );
if ( ins != NoKey )
/*** the key in "ins" has to be inserted in present node ***/
if (t->d < 2*M) InsInNode( t, ins, NewTree );
else /*** present node has to be split ***/
{/*** create new node ***/
if ( i<=M ) {
tempr = NewNode( t->k[2*M-1], NULL, t->p[2*M] );
t->d--;
InsInNode( t, ins, NewTree );
}
else tempr = NewNode( ins, NULL, NewTree );
/*** move keys and pointers ***/
for ( j=M+2; j<=2*M; j++ )
InsInNode( tempr, t->k[j-1], t->p[j] );
t->d = M;
tempr->p[0] = t->p[M+1];
NewTree = tempr;
return( t->k[M] );
}
}
return( NoKey );
}
};
]]> |
![[Home]](../../images/home_g.gif)
![[Contents]](../../images/contents_g.gif)
![[Chapter]](../../images/chapter_g.gif)
![[Previous Algorithm]](../../images/prevalg_g.gif)
![[Next Algorithm]](../../images/nextalg_g.gif)
C source (342.ins.c) 