AVL TREES
What is an AVL tree?
Adelson-Velsky and Landis (AVL) Trees are self-balancing
Binary Search Trees which use rotations to maintain balance.
Balance is tracked using a balance factor.
How do we calculate the balance factor?
At a node v, the balance factor is the height of the
left subtree minus the height of the right subtree.
A node v is balanced if |bf (v)| < 2
- bf(v) < -1 indicates that the left subtree is smaller
than the right subtree.
- bf(v) > 1 indicates that the left subtree is larger
than the left subtree.
- bf(v) = 0 indicates both subtrees are of equal height.
- A binary tree is an AVL tree when every node is balanced.
To read more in detail about AVL trees check here.