AVL

AVL

What is AVL?

AVL is a self balancing tree where the height difference between left and right is less than 2 nodes.AVL useful for make searching more effectively.

Important things that you might know:

-Node Height:

•  empty subtree = 0
•  leaf = 1
•  maximum height of children internal node + 1 

 -Balance factor : the height difference between left subtree and right subtree.

•  maximum balance factor = 1

There are violation in number 17 because the difference between left and right is 2.

So,we need to rebalance it...But how?

How to rebalance Binary tree?

1. Single rotation
2. Double rotation 

 What is Single Rotation?

 

Single rotation is a method of rotation that each node didn't make a branch,so if it's violate in the left,the violation should be on the outer node and continuously move to the left.This applies to the opposite.

 What is Double Rotation?

 

 

 Double rotation happens when the insertion is in the inner branch,so to make it balance you must apply double rotation.

Here it's how to apply double rotation: