In Data Structures, AVL tree (Adelson-Velsky and Landis tree) is a height-balanced binary search tree in which difference between the heights of left subtree and right subtree can be atmost 1. It is a binary search tree where each node associated with a balance factor. If balance factor paired with node is either 1,0, or – 1, it is said to be balanced.
Balance factor = height of left subtree – height of right subtree
It is important for a binary search tree to be balanced so that insertion and deletion require less search time, resulting increased efficiency. It requires O(log n) time to perform deletion, insertion and search operation.
AVL Tree Basic Operations
Search operations
A search operation starts from the root node to all the way downward recursively. The targeted element is compared with the root node, if both are equal then the search would get terminated. If it is smaller than the root node then the search goes on at left subtree. And if the targeted value is greater, then search operation would be performed left subtree recursively.
Insert operation
To insert a given element, AVL first performs search operation, starting from the root node in order to locate the insertion position. Ones a NIL location is found then insertion is performed.
Inserting a new node may increase the chances of AVL tree to get unbalanced, therefore, rotation is performed with the every insertion if required .
AVL Tree Rotations
It is a process of balancing the AVL tree when balance factor is greater than 1 or smaller than -1.
These are the following types of rotation:
Left-Left Rotation
When insertion is performed in the left subtree of the left subtree then LL imbalance occurs and the rotation process perform on this case is therefore known as left left rotation. It is a single rotation.
Right-Right Rotation
When insertion is performed in the right subtree of the right subtree then RR imbalance occurs and the rotation process performed in this case is therefore known as Right-Right rotation. It is a single rotation.
Left Right Rotation
When insertion is performed in the right subtree of the left subtree then LR imbalance occurs and the rotation process performed in this case is therefore known as Left-Right. It is double rotation.
Right Left Rotation
When insertion is performed in the left subtree of the right subtree then RL imbalance occurs and the rotation process performed in this case is therefore known as Right-Left. It is double rotation.
