More than one rotation needed to balance an AVL Tree?

data-structures tree rotation binary-tree avl-tree
kBisla picture kBisla · Jan 3, 2014 · Viewed 7.7k times · Source

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.

Answer

IanWalker0421 picture IanWalker0421 · Jan 3, 2014

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.

Related questions

How to implement a tree data-structure in Java?

Is there any standard Java library class to represent a tree in Java? Specifically I need to represent the following: The sub-tree at any node can have an arbitrary number of children Each node (after the root) and it's children …

Read More
How can I implement a tree in Python?

I am trying to construct a General tree. Are there any built-in data structures in Python to implement it?

Read More
What is the difference between tree depth and height?

This is a simple question from algorithms theory. The difference between them is that in one case you count number of nodes and in other number of edges on the shortest path between root and concrete node. Which is which?

Read More