World's most popular travel blog for travel bloggers.

AVL Tree Height

, , No Comments
Problem Detail: 

What is the height of an AVL Tree? I keep finding contradicting definitions.

I found these two on wiki:

Height of node: The height of a node is the number of edges on the longest path between that node and a leaf.

Height of tree: The height of a tree is the height of its root node.

But then I find examples like this: http://pages.cs.wisc.edu/~ealexand/cs367/NOTES/AVL-Trees/avl1.png

In my course, in the lecture notes it uses the height in the way the above picture does. But then in the course textbook it uses the height in the same way the google definition does. So, honestly, I'm not sure which way is correct. What would an AVL tree, of height 5 for example, look like?

Asked By : Jay P
Answered By : Tom van der Zanden

You can use either definition of height, so long as you are consistent in which one you use. The difference between the definitions is presumably just an additive factor $1$ (since one definition counts edges and the other appears to count nodes), which is irrelevant for most CS purposes. There is no "correct" definitions as different authors have come up with and used their own definitions.

Of course, it is possible that your course instructor (if you are taking a course) expects you to use a particular definition but the only way to find out which one to use is to ask them (or pay attention to which one they use in their lectures).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/61148

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback