我一直在阅读关于 AVL 树的文献，发现它没有详细说明在 AVL 树插入/删除中需要多少平衡检查。
比如插入一个节点后，是否需要检查从新节点到根节点的余额？或者我们可以在轮换完成后停止吗？
使用复制左子树中最右边节点的策略进行删除怎么样？从新删除的(左子树中最右边的节点)节点到根节点查找？我们可以在轮换完成后停止吗？
最佳答案
插入后，需要更新树上每个“父”的平衡因子，直到根；所以它是 O(log n) 更新的最大值。但是您只需进行一次重组即可将树恢复到它的不变量。
在删除之后，就像插入一样，您将必须一直更新树上的平衡因子；所以又是 O(log n) 更新。但是，与插入不同，您可能有多个重组旋转来将树恢复到它的不变量。
关于algorithm - 一次 AVL 树插入/删除需要多少次余额检查，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19714840/