Take the 2-minute tour ×

alt text

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?

share|improve this question
add comment

3 Answers

up vote 9 down vote accepted

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 post, 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
share|improve this answer
That's much clearer! –  Kena Oct 23 '08 at 19:01
add comment

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

share|improve this answer
I think the point is that a tree is only balanced if all subtrees in it are. –  JesperE Oct 23 '08 at 18:23
All leaf/child nodes need to be balanced. –  Joe Philllips Oct 23 '08 at 19:18
add comment

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.

share|improve this answer
add comment

Your Answer


