8
$\begingroup$

Is it true that inserting an element to an AVL tree requires $O(1)$ rotations?

How many rotations, does deletion from AVL require?

I've searched for these two questions with no luck so far.

$\endgroup$

1 Answer 1

5
$\begingroup$

The obvious resource, Wikipedia, I did not find very helpful.

When inserting an element at most one (single or double) rotation is needed, at the lowest point where the tree is out of balance. After rotation the height of that subtree is the same as in the original subtree, so all nodes upwards are balanced. See the answer by colleague Raphael to "Does the rebalancing propagate upwards only to update the height of the nodes in an AVL tree?"

picture: originaly the balance at node $p$ equals $-1$ (left subtree one deeper than right subtree). After insertion in the left subtree the balance is now $-2$. Then rebalancing at $p$ will restore the balance at the root to $0$, while at the same time the heigth of the tree at new root $q$ is now the same as for the original tree. This means that all balance factors above will not change.

rebalance AVL tree

When deleting occurs, one is not always that lucky. Rotation does not necessarily restore the original tree height, so the tree has to be updated at other levels higher up in the tree. Worst case trees are those which are minimal AVL trees, meaning with no node can be removed without violating the AVL property. There you might have to rotate every level, thus a logarithmic number of times.

picture: an AVL tree of "Fibonacci" type. Deleting the node marked "X" results in unbalance at $11$. Rebalancing at $11$ leads to a tree that is shorter than the original tree, and we get an new imbalance at the root. Another rotation will solve that problem. Note that again the resulting tree is shorter than the original one, so this would propagate to levels above.

deletion in example AVL tree

$\endgroup$
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.