0
$\begingroup$

I found an AVL tree implementation on the internet and experimented: For a tree with node count of 2^20, the minimal and maximal tree heights are 16 and 24. While these heights are lg(n)-ish, I am concerned about their difference. Doesn't AVL guarantee maximal-minimal height difference to be 1?

The repository from which I got the code

$\endgroup$
6
  • $\begingroup$ It should guarantee that, so it might be that what you have found is a more relaxed version of some sort of self balancing tree. $\endgroup$
    – nir shahar
    Dec 13, 2021 at 11:29
  • $\begingroup$ I dont think that its an AVL tree, cause theorietical bounds for min/max heights with n nodes are logn and 1.44*logn which turns out to be the range 20-28 in this case. I agree that it might be a relaxed version of some self balancing tree. Maybe you could share the link to its implementation so that one can understand it better. $\endgroup$
    – Rinkesh P
    Dec 13, 2021 at 12:54
  • $\begingroup$ @RinkeshP: Provided a link to the repo. Thanks $\endgroup$
    – Vectorizer
    Dec 13, 2021 at 14:39
  • 1
    $\begingroup$ No, AVL does not require max-min height difference to be <=1 on all paths. It does require that, for each node, (max height of left subtree) and (max height of the right subtree) are at most 1 unit apart. Example: en.wikipedia.org/wiki/Fibonacci_number#/media/… $\endgroup$
    – chi
    Dec 13, 2021 at 16:07
  • $\begingroup$ @Chi This very useful. If you could provide this as an answer(with the "max height" emphasized) I'll gladly mark it so. $\endgroup$
    – Vectorizer
    Dec 13, 2021 at 16:42

1 Answer 1

3
$\begingroup$

The AVL invariant does not guarantee that, given any two tree paths, their length differs at most by one unit. They can differ by more than one unit, as shown by the following tree (Fibonacci AVL tree from Wikipedia):

Fibonacci Tree 6.svg

Instead, the AVL invariant only requires that the heights of the two subtrees of any nodes differ at most by one. Note that the height of a (sub)tree is the maximum length of its paths. Therefore, the AVL invariant is equivalent to requiring that, for all nodes, the maximum length of a path in the left subtree and the maximum length of a path in the right subtree differ at most by one unit.

Note how we only take the paths giving the maximum length, and never the paths giving the minimum length.

$\endgroup$

Your Answer

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

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