algorithm - 删除导致 2 次旋转的最小大小的 AVL 树是多少？

Question

众所周知，从 AVL 树中删除可能会导致几个节点最终不平衡。我的问题是，需要 2 次旋转的最小大小的 AVL 树是多少(我假设左右或左右旋转是 1 次旋转)？我目前有一个包含 12 个节点的 AVL 树，其中删除会导致 2 次旋转。我的 AVL 树按以下顺序插入:

8、5、9、3、6、11、2、4、7、10、12、1。

如果删除 10，9 将变得不平衡并发生旋转。这样做时，8 变得不平衡，并发生另一次旋转。删除后是否有更小的树需要 2 次旋转？

阅读 jpalecek 的评论后，我真正的问题是:给定一些常量 k，在 1 次删除后具有 k 个旋转的最小大小的 AVL 树是多少？

Answer 1

在最坏的情况下，四个节点的树需要单次旋转。最坏情况下删除的数量随着列表中的每个术语而增加:4、12、33、88、232、609、1596、4180、10945、28656，...

这是 Sloane's A027941并且是一个斐波那契类型序列，可以用 N(i)=1+N(i-1)+N(i-2) for i>=2, N( 1)=2, N(0)=1.

要了解为什么会这样，首先请注意，旋转一棵不平衡的 AVL 树会使它的高度降低一个，因为它的较短的腿以其较长的腿为代价而变长。

当从 AVL 树中删除节点时，AVL 算法会检查所有已删除节点的祖先以进行潜在的重新平衡。因此，为了回答您的问题，我们需要确定在给定高度下具有最少节点数的树。

在这样的树中，每个节点要么是叶子，要么具有 +1 或 -1 的平衡因子:如果节点的平衡因子为零，这意味着可以删除节点而不触发重新平衡。我们知道重新平衡会使树变短。

下面，我展示了一组最坏情况的树。您可以看到，在序列中的前两棵树之后，每棵树都是通过连接前两棵树而构建的。您还可以看到每棵树中的每个节点要么是叶子，要么具有非零平衡因子。因此，每棵树都有其节点数的最大高度。

对于每棵树，在最坏的情况下，左子树的移除将导致旋转，最终使该子树的高度减少一。这平衡了整个树。另一方面，从右子树中删除一个节点可能最终会使树不平衡，从而导致根旋转。因此，正确的子树是最重要的。

在最坏的情况下，您可以验证 Tree (c) 和 Tree (d) 在移除时有一个旋转。

树 (c) 在树 (e) 中显示为右子树，而树 (d) 在树 (f) 中显示为右子树。当在树 (c) 或 (d) 中触发旋转时，这会缩短树，从而导致树 (d) 和 (f) 中的根旋转。显然，序列还在继续。

如果您计算树中的节点数，这与我的原始陈述相匹配并完成证明。

(在下面的树中，删除突出显示的节点将导致新的最大旋转数。)