3
$\begingroup$

An AVL tree is one that satisfies the height-balance property which states that: For every position p of T, the heights of the children of p differ by at most 1.

Below is an example AVL tree. However, I've highlighted a node whose child's height would imply that their difference is not at most 1.

Can someone explain to me what I am missing?

enter image description here

Improve this question
$\endgroup$
3
  • $\begingroup$ Which node do you think violates the property? The node with 78? Or the node with 88? Why do you think it violates the property? Please edit the question to spell out which node you are referring to and what you think its children are. $\endgroup$
    – D.W. ♦
    Sep 14, 2015 at 18:17
  • $\begingroup$ I apologize. Yuval identified what I was looking for. I was looking at the difference between a node and its child, rather than the difference between two children. Above, the difference was 3 - 1 = 2, which was > 1, even though it was considered balanced. This difference is irrelevant. We are interested in 3 - 2 (node 78 and 17) which is 1. $\endgroup$
    – tsurantino
    Sep 14, 2015 at 18:29
  • 1
    $\begingroup$ Glad that helped! You can still edit your question to improve the chances that it will be helpful to others in the future. $\endgroup$
    – D.W. ♦
    Sep 14, 2015 at 20:13

2 Answers 2

Reset to default
3
$\begingroup$

The nodes you are highlighting are a node and its child. The promise is that the heights of siblings don't differ by more than $1$. In other words, the promise is that for every node $p$, the heights of the children of $p$ differ by at most $1$ from each other.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I knew I was missing something simple. Thank you so much for writing this answer. $\endgroup$
    – tsurantino
    Sep 14, 2015 at 18:22
2
$\begingroup$

From wikipedia:

The balance property of AVL trees is defined in terms of the "balance factor", which is calculated as

balance factor = height(left sub tree) - height(right sub tree)

So, you should not compare parent with its child, only the left and right children.

Improve this answer
$\endgroup$
3
  • $\begingroup$ The term "balance factor" doesn't appear in the question so it's not clear how defining it helps. Could you flesh out your answer a little? $\endgroup$
    – David Richerby
    Nov 10, 2015 at 10:03
  • $\begingroup$ @DavidRicherby I made it clear in my answer, thanks! $\endgroup$
    – John S. V.
    Nov 13, 2015 at 8:20
  • $\begingroup$ OK, in that case, I don't see what your answer adds to the accepted answer from two months ago, which already points out that this is exactly the error the asker was making. Please don't post answers that just duplicate existing ones. $\endgroup$
    – David Richerby
    Nov 13, 2015 at 8:22

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.