2

我一直在阅读有关 AVL 树的文献，发现并没有详细说明在 AVL 树插入/删除中需要多少平衡检查。

例如，插入一个节点后，我们是否需要从新节点一直到根节点检查余额？或者我们可以在轮换完成后停止吗？

使用复制左子树最右边节点的策略进行删除怎么样？从新删除的（左子树中最右边的节点）节点向上检查到根节点？我们可以在轮换完成后停止吗？

4

2 回答 2

1

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

删除后，如插入，您将不得不一直更新平衡因子；所以又是 O(log n) 更新。但是，与插入不同，您可以进行多次重组旋转以将树恢复为其不变量。

http://en.wikipedia.org/wiki/AVL_tree

于 2013-11-01T01:48:34.660 回答
-1

我一直在进行更深入的搜索，并且发现何时可以停止检查：

  • 当插入节点的上层节点的平衡因子为0时。
  • 一个轮回之后。这是前面肯定的结果。

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

http://www.eternallyconfuzzled.com/tuts/datastructures/jsw_tut_avl.aspx

于 2016-01-23T12:47:31.313 回答