删除导致2个旋转的最小AVL树大小是多少？ [英] What is the minimum sized AVL tree where a deletion causes 2 rotations?
问题描述
众所周知，从AVL树中删除可能会导致多个节点最终失衡。我的问题是，需要进行2轮旋转的最小尺寸的AVL树是多少（我假设左右或左右旋转为1轮）？我目前有一个带有12个节点的AVL树，删除将导致2个旋转。我的AVL树按以下顺序插入：
8、5、9、3、6、11、2、4、7、10、12、1。
如果删除10，则9将变得不平衡并发生旋转。这样做，8变得不平衡，并发生另一个旋转。
在删除jpalecek的评论后，我真正的问题是：给定常数k，最小的AVL是多少？
由四个节点组成的树在最坏的情况下需要旋转一圈。删除中最坏情况的数目随着列表中的每个术语而增加：4、12、33、88、232、609、1596、4180、10945、28656，...
这是 Sloane的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）在移除后是否旋转一圈。 / p>
树（c）在树（e）中显示为右子树，树（d）在树（f）中显示为右子树。当在树（c）或（d）中触发旋转时，这会缩短树，从而导致树（d）和（f）中的根旋转。显然，序列继续进行。
如果您计算树中的节点数，这将与我的原始语句匹配并完成证明。
（在下面的树中，删除突出显示的节点将导致新的最大旋转次数。）
It is well known that deletion from an AVL tree may cause several nodes to eventually be unbalanced. My question is, what is the minimum sized AVL tree such that 2 rotations are required (I'm assuming a left-right or right-left rotation is 1 rotation)? I currently have an AVL tree with 12 nodes where deletion would cause 2 rotations. My AVL tree is inserting in this order:
8, 5, 9, 3, 6, 11, 2, 4, 7, 10, 12, 1.
If you delete the 10, 9 becomes unbalanced and a rotation occurs. In doing so, 8 becomes unbalanced and another rotation occurs. Is there a smaller tree where 2 rotations are necessary after a deletion?
After reading jpalecek's comment, my real question is: Given some constant k, what is the minimum sized AVL tree that has k rotations after 1 deletion?
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.)
这篇关于删除导致2个旋转的最小AVL树大小是多少？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
