patternMinor
AVL Trees Height-Balance Property
Viewed 0 times
heightbalancetreespropertyavl
Problem
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?
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?
Solution
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.
Context
StackExchange Computer Science Q#47175, answer score: 3
Revisions (0)
No revisions yet.