5
$\begingroup$

I have been reading about AVL trees, at the moment I'm trying to figure out how to determine the height of a tree and how to draw an AVL tree of some height with minimum number of elements.

In a tutorial I found that this: would be a AVL tree of height 7
enter image description here

And this AVL tree with the height 4
enter image description here

This is really confusing by the look I would guess that both of them are of height 4. I'm fairly new to data structures, I could not find a simple documentation/tutorial regarding this most of what i found was about Insertion/Deletion with AVL trees.

So is the top tree of height 7 if not how would I draw it with the minimal number of elements. I understand the each sub tree would have to be balanced.

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ This answer contains all you need to know. $\endgroup$ Commented Apr 7, 2013 at 12:55

2 Answers 2

Reset to default
4
$\begingroup$

Generally tree height is defined as the length of the longest path from the root to a leaf. Therefore you're right that the two trees have the same height, but they actually have height 3.

As far as your second question, about how to draw the smallest possible AVL tree of a given height $n$, the trick is to think inductively. Construct a new tree of height $n$ by joining the smallest possible AVL trees of height $n-1$ and height $n-2$ as subtrees of a new common root. Using the definition of AVL trees, it's a straightforward exercise to see that (1) this new tree is a valid AVL tree and (2) it's the smallest possible AVL tree of height $n$.

To get the height 7 tree in particular, find the base case minimal AVL trees of heights 0 and 1, and repeat the above construction 6 times.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I drew a tree with the height of 7 but I'm not fully sure if it's correct. I get that min 17 elements are required. I added the picture to my question. $\endgroup$ Commented Apr 7, 2013 at 3:08
  • $\begingroup$ No. The heights of the subtrees of the left child of the root do not satisfy the AVL property. $\endgroup$ Commented Apr 7, 2013 at 3:23
  • $\begingroup$ I followed a pretty complex tutorial and what you wrote and managed to get another graph. Can you check if this would be correct ? $\endgroup$ Commented Apr 7, 2013 at 4:01
1
$\begingroup$

What you want is to produce maximally unbalanced AVL trees of a given height, also called Fibonacci trees (because they have Fn+2-1 nodes, where n is the height of the tree, and Fn is the n-th Fibonacci number).

I worked on that, and asked and answered a question on stackoverflow, accepting another answer. Have a look, you may find what you are looking for.

And of course, the top tree is of height 4, not 7. BTW, your last sentence is not correct: every subtree should be unbalanced.

To build a Fibonacci tree of height 7, you may start from your bottom picture, which is a Fibonacci tree of height 4, consisting of two Fibonacci subtrees, the left one of height 3, and the right one of height 2. Take the left subtree, put it to the right of the current tree, and link both to a new root node. You will obtain a Fibonacci tree of height 5. Just repeat the same recipe 2 more times, and you are done.

Please note: I'm using the more intuitive convention that calls the height of the tree the number of nodes on the longest path from root to leaf. I'm not alone in this for sure. I find it a bit disturbing to say that an empty tree has height -1.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.