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


Weight balanced insertion: check rotations (Pascal version available)


tree checkrots( t ) tree t; { float wbal; wbal = wt( t->left ) / (float)t->weight; if( wbal > 0.707011 ) /*** left subtree too heavy: right rotation needed ***/ if( wt( t->left->left ) / (float)wt( t->left ) > 0.414213 ) t = rrot( t ); else { t->left = lrot( t->left ); t = rrot( t ); } else if( wbal < 0.292893 ) /*** right subtree too heavy: left rotation needed ***/ if( wt( t->right->left ) / (float)wt( t->right ) < 0.585786 ) t = lrot( t ); else { t->right = rrot( t->right ); t = lrot( t ); } return( t ); }

C source (3414.chckr.c) Pascal source (3414.chckr.p)



© Addison-Wesley Publishing Co. Inc.