0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • $\begingroup$ Your question would be clearer if you could explain the definition that the picture illustrates, and what the supposed conflict is. $\endgroup$
    – Tom van der Zanden
    Aug 1, 2016 at 11:19
  • $\begingroup$ @TomvanderZanden By the wikipedia definition, the example I gave the root would have height 3, and not 4 as is shown. And by the second definition, the height of the tree would be 3, and not 4 as is shown. $\endgroup$
    – Jay P
    Aug 1, 2016 at 11:28
  • $\begingroup$ What is the second definition? The picture just shows a tree whose vertices are labeled with heights, but how can one tell from just that picture what the definition is? $\endgroup$
    – Tom van der Zanden
    Aug 1, 2016 at 11:32
  • $\begingroup$ @TomvanderZanden If you look at the example, and apply the definition of the height of the tree, the tree has height 4. But if you look at the example, and apply both the definition of the height of node and the height of tree, the tree has height 3. This is where my confusion comes from. $\endgroup$
    – Jay P
    Aug 1, 2016 at 11:35

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ So regardless of which definition you use, the height of a given AVL tree will always be the same numerical value? It doesn't change with the additive factor 1? $\endgroup$
    – Jay P
    Aug 1, 2016 at 11:46
  • $\begingroup$ The height depends on the definition you use. $\endgroup$
    – Tom van der Zanden
    Aug 1, 2016 at 12:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.