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

Answer 1

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

Answer 2

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.

Answer 3

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