问当删除操作导致2次旋转时，最小的AVL树大小是多少？

EN

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

这是Sloane's A027941，是一个斐波那契类型的序列，可以用N(i)=1+N(i-1)+N(i-2)为i>=2, N(1)=2, N(0)=1生成。

要了解为什么会这样，首先要注意的是，旋转不平衡的AVL树会将其高度降低1，因为它的短腿是以牺牲它的长腿为代价的。

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

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

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

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

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

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

如果计算树中的节点数，则匹配我的原始语句并完成证明。

(在下面的树中，移除高亮显示的节点将导致新的最大旋转次数。)

​

​

我不擅长证明，我相信下面的文章充满了漏洞，但也许它会引发一些积极的东西。

要在删除节点后对最小化的AVL树进行k次旋转，必须满足以下条件：

• 目标节点必须存在于包含4个节点的子树中。
• 目标节点必须位于短分支上，或者必须是子树的根并替换为短分支的叶。
• 目标子树根的祖先中的每个节点必须稍微失衡(平衡系数为+/-1)。也就是说，当遇到平衡因子0时，旋转链将停止。

最小化树的高度和节点数是用以下公式计算的。

• 设H(k) =受k次旋转影响的树的最小高度。

H(k) = 2k + 1，k>0

• 设N( h ) =高度为h的(最小节点) AVL树中的节点数。

N(0) =0 N(1) =1 N(h) = N(h-1) + N(h-2) + 1，h>1

• 设F(k) =树中受k次旋转影响的最小节点数。

F(k) = N(H(k))

(例如：)

k = 1, H(k) = 4, N(4) = 7
k = 2, H(k) = 6, N(6) = 20

证据(如它是)

最小高度

删除操作只能导致包含4个或更多节点的树进行轮换。

• 包含1个节点的树必须具有平衡因子0。
• 包含2个节点的树必须具有平衡因子+/-1，删除操作将生成包含1个节点的平衡树。
• 包含3个节点的树必须具有平衡因子0。删除节点会导致平衡因子为+/-1，并且没有旋转从少于4个节点的树中删除occurs.
• Therefore，不会导致旋转。

删除时发生1次旋转的最小子树是4个节点，其高度为3。删除短边中的节点将导致旋转。同样，删除根节点，使用短边的节点作为替换，将导致旋转。树是如何配置的并不重要：

  B        B     Removal of A or replacement of B with A               
 / \      / \    results in rotation. No rotation occurs
A   C    A   D   on removal of C or D, or on replacement 
     \      /    of B with C.
      D    C     

    C      C     Removal of D or replacement of C with D
   / \    / \    results in rotation. No rotation occurs
  B   D  A   D   on removal of A or B, or on replacement
 /        \      of C with B. 
A          B     

从4节点树中删除会得到高度为2的平衡树。

  .
 / \
.   .

要实现第二次旋转，目标树必须具有高度为4的同级树，以便根的平衡因子为+/-1 (因此高度为5)。受影响的树是在父树的右侧还是左侧并不重要，兄弟树的布局也不重要(即H4的H3子级可以在左侧或右侧，并且可以是上述4个方向中的任何一个，而H2子级可以是2个可能的方向中的任何一个-这需要证明)。

   _._              _._
  /   \            /   \
(H4)   .          .   (H4)
      / \        / \
     .   .      .   .
          \          \
           .          .

很明显，第三次旋转要求受影响树的祖父母同样不平衡+/-1，第四次旋转要求曾祖父母不平衡+/-1，以此类推。

根据定义，子树的高度是每个分支的最大高度加上根的最大高度。一个同级必须比另一个同级高1，才能实现根中的+/-1不平衡。

H(1) = 3 (as observed above)
H(k) = 1 + max(H(k - 1), H(k - 1) + 1)) = 1 + H(k - 1) + 1 = H(k - 1) + 2
... Inductive proof leading to H(k) = 2k + 1 eludes me.

最小节点数

• 根据定义，子树中的节点数是左分支中的节点数加上右分支中的节点数加上根的节点数。
• 也是这样定义的，高度为0的树必须有0个节点，高度为1的树必须没有分支，因此有1个节点。
• 如上所示，一个分支必须比另一个短。
• 设N(h) =创建高度为h的树所需的最小节点数：

N(0) =0 N(1) =1 //两个子树的节点数加上根N(h) = N(h-1) + N(h-2) + 1

推论

• 最小节点数不一定是大型树中的最大节点数。简而言之：

从下面的树中删除A，并观察到高度在旋转后没有变化。因此，父级中的平衡系数不会改变，也不会发生额外的旋转。

  B          B           D
 / \          \         / \
A   D    =>    D   =>  B   E  
   / \        / \       \    
  C   E      C   E       C

然而，在k=2的情况下，如果H(4)在这里最小化并不重要-第二次旋转仍然会发生。

   _._              _._
  /   \            /   \
(H4)   .          .   (H4)
      / \        / \
     .   .      .   .
          \          \
           .          .

问题

• 目标子树的位置是什么？显然，对于k= 1，它是根，而对于k= 2，如果根的平衡因子为-1，则它是左边，否则是右边。有没有一个公式来确定k >= 3的位置？
• 一棵树可以包含多少个最大节点来影响k个旋转？在祖先中是否可以有一个不旋转的中间节点，尽管它的父节点是？