# AVL tree insertion

• 12-04-2010
nik
AVL tree insertion
Hello,

I have a problem with implementing the insertion in AVL tree.

I have coded everything except the insert method. I have some other methods about the preorder, postorder etc, I managed to create the code about height, which will help me balance the tree every time I put new value in it

I have the height and I have the code for a simple insertion in binary search tree.

the insertion I've coded uses simple loops, basically what I'm doing is I create the new node and check every time its value, if it's bigger I change the current pointer to go to right, else left, until it reaches a NULL value which means that it's the end and we need to put the new node there

I know that in AVL we have 4 different cases at most, please correct me if I'm wrong

So we have

a) left rotation

for example if we have

Code:

```a  \   b   \     c```
the height difference is 2 so it will be
Code:

```  b  / \ a  c```
b) right rotation

Code:

```  c   /   b  / a```
the height difference is -2 so it will be

Code:

```   b  / \ a  c```
c) left right rotation

here I'm not 100% sure.. if I understand it correctly I need to find every time the node where the height difference has a difference of 2, then if the right subtree is left heavy then we need to make a right rotation to the subtree and a left to the root node

d) right left rotation, again I'm not 100% sure, here it's the opposite, if the left subtree is right heavy we need to make a left rotation to the left subtree and right to the root node

Is it just these 4 cases, or is there anything more? The problem is that I don't know how to make the code for the rebalancing...

I don't have any parent nodes.. just left and right...

I've heard recursion works well in AVL, but I don't know how to use it here..

any suggestions on how to move from a simple BST insertion method to an AVL insertion method?