AVL, keys where rotations are not required

76 Views Asked by At

Suppose the keys {1,2,3.....,n} are inserted into n empty AVL tree in sequence 1,2,3.....,n. Find the key values(1,2...n these are the keys) where rotation(rotations to balance the tree structure) is not required while inserting them. At which points of inserting the number does the requirement for re-balancing not arise, that the main question

Now what i noticed, is that rotation is not required for the nodes 1,2,4,8.... by brute force method, but cannot prove it. I added number manually to the AVL tree and came to know that rotations are not required for 1,2,4,8..... Now how do I prove it? I have an intuition that its something got to do with the power of 2 or the tree a condition of the nodes having 2 children, but cannot really relate it to the problem. Please help!