HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

AVL Trees Height-Balance Property

Submitted by: @import:stackexchange-cs··
0
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?

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.