avl-tree - 权重不平衡的 AVL 树

Question

相信维基百科文章: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.

但是，作为 AVL 树是:

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

我不明白 AVL 是如何实现重量不平衡的，因为 - 如果我很好地理解了 AVL 树的定义 - 每个 sibling 将拥有大致相同数量的 child ，因为他们的高度相同 +/- 1。

那么，你能给我举个不平衡的 AVL 树的例子吗？我没有成功找到一个。因此，或者我误解了 AVL/未加权树的定义，或者维基百科文章是错误的......

谢谢

Answer 1

sibling nodes can have hugely differing numbers of descendants.

我只是在摸索这一点，事实上我的 AVL 实现产生的树最终并不是不平衡的，但里面有越来越大的“远亲”子树。

我勾勒出这一点来让自己放心:



红色节点的余额为 1，绿色节点的余额为 -1，黑色节点的余额为 0。这是一个有效的 AVL 树，因为两个兄弟子树之间的高度差永远不会超过 1，但(几乎)是两倍右子树中的许多节点作为左子树。