英文:
AVL Tree Which Has 11 Nodes and Answers Requirements
问题
我试图找到一个由11个节点组成的AVL树，满足以下要求：
- 我们可以连续删除任意两个节点，树的高度保持不变。
- 我们可以添加任何一个节点，树的高度也保持不变。
注意：当我们删除一个节点并插入一个节点时，我们使用旋转（RR、LL、RL、LR）来平衡它。
请找到一个满足问题要求的AVL树。
英文:
I am trying to find an AVL tree composed of 11 nodes, such that it answers the following requirements:
- We can remove any 2 nodes (one after the other) and the tree's height will remain unchanged.
- We can add any 1 node and the tree's height will remain unchanged.
Note: When we delete a node and insert a node to the tree we balance it using rotations (RR, LL, RL, LR).
Find an AVL tree which answers the requirements in the question.
答案1
得分: 0
这棵树可能是这样的：
6
/
3 9
/ \ /
2 4 8 10
/ \ /
1 5 7 11
这棵树的左子树和右子树具有相同的形状。它们各包含两个“腿”，总共有四条腿。
删除
无论首先删除哪个节点，都将导致四条腿中的一条变短。这不会导致旋转。例如，如果删除根节点的值，7将取而代之，将9-8-7腿缩短为只有9-8。
当删除第二个节点时，要么它缩短了不同的腿且不需要旋转，要么与上次删除相同的腿（如前一次删除）再次缩短：在这种情况下，单旋转将解决不平衡问题。
无论哪种方式，原始树至少会有两条腿没有被这两次删除缩短，因此无论删除哪两个节点，树的高度都保持不变。
插入
如果新节点的父节点不是叶子节点（即其父节点是2、4、8或10中的一个），则不会发生旋转，树的高度也不受影响。
否则，新节点将插入到四个叶子节点之一下方，使其中一条“腿”变长。这将触发单旋转或双旋转，从而恢复树的原始高度。
英文:
It could be this tree:
____6____
/ \
3 9
/ \ / \
2 4 8 10
/ \ / \
1 5 7 11
This tree's left and right sub trees have the same shape. They consist of two "legs" each, four legs in total.
Deletions
Whichever node is first deleted, it will result in one of the four legs getting shorter. This will not result in a rotation. For instance, if the root value is deleted, 7 will take its place, shortening the the 9-8-7 leg to just 9-8.
When a second node is deleted, either it shortens a different leg and no rotation is needed, or the same leg (as in the previous deletion) is shortened again: in that case a single rotation will resolve the imbalance.
Either way, there will be at least two legs of the original tree that were not shortened by the two deletions, and so the tree's height remains the same whichever two nodes are deleted.
Insertion
If the new node gets a parent that is not a leaf (i.e. its parent is either 2, 4, 8 or 10), then no rotation happens and the tree's height is not affected.
Otherwise the new node is inserted below one of the four leaves, making one "leg" longer. This will trigger a single or double rotation, which restores the original height of the tree.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论