AVL树完美平衡问题

Question

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

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

这将强制新根为 6 或 6.5（如果我们插入 6.5）。我真的想不出在 2 个轮换内重新平衡它的方法。如果只看"balance"的定义，4-rows还是叫平衡的，但是搜索的时间会比较长。

我是不是漏掉了什么？

为了防止图片被删，下面是文字版：

                               7
              5                                9
           4     6                         8        Empty_slot
       3 or 4.5 or 5.5 or 6.5

Answer 1

正如您在 wikipedia

上看到的那样

In an AVL tree, the heights of the two child subtrees of any node differ by at most one

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

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

在根的一侧有子树

      5
  4       6        height 2 
3   #   #   #

在奥德一侧，您将拥有子树

  9
8   #              height 1

因为这 2 个子树只有 1 的高度差，所以没关系......你可以检查这个属性对所有节点都是正确的

AVL树完美平衡问题

AVL tree perfect balancing issue

avl-tree

tree-balancing