1
$\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
$\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?"

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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