如果插入之后，在AVL树中删除后可能需要多次旋转，所以最多需要多次旋转？

Question

我明白，在删除后，您必须回溯以更新祖先，并且插入后，您可以执行类似但在大多数情况下，将执行最多一次旋转。

问题是为什么这两个操作的潜在旋转数量有差异。

对我来说，似乎这些操作应该相互反转，但它们的属性中的这种差异表明他们不是。为什么？

Answer 1

将一个元素添加到集合，与删除一个元素从集合删除，确实是对称的操作。你是对的。

然而，在该组由树表示的情况下，两种操作变得不对称。当添加项目时，一个分支可能太长，并且一个良好的旋转将重新平衡。当删除项目时，一个分支可能太短，并且重新平衡所需的本地旋转将改变当前树的高度，因此我们可能被迫在其他斑点重复旋转。

所以似乎“太长”而“太短”对树旋转不对称。

还有各种其他集合表示，不与添加和删除对称。

我们可以保留为无序阵列。添加很容易，只需在最后放置一个新项目。删除稍微困难。假设我们实际上找到了该项目，它在数组中删除，然后将最后一个项目移至打开位置。

我们也可以保留设置为hash-tables，与打开地址。然后添加具有标准解决方案，但删除很难，因为以天真的方式执行它可能会使其他项目无法追踪（当我们有线性探测之外的方法时）。