int incrhei;

tree insert( key, t )
typekey key;
tree t;

{ if( t == NULL ) {
        t = NewNode( key, NULL, NULL );
        t->bal = 0;
        incrhei = 1;
        }
  else if( t->k == key )
        Error; /*** Key already in table ***/
  else  {
        if( t->k < key )
         { t->right = insert( key, t->right );  t->bal += incrhei; }
        else { t->left  = insert( key, t->left );   t->bal -= incrhei; }
        if( (incrhei != 0) && (t->bal != 0) ) {
            incrhei = 0;
            if( t->bal < -1 )
                /*** left subtree too tall: right rotation needed ***/
                if( t->left->bal < 0 ) t = rrot( t );
                    else { t->left =  lrot( t->left );  t = rrot( t ); }
            else    if( t->bal > 1 )
                /*** right subtree too tall: left rotation needed ***/
                if( t->right->bal > 0 )   t = lrot( t );
                    else { t->right = rrot( t->right );  t = lrot( t ); }
            else    incrhei = 1;
        }
    else  incrhei = 0;
        }
  return( t );
}