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

问题描述

我最好的猜测是，当您从已经平衡的 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:我只将 RL/LR 旋转算作一次旋转.

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

推荐答案

对于 insert 最多旋转 1 圈.
对于删除，旋转次数以 O(log(n)) 为界.Log(n) 是树的高度.
关于 AVL 删除的更多解释.当你从 AVL 中删除一个节点时，你可能会导致树不平衡，你必须追溯到它不平衡的点.如果不平衡点是根.您必须从上到下重新平衡树.

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屋！