0

我想知道 AVL 树重新平衡是否存在根本问题。根据几个教程，对于 AVL 插入，最多 2 次旋转它可以平衡。但是，这可能取决于所谓的平衡。按照链接查看树。

最初它有6个元素。假设我们将最后一个值插入为 3 或 4.5 或 5.5 或 6.5。无论如何，它将被插入底部的左侧。总共有 7 个元素树，为了完美平衡，我认为它只有 3 行。

这将强制新根为 6 或 6.5（如果我们插入 6.5）。我真的想不出一种在 2 次旋转内重新平衡它的方法。如果我们只依赖“平衡”的定义，4-rows 仍然被称为平衡，但它会导致更多的搜索时间。

我错过了什么吗？

如果图片被删除，下面是文字版本：

                               7
              5 9
           4 6 8 空槽
       3 或 4.5 或 5.5 或 6.5
4

1 回答 1

2

正如你可以在维基百科上阅读的

在 AVL 树中，任何节点的两个子子树的高度最多相差 1

这并不意味着你有一棵完整的树！请参阅链接的维基百科页面中的余额树示例。

因此，对于您建议的任何插入，您的树在插入后仍将是平衡的（对于平衡的通用定义）

在根的一侧，您将拥有子树

      5
  4       6        height 2 
3   #   #   #

在奥德方面，您将拥有子树

  9
8   #              height 1

由于那些 2 子树只有 1 的高度差，所以没关系......你可以检查这个属性是否适用于所有节点

于 2015-04-28T01:56:04.903 回答