重量不平衡的AVL树

Question

AVL树是高度平衡的,但通常不是重量平衡的,也不是μ平衡的; [4]也就是说,兄弟节点可以有非常不同数量的后代.

但是,作为AVL树是:

自平衡二进制搜索树[...].在AVL树中,任何节点的两个子子树的高度最多相差一个

我不知道AVL是如何重量不平衡的,因为如果我理解AVL树的定义,每个兄弟都会有大约相同数量的孩子,因为他们有相同的身高+/- 1.

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

谢谢

Answer 1

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

\n\n

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

\n\n

\n\n

来自维基百科：

\n\n

\n
二叉树称为 \xce\xbc-balanced，其中，如果对于每个节点 N，不等式：\n
\n\n
成立且 \xce\xbc 在此属性下是最小的。|N| 是以N为根（包括根）的树下的节点数，Nl是N的左子树。
\n

\n\n

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

\n\n

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

\n

Answer 2

兄弟节点可以有很多不同数量的后代.

我只是对这个问题感到头疼,事实上我的AVL实现产生的树木最终并不是不平衡的,而是里面有越来越大的"远亲"子树.

我勾勒出这一点来安抚自己:

在此输入图像描述

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