|
<![CDATA[
patricia insert( key, t )
typekey key;
patricia t;
{patricia p;
patricia InsBetween();
int i;
if (t==NULL) return( NewDataNode(key) );
for( p=t; !IsData(p); )
p = bit( p->level, key ) ? p->right : p->left ;
/* find first different bit */
for (i=1; i<=D && bit(i,key)==bit(i,p->k); i++);
if (i>D) { Error /* Key already in table */;
return(t); }
else return( InsBetween( key, t, i ) );
}
patricia InsBetween( key, t, i )
typekey key;
patricia t;
int i;
{patricia p;
if ( IsData(t) || i < t->level ) {
/* create a new internal node */
p = NewDataNode( key );
return( bit(i,key) ? NewIntNode(i,t,p) : NewIntNode(i,p,t) );
}
if (bit(t->level,key)==1)
t->right = InsBetween( key, t->right, i );
else t->left = InsBetween( key, t->left, i );
return( t );
};
]]> |
![[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 (3445.ins.c) 