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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://cathyatseneca.gitbook.io/data-structures-and-algorithms/avl_trees/insertion.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.