[Home]
[Contents]
[Chapter]
[Previous Algorithm]
[Next Algorithm]


B-tree insertion (Pascal version available)


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 ); } };

C source (342.ins.c) Pascal source (342.ins.p)



© Addison-Wesley Publishing Co. Inc.