平衡AVL树需要多次旋转？ [英] More than one rotation needed to balance an AVL Tree?

问题描述

我最好的猜测是，当您从已经平衡的AVL树中插入或删除一个元素时，一次旋转始终足以平衡AVL树。

是一次旋转总是够吗
一个例子将帮助需要多次旋转。

PS：我只计算RL / LR轮换为一轮。

解决方案

最多只能插入1个旋转。

要删除旋转数由O（log（n））限定。 Log（n）是树的高度。

关于AVL删除的更多解释。
从AVL中删除节点时，可能会导致树不平衡，您必须追溯到不平衡点。如果不平衡点是根。你必须从上到下重新平衡树。

My best guess is that one rotation is always enough to balance an AVL tree when you insert or delete ONE element from an already balanced AVL tree.

Is one rotation always enough? An example will help where more than one rotations are needed.

PS: I count RL/LR rotations as one rotation only.

解决方案

For insert 1 rotation is at most.
For delete the number of rotation is bounded by O(log(n)). Log(n) is the height of the tree.
More explanation on AVL deletion. When you delete a node from AVL you might cause the tree unbalanced, which you have to trace back to the point where it is unbalanced. If the unbalanced point is the root. You have to rebalance the tree from top to bottom.

这篇关于平衡AVL树需要多次旋转？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！