Insertion

Insertion in AVL tree is starts out similar to regular binary search trees. That is we do the following:

• Find the appropriate empty subtree where new value should go by comparing with values in the tree.
• Create a new node at that empty subtree.
• New node is a leaf and thus will have a height balance of 0
• go back to the parent and adjust the height balance.
• If the height balance of a node is ever more than 1 or less than -1, the subtree at that node will have to go through a rotation in order to fix the height balance. The process continues until we are back to the root.
• NOTE: The adjustment must happen from the bottom up

Example

Suppose we have start with the following tree (value on top is the value, value on bottom is the height balance

Insert 30

At this point, we have adjusted all the height balances along the insertion path and we note that the root node has a height balance of 2 which means the tree is not height balanced at the root.

In order to fix our tree, we will need to perform a rotation