众所周知，从 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 树是多少？
A tree of four nodes requires a single rotation in the worst case. The worst case number of deletions increases with each term in the list: 4, 12, 33, 88, 232, 609, 1596, 4180, 10945, 28656, ...
This is Sloane's A027941 and is a Fibonacci-type sequence that can be generated with N(i)=1+N(i-1)+N(i-2) for i>=2, N(1)=2, N(0)=1.
To see why this is so, first note that rotating an imbalanced AVL tree reduces its height by one because its shorter leg is lengthened at the expense of its longer leg.
When a node is removed from an AVL tree, the AVL algorithm checks all of the removed node's ancestors for potential rebalancing. Therefore, to answer your question we need to identify trees with the minimum number of nodes for a given height.
In such a tree every node is either a leaf or has a balance factor of +1 or -1: if a node had a balance factor of zero this would mean that a node could be removed without triggering a rebalancing. And we know rebalancing makes a tree shorter.
Below, I show a set of worst-case trees. You can see that following the first two trees in the sequence, each tree is constructed by joining the previous two trees. You can also see that every node in each tree is either a leaf or has a non-zero balance factor. Therefore, each tree has the maximum height for its number of nodes.
For each tree, a removal in the left subtree will, in the worst case, cause rotations which ultimately reduce the height of that subtree by one. This balances the tree as a whole. On the other hand, removing a node from the right subtree may ultimately imbalance the tree resulting in a rotation of the root. Therefore, the right subtrees are of prime interest.
You can verify that Tree (c) and Tree (d) have one rotation upon removal, in the worst case.
Tree (c) appears as a right subtree in Tree (e) and Tree (d) as a right subtree in Tree (f). When a rotation is triggered in Tree (c) or (d) this shortens the trees resulting in a root rotation in Trees (d) and (f). Clearly, the sequence continues.
If you count the number of nodes in the trees this matches my original statement and completes the proof.
(In the trees below removing the highlighted node will result in a new maximum number of rotations.)
我不擅长打样，我敢肯定下面充满了漏洞，但也许它会激发一些积极的东西。
要在删除节点后对最小化的 AVL 树进行 k 次旋转，必须满足以下条件：
最小化树的高度和节点数通过以下等式计算。
令 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 次旋转的最小子树是 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.
令 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)
/ \ / \
. . . .
\ \
. .