|
<![CDATA[
tree checkrots( t )
tree t;
/*** check need for rotations ***/
{ int wl, wll, wr, wrr;
if( t != NULL ) {
wl = wt( t->left );
wr = wt( t->right );
if( wr > wl ) {
/*** left rotation needed ***/
wrr = wt( t->right->right );
if( wrr > wl && 2*wrr >= wr )
{ t = lrot( t ); t->left = checkrots( t->left ); }
else if( wr-wrr > wl ) {
t->right = rrot( t->right );
t = lrot( t );
t->left = checkrots( t->left );
t->right = checkrots( t->right );
}
}
else if( wl > wr ) {
/*** right rotation needed ***/
wll = wt( t->left->left );
if( wll > wr && 2*wll >= wl )
{ t = rrot( t ); t->right = checkrots( t->right ); }
else if( wl-wll > wr ) {
t->left = lrot( t->left );
t = rrot( t );
t->left = checkrots( t->left );
t->right = checkrots( t->right );
}
}
}
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 (3415.chckr.c) 