I am watching 开发者_C百科a lecture from IIT about data structures ( Dr.naveen garg ) About AVL tree.
My Question : Why the height of T2 can't be (h-1)?
The assumption is that the tree is balanced after the insertion WITHOUT rotation.
If rotation occured - it's a different case and you deal with it with ROTATION, I figure it out from "Since X remains balanced.."
this is the assumption, and we are showing in here that the tree stays balanced only in this case.
if ht(T2) were to be (h-1) like you said, then the tree would be unbalanced AFTER insertion. Which is not part of the ASSUMPTION in the question.
Because the balance factor of x will now be 2. Thus a rotation would have to take place.
精彩评论