I am wondering if there is fundamental issue for AVL tree re-balancing. According to several tutorials, for AVL insertion, maximum 2 rotates it can be balanced. However, it may depend what is called as balanced. Follow link to see the tree.
Originally it has 6 elements. Assume that we inserted the last value as 3 or 4.5 or 5.5 or 6.5. Anyway, it will be inserted on the left side of the bottom. As total 7 element tree, for perfect balancing, I will consider it has only 3 rows.
This will force the new root is 6 or 6.5 (if we insert 6.5). I really cannot figure out a way to rebalancing it within 2 rotations. If we only depends on the "balance" definition, 4-rows is still called balanced, but it will result more searching time.
Am I missing something?
In case the picture got deleted, below is a text version:
7
5 9
4 6 8 Empty_slot
3 or 4.5 or 5.5 or 6.5
As you can read on wikipedia
In an AVL tree, the heights of the two child subtrees of any node differ by at most one
That doesn't imply that you have a complete tree ! See examples of balances tree in the wikipedia page linked.
So for any of the insertion you propose you tree will still be balanced (for the common definition of balanced) after the insertion
on the one side of the root you'll have the subtree
5
4 6 height 2
3 # # #
and on the oder side you would have the subtree
9
8 # height 1
As thoses 2 subtrees only have a difference of height of 1, so it's ok ... and you can check that this property is true for all nodes