Uneven AVL Tree

Question

Assuming a Wikipedia article: http://en.wikipedia.org/wiki/AVL_tree

AVL trees are balanced in height, but, as a rule, are not balanced in weight, nor μ-balanced [4], that is, siblings can have an extremely different number of descendants.

But, since the AVL tree:

self-balancing binary search tree [...]. In the AVL tree, the heights of two child subtrees of any node differ by no more than

I do not see how AVL can be an unbalanced weight since, as if I understood the definition of the AVL tree well, each brother would have approximately the same number of children, since they have the same height +/- 1.

So, could you give me an example of an AVL tree that is unbalanced? I could not find him. Thus, either I misunderstood the definition of AVL / unweighted tree, or the wikipedia article is false ...

thanks

Answer 1

You correctly understand that the AVL tree is determined by almost the same height of its edge nodes, but your confusion seems to be related to the difference between the node position and the edge weight.

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

This page contains additional information: weight balanced tree - wikipedia

From Wikipedia:

The binary tree is called μ-balanced with if for each node N the following 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 subtree of N.

Essentially, this means that children in the AVL tree are not necessarily evenly distributed across the lowest level of the tree. Taking N as an indication of the root of the node tree, you can build 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 can be many nodes at this lower level.

Defining an AVL tree will require that they all be at one of the deepest points, but makes no guarantee that they are children of node N.

Answer 2

sibling nodes can have an extremely different number of descendants.

I just scratched my head about this and the fact that my AVL implementation created trees that were not ultimately one-sided, but that had smaller and larger subtree "distant cousins" inside.

I sketched this to reassure myself:

Red nodes have a balance of 1, green -1 and black 0. This is a real AVL tree in that the height difference between the two sister subfamilies is no more than one, but there are (almost) twice as many nodes in the right subtree as the left one.