在最坏的情况下，四个节点的树需要一次旋转。最坏情况下的删除数量随着列表中的每个术语而增加：4、12、33、88、232、609、1596、4180、10945、28656，...
This is 斯隆的 A027941 http://oeis.org/A027941是一个斐波那契类型序列，可以通过以下方式生成N(i)=1+N(i-1)+N(i-2) for i>=2, N(1)=2, N(0)=1.
要了解为什么会这样，首先请注意，旋转不平衡的 AVL 树会将其高度降低一倍，因为其较短的腿被延长，但牺牲了较长的腿。
当一个节点从 AVL 树中删除时，AVL 算法会检查所有被删除节点的祖先是否有潜在的重新平衡。因此，为了回答您的问题，我们需要识别给定高度的节点数最少的树。
在这样的树中，每个节点要么是叶子，要么具有+1或-1的平衡因子：如果节点的平衡因子为零，则这意味着可以在不触发重新平衡的情况下删除节点。我们知道重新平衡会使树变短。
下面，我展示了一组最坏情况的树。您可以看到，在序列中的前两棵树之后，每棵树都是通过连接前两棵树来构造的。您还可以看到每棵树中的每个节点要么是叶子，要么具有非零平衡因子。因此，每棵树的节点数都有最大高度。
对于每棵树，在最坏的情况下，左子树的删除将导致旋转，最终将该子树的高度减少一。这平衡了整个树。另一方面，从右子树中删除节点可能最终导致树不平衡，导致根旋转。因此，正确的子树是最重要的。
您可以验证在最坏的情况下，树 (c) 和树 (d) 在移除后有一次旋转。
树(c)作为树(e)的右子树出现，树(d)作为树(f)的右子树出现。当树 (c) 或 (d) 中触发旋转时，这会缩短树，从而导致树 (d) 和 (f) 中的根旋转。显然，这个序列还在继续。
如果你计算树中的节点数量，这与我原来的陈述相符并完成了证明。
（在下面的树中，删除突出显示的节点将导致新的最大旋转数。）
