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


Quad trie insertion


tree insert( key, t ) typekey key[K]; tree t; { tree InsertIndx(); return( InsertIndx(key,t,1) ); } tree InsertIndx( key, t, lev ) typekey key[K]; tree t; int lev; { int i, indx; tree t1; if ( t == NULL ) return( NewDataNode(key) ); if ( IsData(t) ) { for( i=0; i<K && key[i] == t->k[i]; i++ ); if ( i >= K ) { Error /*** Key already in table ***/; return(t); } else { t1 = NewIntNode(); indx = 0; for ( i=0; i<K; i++ ) indx = 2*indx + bit(lev,t->k[i]); t1->p[indx] = t; t = t1; } } indx = 0; for ( i=0; i<K; i++ ) indx = 2*indx + bit(lev,key[i]); t->p[indx] = InsertIndx( key, t->p[indx], lev+1 ); return( t ); };

C source (351b.ins.c)



© Addison-Wesley Publishing Co. Inc.