在AVL树插入/删除中需要多少个平衡检查？

Question

我一直在阅读有关AVL树的文献，发现在AVL树插入/删除中需要多少个平衡检查，这一点并没有得到详细的阐述。

例如，插入节点后，是否需要检查从新节点一直到根节点的平衡情况？或者我们可以在轮换之后停止吗？

如果删除的策略是复制左边子树中最右边的节点，情况如何？检查从新删除的节点(左侧子树中的最右边节点)到根节点？我们能在轮换之后停下来吗？

Answer 1

插入之后，您需要更新每个“父”的平衡因子，直到根为止；因此，它是O(log )更新的最大值。但是，您只需进行一次重构就可以将树恢复到它的不变量。

在删除之后，如插入，您将不得不在树的整个过程中更新平衡因子；同样，它也是O(log )更新。但是，与insert不同，您可能有多个重构旋转来将树恢复到它的不变量。

tree

Answer 2

我一直在深入搜索，我发现你什么时候可以停止检查：

• 当插入节点的上节点的平衡因子为0时。
• 在轮换之后。这是前一次确认的结果。

http://www.superstarcoders.com/blogs/posts/efficient-avl-tree-in-c-sharp.aspx

avl.aspx