什么是最小尺寸的AVL树，其中一个缺失导致2转？(What is the minimum sized

众所周知，从AVL树的缺失可能会导致几个节点，最终是不平衡的。我的问题是，什么是最小尺寸的AVL树，从而需要2个旋转（我假设左右或左右旋转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，...

这是斯隆的A027941 ，并且是可与所生成的斐波那契型序列N(i)=1+N(i-1)+N(i-2)为i>=2, N(1)=2, N(0)=1 。

要知道为什么会这样，首先说明一个旋转不平衡的AVL树降低了它的高度，因为它的短支脚在其较长的边为代价延长。

当一个节点从AVL树移除，AVL算法检查所有拆下的节点的祖先潜在的再平衡。因此，要回答你的问题，我们需要有一个给定的高度的最小节点编号来识别树木。

在这种树的每个节点是叶或具有+1或-1的平衡因素：如果一个节点有一个零余额的因素，这将意味着一个节点可以在不触发重新平衡被删除。而我们知道的再平衡，使树更短。

下面，我将展示一套最坏情况下的树木。你可以看到以下序列中的第一个两棵树，每棵树是通过将以前的两棵树制成。你也可以看到，在每个树的每一个节点是叶或具有非零平衡因素。因此，每棵树都有其节点数的最大高度。

对于每一个树，在左子树的移除会，在最坏的情况下，引起的旋转最终减少一个该子树的高度。这种平衡树作为一个整体。在另一方面，从右边的子树删除节点可能最终不平衡导致根的旋转树。因此，右子树是主要关注的。

您可以验证树（c）和树（d）在去除有一个旋转，在最坏的情况下。

树（c）中显示为树（e）和树（d）一右子树作为树一个右子树（F）。当旋转在树（c）或（d）被触发此缩短导致根旋转树（d）和（f）的树木。显然，该顺序继续。

如果算上在树上的节点数这个符合我原来的语句，并完成了证明。

（在下面除去所述突出显示的节点将导致旋转的新的最大数目的树。）

Answer 2:

我不擅长的证明，我敢肯定，下面的是千疮百孔，但也许它会引发一些积极的。

到上的节点的删除下面的最小化的AVL树实现ķ旋转，在下列条件必须满足：

目标节点必须存在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

证明（如它是）

Minimum Height

缺失只会导致与4级或更多的节点树的旋转。

1个节点的树必须具有为0的平衡因素。
2个节点的树必须有一个±1的平衡因子，并缺失导致1个节点的平衡树。
3个节点的树必须具有0去除的节点的结果的平衡因子在+/- 1的平衡因子和不发生旋转。
因此，从具有少于4个节点树的删除不能导致的旋转。

对于其中上删除发生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.

Minimum Nodes

根据定义，一个子树节点的数量为节点的左支加根的数量的节点在右支数加1。
也有定义，高度为0的树必须有0的节点，和高度1必须没有分支的树，因此1个节点。
据以上所述一个分支所示必须比另一个短。

令N（H）=创建高度h的树所需的节点的最小数量：

 N(0) = 0 N(1) = 1 // the number of nodes in the two subtrees plus the root 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)
      / \        / \
     .   .      .   .
          \          \
           .          .