What is an AVL tree?

AVL, named after inventors Adelson-Velsky and Landis, is a binary tree that​ self-balances by keeping a check on the balance factor of every node.

Balance Factor

The balance factor of a node is the difference in the heights of the left and right subtrees. The balance factor of every node in the AVL tree should be either +1, 0 or -1.

After each insertion or deletion, if the balance factor of any node does not follow the AVL balance property, the AVL tree balances itself through the following rotation techniques:

• Left Rotation
• Right Rotation
• Left-Right Rotation
• Right-Left Rotation

Time Complexity

Due to the balancing property, the insertion, deletion and search operations take $O(log n)$ in both the average and the worst cases. Therefore, AVL trees give us an edge over Binary Search Trees which have an $O(n)$ time complexity in the worst case scenario.

Space Complexity

The space complexity of an AVL tree is $O(n)$ in both the average and the worst case.