What is an AVL Tree?
An AVL tree (named after inventors Adelson-Velsky and Landis) is a Self-Balancing Binary Search Tree (BST). In a normal BST, the left child is smaller and the right child is greater than the parent. But an AVL tree adds one strict rule: The difference in height between the left subtree and right subtree cannot be more than 1. This difference is called the Balance Factor.
- Formula:
Balance Factor = Height of Left Subtree - Height of Right Subtree - Valid Balance Factors for AVL: -1, 0, or +1.
Why is Balancing Necessary? (The Skewed Tree Problem)
Imagine you insert data in a normal Binary Search Tree in ascending order: 10, 20, 30, 40, 50.
Because every number is bigger, it will only keep attaching to the right side, forming a straight line (called a Skewed Tree).
If you want to search for '50', you have to check every single node line-by-line, which takes O(n) time. This defeats the whole purpose of a fast search tree!
By balancing the tree (using AVL Rotations), we ensure the tree stays wide and short. This guarantees that searching, inserting, or deleting any data will always take extremely fast O(log n) time, even in the worst-case scenario.