AVL tree -What if the input to binary search tree comes in a
sorted (ascending or descending)
Manner? It will then look like this –
It is observed that BST's worst-case performance is
closest to linear search algorithms,
that is Ο (n). In real-time data, we cannot predict
data pattern and their frequencies. So,
a need arises to balance out the existing BST.
Named after their inventor Adelson, Velski &
Landis, AVL trees are
height balancing
binary search tree. AVL tree checks the height of the
left and the right sub-trees and
assures that the difference is not more than 1. This
difference is called the Balance
Factor.
Here we see that the first tree is balanced and the
next two trees are not balanced –
In the second tree, the left sub tree of C has
height 2 and the right sub tree has height 0,
so the difference is 2. In the third tree, the right
sub tree of A has
height 2 and the left is
missing, so it is 0, and the difference is 2 again.
AVL tree permits difference (balance
factor) to be only 1.