weight-unbalanced AVL tree

Question

Believing the wikipedia article: http://en.wikipedia.org/wiki/AVL_tree

AVL trees are height-balanced, but in general not weight-balanced nor μ-balanced;[4] that is, sibling nodes can have hugely differing numbers of descendants.

But, as an AVL tree is:

a self-balancing binary search tree [...]. In an AVL tree, the heights of the two child subtrees of any node differ by at most one

I don't see how an AVL could be weight-unbalanced since -if I understood the definition of an AVL tree well-, every sibling will have approximately the same number of child since they have the same height +/- 1.

So, could you give me an example of an AVL tree which is unbalanced ? I did not succeed to find one. Thus, or I misunderstood the definition of an AVL/unweighted tree, or the wikipedia article is false...

Thanks

Answer 1

sibling nodes can have hugely differing numbers of descendants.

I was just scratching my head about this and the fact that my AVL implementation produced trees that were not ultimately lopsided, but which had smaller and larger "distant cousin" subtrees inside.

I sketched this out to reassure myself:

The red nodes have a balance of 1, the green ones -1, and the black ones 0. This is a valid AVL tree in that the height difference between two sibling subtrees is never more than one, but there are (almost) twice as many nodes in the right subtree as the left one.

Answer 2

You are correct in your understanding that an AVL tree is defined by the nearly-uniform height of its edge nodes, but your confusion appears to be about the difference between node position and edge weight.

That is: In an AVL tree, the depth of the edge nodes will the same +/- (but not both!) one. This makes no claims as to the cost associated with an edge between the nodes. For an AVL tree with a root node and two children, the left path may be twice as expensive to traverse as the right path. This would make the tree weight-unbalanced, but still maintain the definition of an AVL tree.

This page has more information: Weight-balanced tree - wikipedia

From Wikipedia:

A Binary Tree is called μ-balanced, with , if for every node N, the inequality:

holds and μ is minimal with this property. |N| is the number of nodes under the tree with N as root (including the root) and Nl is the left sub-tree of N.

Essentially, this means that the children in an AVL tree are not necessarily evenly distributed across the lowest level of the tree. Taking N as indicating the root node of the tree, one could construct a valid AVL tree that has more children to the left of the root than to the right of it. With a very deep tree, there could be many nodes at this bottom level.

The definition of an AVL tree would require that they all be within one of the deepest point, but makes no guarantee as to what node they are a child of with respect to a node N.