How is Wikipedia's example of an unbalanced AVL tree really unbalanced?

Question

The image above is from "Wikipedia's entry on AVL trees" which Wikipedia indicates is unbalanced. How is this tree not balanced already? Here's a quote from the article:

The balance factor of a node is the height of its right subtree minus the height of its left subtree and a node with balance factor 1, 0, or -1 is considered balanced. A node with any other balance factor is considered unbalanced and requires rebalancing the tree. The balance factor is either stored directly at each node or computed from the heights of the subtrees.

Both the left and right subtrees have a height of 4. The right subtree of the left tree has a height of 3 which is still only 1 less than 4. Can someone explain what I'm missing?

Grooms

Answer 1

To be balanced, every node in the tree must, either,

• have no children, (be a "leaf" node)
• Have two children.

• Or, if it has only one child, that child must be a leaf.

  In the chart you posted, 9, 54 & 76 violate the last rule.

Properly balanced, the tree would look like:

Root: 23
(23) -> 14 & 67
(14) -> 12 & 17
(12) -> 9
(17) -> 19
(67) -> 50 & 72
(50) -> 54
(72) -> 76

UPDATE: (after almost 9 years, I created a cool online chart for the graph at draw.io)

Semiporcelain

Answer 2

Node 76 is unbalanced, for example, because its right subtree is of height 0 and the left is of height 3.

Brack

I think the point is that a tree is only balanced if all subtrees in it are. – Brack

All leaf/child nodes need to be balanced. – Foolery

Answer 3

Intuitively, it's because it's not as small as possible. e.g., 12 should be the parent of 9 and 14. As it is, 9 has no left sub-tree so it's out of balance. A tree is a hierarchical data structure so a rule like "balanced" often apply to every node and not just the root node.

You're correct the root node is balanced, but not all the nodes of the tree are.

Miliaria

Answer 4

Another way to look at this is that the height h of any node is given by:

h = 1 + max( left.height, right.height )

and a node is unbalanced whenever:

abs( left.height - right.height ) > 1

Looking at the tree above:

- Node 12 is a leaf node so its height = 1+max(0,0) = 1
- Node 14 has one child (12, on the left), so its height is = 1+max(1,0) = 2
- Node 9 has one child (14, on the right), so its height is = 1+max(0,2) = 3

To determine if node 9 is balanced or not we look at the height of its children:

- 9's left child is NULL, so 9.left.height = 0
- 9's right child (14) has height 2, so 9.right.height = 2

Now solve to show that node 9 is unbalanced:

9.unbalanced = abs( 9.left.height - 9.right.height ) > 1
9.unbalanced = abs( 0 - 2 ) > 1
9.unbalanced = abs( -2 ) > 1
9.unbalanced = 2 > 1
9.unbalanced = true

Similar calculations can be made for every other node.

Vivacity

Answer 5

A height balanced tree is many ways best! For every subtree, it has children of heights that differ by 1 or 0, where no children is a height of zero, so a leaf has height 1. It is the simplest balanced tree, with the lowest overhead to balance: a maximum of 2n rotations for an insert or delete in a tree area of height n, and often much less. A rotation is writing 3 pointers, and so is very cheap. The worst case of the height balanced tree, even though of about 42% greater maximum height, is about one comparison less efficient than a perfectly balanced full binary tree of 2^n-1 values. A perfectly balanced full binary tree is far more expensive to achieve, tends to need, on average, n-1 comparisons for a find and exactly n comparisons always for a not-found. For the tree worst case insertion order, ordered data, when 2^n-1 items are inserted, the height balanced tree that results is a perfectly balanced full binary tree!

(Rotation is a great way to balance, but comes with a catch: if the heavy grandchild is on the inside of the heavy child, a single rotate just moves it to the inside of the opposite side, with no improvement. So, if it is 1 unit higher, even though nominally balanced, you rotate that child to lighten it first. Hence a max of 2n rotations for an n level insert or delete, worst case and unlikely.)

Submediant