- AVL tree is a self-balancing binary search tree in which each node maintains extra information called a balance factor whose value is either -1, 0 or +1.
- Balance factor of a node in an AVL tree is the difference between the height of the left subtree and that of the right subtree of that node.

AVL Rotation
- Left rotation(L) : In left rotations, every node moves one position to left from the current position.
- Right rotation(R) : In right rotations, every node moves one position to right from the current position.
- Left Right rotation(LR) : In left right roation, First every node moves one position to the left, then one position to the right from the current position.
- Right Left rotaton(RL) : In right left rotation, First every node moves one position to the right, then one position to the left from the current position.
Algorithm for insertion
- Insert a new element into the tree using BST's (Binary Search Tree) insertion logic.
- After inserting the element check the Balance Factor of each node.
- When the balance factor of any node comes other than the three values(0,1,-1) then the tree is said to be unbalanced. Then perform the suitable Rotation to make it balanced.
- If there is an imbalance in the left child's right sub-tree, perform a left-right rotation
- If there is an imbalance in the left child's left sub-tree, perform a right rotation
- If there is an imbalance in the right child's right sub-tree, perform a left rotation
- If there is an imbalance in the right child's left sub-tree, perform a right-left rotation
Algorithm for deletion
- If the node to be deleted is a leaf node, it is simply removed from the tree.
- If the node to be deleted has one child node, the child node is replaced with the node to be deleted simply.
- If the node to be deleted has two child nodes then,
- Either replace the node with it’s inorder predecessor , i.e, the largest element of the left sub tree.
- Or replace the node with it’s inorder successor , i.e, the smallest element of the right sub tree.
- If the tree is unbalanced, then perform the suitable rotation to make it balanced.
- If there is an imbalance in the left child's right sub-tree, perform a left-right rotation
- If there is an imbalance in the left child's left sub-tree, perform a right rotation
- If there is an imbalance in the right child's right sub-tree, perform a left rotation
- If there is an imbalance in the right child's left sub-tree, perform a right-left rotation
Algorithm for search
- First compare the searching element with root, if less than root, then recursively call left subtree, else recursively call right subtree.