> For the complete documentation index, see [llms.txt](https://cathyatseneca.gitbook.io/data-structures-and-algorithms/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://cathyatseneca.gitbook.io/data-structures-and-algorithms/avl_trees/insertion.md).

# 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

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fd0c08630afebc6cc34c45d5c5dcc2a9a66a05b1f.png?generation=1588191939325044\&alt=media)

### 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

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F7b8ef01385d0850951fcfd751173b17922935f30.png?generation=1588191940315566\&alt=media)

### Insert 27

We start with our tree:

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F8216b9b1f62dfdf5a3dc8a64362adc0f55aba77b.png?generation=1588191940209026\&alt=media)

Now we find the correct place in the tree and insert the new node and fix the height balances

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2F3c99e72eda4bcb58f17d157ee76b84f27ade553a.png?generation=1588191940143769\&alt=media)

Now, as we reach node 25 and see that it the height balance is +2. If we then look at it's child's height balance we find that it is -1. As the signs are different, it indicates that we need a double rotation. Different signs indicate that the unbalance is in different directions so we need to do a rotation to make it the same direction then another to fix the unbalance.

![](https://2254094223-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M66b4KsHxRGUQlYomYk%2Fsync%2Fa120e242a8fff9ac53ef82ab502a455088eedcdf.png?generation=1588191940159849\&alt=media)