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

$\endgroup$
  • $\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 '15 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 '15 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 '15 at 20:13
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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I knew I was missing something simple. Thank you so much for writing this answer. $\endgroup$ – tsurantino Sep 14 '15 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.

| cite | improve this answer | |
$\endgroup$
  • $\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 '15 at 10:03
  • $\begingroup$ @DavidRicherby I made it clear in my answer, thanks! $\endgroup$ – John S. V. Nov 13 '15 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 '15 at 8:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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