- AVL tree is a height balanced tree.
- It is a self-balancing binary search tree.
- AVL tree is another balanced binary search tree.
- It was invented by Adelson-Velskii and Landis.
- AVL trees have a faster retrieval.
- It takes O(logn) time for addition and deletion operation.
- In AVL tree, heights of left and right subtree cannot be more than one for all nodes.
- The above tree is AVL tree because the difference between heights of left and right subtrees for every node is less than or equal to 1.
- The above tree is not AVL because the difference between heights of left and right subtrees for 9 and 19 is greater than 1.
- It checks the height of the left and right subtree and assures that the difference is not more than 1. The difference is called 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 subtree of C has height 2 and the right subtree has height 0, so the difference is 2. In the third tree, the right subtree 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.
BalanceFactor = height(left-sutree) − height(right-sutree)
Rotation in AVL Tree:
To balance itself, an AVL tree may perform the following four kinds of rotations −
The first two rotations are single rotations and the next two rotations are double rotations. To have an unbalanced tree, we at least need a tree of height 2. With this simple tree, let's understand them one by one.
