height of an avl tree?

[timb89]

anyone have any ideas? for some reason uni forgot to include lectures notes on this, yet decided to base homework on it. i get the general idea just not sure how to implement it.

[SasseMan]

An avl tree is a self balancing tree which means that there is a mathematical relationship between the number of elements in the tree and the height.

Since a lookup in a AVL tree takes O(log(n)) time, the height should also be O(log(n)) i.e. ceiling(log2(n)). Read about avl trees here...

http://en.wikipedia.org/wiki/AVL_tree

[timb89]

An avl tree is a self balancing tree which means that there is a mathematical relationship between the number of elements in the tree and the height.

Since a lookup in a AVL tree takes O(log(n)) time, the height should also be O(log(n)) i.e. ceiling(log2(n)). Read about avl trees here...

http://en.wikipedia.org/wiki/AVL_tree

obvuously regular code like this would work? but is it as simple as just a one line return code?

int height(node *AVLtree, int current, int max) 
{
    if(AVLtree != NULL) 
    {
        if(current > max) 
        { 
        max = current;
	}
    }

	
    if(AVLtree->left != NULL)
    {
    current = height(AVLtree->left, current, max);
    }


    if(AVLtree->right != NULL) 
    {
    current = height(AVLtree->right, current, max);
    }

}

[SasseMan]

If you want to calculate the height by going down the tree you don't need all that code. Just follow nodes down until you reach the end and thats your height. But the better thing to do is to keep track of the number of nodes in the data structure an just return ceil(log2(n)). Your code look to be running in O(n), I would do it like this...

int height( node *AVLtree ) {
     if(AVLtree == NULL) return 1;
     return 1 + height(AVLtree->left);
}

But of course you can be off by 1 if you use this method, it depends on what the heigh value is going to be used for. If your looking for the most "correct" solution you probably want to go through the entire tree. I'm not sure if your code will work though, it not even returning anything.