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 );
  }