AVL Tree Code - I don't understand

Question

void insert( const Comparable & x, AvlNode * & t )
{
    if( t == NULL )
            t = new AvlNode( x, NULL, NULL );
    else if( x < t->element )
    {
            insert( x, t->left );
            if( height( t->left ) - height( t->right ) == 2 )
                    if( x < t->left->element )
                            rotateWithRightChild( t );
                    else
                            doubleWithLeftChild( t );
    }
    else if( t->element < x )
    {
            insert( x, t->right );
            if( height( t->right ) - height( t->left ) == 2 )
                    if( x < t->left->element )
                            rotateWithRightChild( t );
                    else
                            doubleWithLeftChild( t );
    }
    else
            ; // Duplicate; do nothing
    t->height = max( height( t->left ), height( t->right ) ) + 1;

}

int height( AvlNode *t ) const { return t == NULL ? -1 : t->height; }

How can they cal the height of tree ?

       1
     0
  -1

height(-1) - height(null) = 1 ?? Not balance ?

Answer 1

It's not 100% clear what you're asking. The code

AvlNode * & t

declares t to be a reference to a non-const pointer. So, the function insert may change the pointer object of the caller. Since pointers may be null the code probably uses a function called height as a shortcut to handle the special case of null pointers:

inline int height(AvlNode * tree) {
    return tree ? tree->height : 0;
}

(just my guess of what height could look like)

Added after you editited your question: It seems each node posesses a member called height which is kept in sync and reflects the maximum length of the path from the current node to a leaf. Since a null pointer doesn't point to a node, the subtree would be empty which explains the special case in height() that returns -1.

Answer 2

Thanks . I completely understand now :) I miss the last line of insert function. How shame :P