开发者

AVL tree insertion question

开发者 https://www.devze.com 2023-02-15 00:00 出处:网络
I am watching 开发者_C百科a lecture from IIT about data structures ( Dr.naveen garg ) About AVL tree.

I am watching 开发者_C百科a lecture from IIT about data structures ( Dr.naveen garg ) About AVL tree.

AVL tree insertion question

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.

0

精彩评论

暂无评论...
验证码 换一张
取 消

关注公众号