Binary Search Tree (BST) becomes ineffective, O(n) worst case if not balanced. Any practical usage of BST requires a balanced tree. AVL tree is a self-balancing binary search tree which guarantees O(log n) performance.
- AVL tree balances itself on insertion and deletion.
- Balancing is done by computing the balance factor for every node. A node in a tree is unbalanced if its absolute(balance factor) > 1. That means a node stays balanced if it’s left and right sub-tree are in the same level or in difference of one level.
- Balance factor = (height of left sub-tree ) – (height of right sub-tree)
- Once a node is determined as unbalanced, balancing the node is done using rotations.
- 4 kinds of rotations – well explained in tutorialpoint.