CODEWITHSUNDEEP
algorithmbinary-treeavl-tree
JAN
JAN

Reputation: 21855

AVL tree - Why is it a must that the heights of the left and right children of some node may differ by 1?

What's wrong with the heights of the left and right children of some node differ being by 2?

This is my first encounter with AVL trees, and I can't seem to understand why it is a must?

Really, what's wrong with the children being different by 2?

Regards

Upvotes: 2

Views: 808

Answers (2)

Oleksi
Oleksi

Reputation: 13097

By definition, a balanced binary tree can only differ by one. If you look at the algorithms that operate on the AVL trees, you'll see that this property is always maintained.

While it's possible to make some sort of data structure where the height differs by +- 2 at most, there is not real benefit in doing so. By leaving it as +- 1, you create a simpler, self-balancing data structure.

Upvotes: 3

allaire
allaire

Reputation: 6045

Well that's the concept of an AVL tree, the height of left and right childs must not differ by at most one.

From Wikipedia

In an AVL tree, the heights of the two child subtrees of any node differ by at most one.

Since it's balanced, this make the search 0(logn), so it's faster than a non-balanced binary tree, where all the elements could be on the left, making it 0(n)

Upvotes: 3

Related Questions