AVL trees are a self-balanced special type of Binary Search Tree with just one exception:
For each Node, the maximum height difference between the left and right sub-trees can only be one.
If at any point their difference becomes more than one, then re-balancing is applied to make it a valid AVL tree.
In the case of BST, the Big(O) of all three basic operations (Insertion, Deletion, and Searching) takes O(h) time, where “h” is the height of a Binary Search Tree.
In the case of Skewed Trees, the complexity becomes O(n), where “n” is the number of nodes in the tree. Now to improve time complexity, We have to manage the height of the tree to improve time complexity, such that we can bring the time down to O(logn) for performing these basic operations.
As AVL are strictly balanced, AVL Trees are preferred in those applications where the lookup is the most vital operation. The following is an example of a valid AVL Tree:
The AVL tree and other self-balancing search trees like Red Black are useful to get all basic operations done in O(log n) time. The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is the more frequent operation, then AVL tree should be preferred over
Red Black Tree.