AVL Tree

AVL Tree is an type of BST that will automatically balance itself which in turn ensures that we have log(n) time complexity for all the operations

Time Complexity

Operation	Worst
Insert	O(log(n))
Delete	O(log(n))
Search	O(log(n))

Tree Rotations

Binary Tree Invariant should be preserved even after rotation

Right Rotation

function rightRotate(A) 
{
	B = A.left
	A.left = B.right
	B.right = A
	return B
}

Left Rotation
Reverse of Above Function

AVL Tree Invariant (Balanced Factor)

BF(node) = H(node.right) - H(node.left)
Value of BF: -1,0, +1
If Value of BF: -2, +2 perform Rotation on the node to make it balanced

Left Left Case
Right Rotation

Left Right Case
Left Rotation then Right Rotation

Right Right Case
Left Rotation

Right Left Case
Right Rotation then Left Rotation