about AVL tree insertion operation

In the standard process of AVL tree insertion, after we insert a new node, we will do adjustment from bottom to top, and during the process, is it possible a sub-tree height increase by one (because of insertion and rotation operation), while the sub-tree (after height increase by one), still have the same height of left/right child? If so, an example is appreciated, and if not, it will be great if anyone could explain why. Thanks. :)

Here is a reference to AVL tree (https://en.wikipedia.org/wiki/AVL_tree)

regards, Lin

It is not possible after the insertion to have the left and right child of the sub-tree to remain same with a change in height.

Lets consider a simple example with only <3 nodes in a sub-tree. The possiblities of balance factor are,

• +1 - which is Root node in subtree with 1 Left Child and no Right child
• -1 - which is Root node in subtree with 1 Right Child and no Left child
• 0 - Root node in subtree has 1 node in Right and Left.

For SubTree with Balance factor +1,

• if we insert into the Right, we are ok
• if we insert into the Left, the balance factor changes to 2. So we need to balance the tree in which case the the height of the subtree is changed.

For SubTree with Balance factor -1,

• if we insert into the Left we are ok
• if we insert into the Right, the balance factor changes to -2. So we need to balance the tree in which case the the height of the subtree is changed.

For SubTree with Balance factor 0,

• if we insert into the Left, we are ok. Height is changed for but the child node is changed as well.
• if we insert into the Right, we are ok. Height is changed for but the child node is changed as well.

So, it is not possible to have the height changed and still have same right and left child heights.