i wondering if there fundamental issue avl tree re-balancing. according several tutorials, avl insertion, maximum 2 rotates can balanced. however, may depend called balanced. follow link see tree.
originally has 6 elements. assume inserted last value 3 or 4.5 or 5.5 or 6.5. anyway, inserted on left side of bottom. total 7 element tree, perfect balancing, consider has 3 rows.
this force new root 6 or 6.5 (if insert 6.5). cannot figure out way rebalancing within 2 rotations. if depends on "balance" definition, 4-rows still called balanced, result more searching time.
am missing something?
in case picture got deleted, below text version:
7 5 9 4 6 8 empty_slot 3 or 4.5 or 5.5 or 6.5
as can read on wikipedia
in avl tree, heights of 2 child subtrees of node differ @ one
that doesn't imply have complete tree ! see examples of balances tree in wikipedia page linked.
so of insertion propose tree still balanced (for common definition of balanced) after insertion
on 1 side of root you'll have subtree
5 4 6 height 2 3 # # # and on oder side have subtree
9 8 # height 1 as thoses 2 subtrees have difference of height of 1, it's ok ... , can check property true nodes
