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


Internal path reduction trees (k-balancing): check rotations


#define K 3 /*** Split the largest, merge the two smallest ***/ tree checkrots( t ) tree t; { tree R[K], P[K+1]; int i, j, maxwt, minwt; if( wt(t) <= K ) return( t ); if( wt( t->left ) < wt( t-> right ) ) { R[0] = t; R[1] = t->right; P[0] = t->left; P[1] = R[1]->left; P[2] = R[1]->right; } else { R[0] = t->left; R[1] = t; P[0] = R[0]->left; P[1] = R[0]->right; P[2] = t->right; } /*** Expand ***/ for( i=2; i<K; i++ ) { for( maxwt=0,j=1; j<=i; j++ ) if( wt(P[maxwt]) < wt(P[j]) ) maxwt = j; for( j=i-1; j >= maxwt; j-- ) { P[j+2] = P[j+1]; R[j+1] = R[j]; } R[maxwt] = P[maxwt]; P[maxwt] = R[maxwt]->left; P[maxwt+1] = R[maxwt]->right; } /*** Merge the two smallest neighbours ***/ for( i=K; i>0; i-- ) { for( minwt=0,j=1; j<i; j++ ) if( wt(P[minwt])+wt(P[minwt+1]) > wt(P[j])+wt(P[j+1]) ) minwt = j; R[minwt]->left = P[minwt]; R[minwt]->right = P[minwt+1]; R[minwt]->weight = wt(P[minwt]) + wt(P[minwt+1]); P[minwt] = R[minwt]; for( j=minwt+1; j<i; j++ ) { R[j-1] = R[j]; P[j] = P[j+1]; } } return( P[0] ); }

C source (34155.chckr.c)



© Addison-Wesley Publishing Co. Inc.