权重不平衡AVL树

Question

相信维基百科文章：http://en.wikipedia.org/wiki/AVL_tree

AVL树高度平衡，但一般不平衡重量，也不平衡μ；[4] 也就是说，同级节点的子节点数量可能相差很大。

但是，作为AVL树是：

自平衡二叉查找树[...]。在AVL树中，任何节点的两个子树的高度最多相差一个

我不明白AVL怎么会是重量不平衡的，因为——如果我很好地理解AVL树的定义——每个兄弟姐妹都会有大约相同数量的孩子，因为他们有相同的身高 /-1。

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

谢啦

Answer 1

兄弟节点可以有非常不同数量的后代。

我只是在挠头，我的AVL实现生成的树并不是最终不平衡的，而是内部有越来越大的“远亲”子树。

我勾勒出这个来安慰自己：

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

Answer 2

您的理解是正确的，AVL树是由其边缘节点的几乎均匀的高度定义的，但您的困惑似乎是关于节点位置和边缘权重之间的差异。

也就是说：在AVL树中，边缘节点的深度将与 /-相同（但不是两者！）。这不会对节点之间的边缘相关的成本提出索赔。对于具有根节点和两个子节点的AVL树，左路径的遍历成本可能是右路径的两倍。这将使树权重不平衡，但仍保持AVL树的定义。

此页面有更多信息：权重平衡树-维基百科

来自维基百科：

|N|是以N为根（包括根）的树下的节点数，Nl是N的左子树。

本质上，这意味着AVL树中的子级不一定均匀分布在树的最低级别。以N表示树的根节点，可以构造一个有效的AVL树，该树在根的左侧比右侧有更多的子级。对于非常深的树，此底层可能有许多节点。

AVL树的定义要求它们都位于最深点之一内，但不能保证它们相对于节点N是哪个节点的子节点。