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
but what about balancing?
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
the height difference is 2 so it will beCode:a \ b \ c
b) right rotationCode:b / \ a c
the height difference is -2 so it will beCode:c / b / a
c) left right rotationCode:b / \ a c
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?
thanks in advance