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

Weight balanced tree deletion (Pascal version available)


tree delete( key, t ) typekey key; tree t; { if( t == NULL ) Error; /*** key not found ***/ else { /*** search for key to be deleted ***/ if( t->k <key ) t->right = delete( key, t->right ); else if( t->k > key ) t->left = delete( key, t->left ); /*** key found, delete if a descendant is NULL ***/ else if( t->left == NULL ) t = t->right; else if( t->right == NULL ) t = t->left; /*** no descendant is null, rotate on heavier side ***/ else if( wt( t->left ) > wt( t->right ) ) { t = rrot( t ); t->right = delete( key, t->right ); } else { t = lrot( t ); t->left = delete( key, t->left ); } /*** reconstruct weight information ***/ if( t != NULL ) { t->weight = wt( t->left ) + wt( t->right ); t = checkrots( t ); } } return( t ); }

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


© Addison-Wesley Publishing Co. Inc.