|
<![CDATA[
int incrhei;
tree insert( key, t )
typekey key;
tree t;
{ if( t == NULL ) {
t = NewNode( key, NULL, NULL );
t->bal = 0;
incrhei = 1;
}
else if( t->k == key )
Error; /*** Key already in table ***/
else {
if( t->k < key )
{ t->right = insert( key, t->right ); t->bal += incrhei; }
else { t->left = insert( key, t->left ); t->bal -= incrhei; }
if( (incrhei != 0) && (t->bal != 0) ) {
incrhei = 0;
if( t->bal < -1 )
/*** left subtree too tall: right rotation needed ***/
if( t->left->bal < 0 ) t = rrot( t );
else { t->left = lrot( t->left ); t = rrot( t ); }
else if( t->bal > 1 )
/*** right subtree too tall: left rotation needed ***/
if( t->right->bal > 0 ) t = lrot( t );
else { t->right = rrot( t->right ); t = lrot( t ); }
else incrhei = 1;
}
else incrhei = 0;
}
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 (3413.ins.c) 