AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right subtrees cannot be more than one for all nodes.
An Example Tree that is an AVL Tree
The above tree is AVL because differences between heights of left and right subtrees for every node is less than or equal to 1.
Operations on an AVL tree
Various operations that can be performed on an AVL tree are:
Rotating the subtrees in an AVL Tree
In rotation operation, the positions of the nodes of a subtree are interchanged.
There are two types of rotations:
Left Rotation :
In left-rotation, the arrangement of the nodes on the right is transformed into the arrangements on the left node.
Algorithm
1: Let the initial tree be:
2: If y has a left subtree, assign x as the parent of the left subtree of y.
3: If the parent of x is NULL, make y as the root of the tree.
4: Else if x is the left child of p, make y as the left child of p.
5: Else assign y as the right child of p.
6: Make y as the parent of x.
