Data Structures - AVL Tree
AVL (named from their inventors, G.M.Adelson, Velskii & E.M.Landis) tree is binary search tree with a balance condition. The balance condition is determined by the difference between the heights of subtrees of root in the tree. AVL tree ensures that Insertion, Deletion and Search operations take
O(log n) in both average and worst cases. AVL tree is a balanced binary search tree in which the height of left and right subtrees differ by no more than one.
Why AVL Tree?
Let as consider the two cases that are given below:
When we consider case (a):
- If we want to locate 10,it will require two tests, again if we want to locate 50, it requires six tests. Hence the maximum search effort for this BST is O(n). This worst case performance closer to the sequential search algorithms. So we need to balance the unbalanced BST.
- If we want to locate the value 8 and 50, this search needs only 3 tests. So the maximum search effort for this tree is O(log n).
- When we compare these two samples, we see that the worst search effort was reduced from six to three.
Definition of AVL Tree
AVL tree is a binary search tree that is either empty or that consists of two AVL subtree, TL and TR whose heights differ by no more than one. This height difference is called Balance Factor. Balance factor for any node in AVL tree must be +1, 0, (or)-1.
|HL-HR| < = 1
Where H L and H R are the height of left and right subtree respectively.AVL tree is also called height-balanced binary search tree.
Whenever we insert a node into a tree (or) delete a node from a tree, the resulting tree may be unbalanced. We must rebalance this unbalanced tree. The balancing of AVL tree is done by rotating node to either left or right.
There are two kinds of Rotations:
- Single Rotation
- Double Rotation
All unbalanced AVL trees fall into one of these four cases that are:
- Left of Left
- Right of Right
- Right of Left
- Left of Right
In the first two cases, insertion occur on the "Outside". This is fixed by single rotation. Whereas in 3 & 4 cases, insertion occurs on "Inside". This is fixed by double rotation. Let's discuss them one by one.
Left of Left
If the AVL tree becomes unbalanced because of insertion into the left subtree of left child, then we rotate the out of balance node to the right.
Let's consider an example below:
In the example above, the out of balance condition has been created by inserting node 12 on its left child of left. Here we must rebalance the tree by rotating out balance node 20 to the right.
Right of Right
If the AVL tree becomes unbalanced due to the insertion into the right subtree of the right child, then we need to rote the out of balance node to left.
It is opposite to that of Left of Left. Whenever we find the out of balance by inserting node to right, we must rebalance the tree by rotating the out of balance node to left. In our example inserting of node 20 will cause the out balance at node 12, so we need to rotate that node 12 to left in order to bring the tree in balance condition.
Right of Left
Double rotation is similar to single rotation but which involves four subtree instead of three. Here we study two out of balance conditions in which we need to rotate two nodes. Let us discuss right of left case. In right of left, the out of balance caused by inserting into the right subtree of left child. We need to balance the tree by rotating the right subtree to right and root to left.
Let's explain this Right of Left case with given example:
In the example above, the node 18 is inserted on left of right subtree. This will make a node 12 an unbalanced condition. It is necessary to balance it by rotating node 44 to right, making 18 as a right subtree of root node 12. Now The node 12 is still unbalanced, so we need to perform the second rotation. That means, rotate the root node to left and making the node 12 is a left subtree of node 18.
Left of Right
It is opposite to that of Right of Left case. To balance the tree, we first rotate the left subtree to left, then we rotate the root to the right and making the left node as the new root.
Let's explain this Left of Right case with given example:
In the example above, the node 8 is inserted on right of left subtree. So the node 12 is an unbalanced. To balance it by rotating node 4 to left and making node 8 is the left subtree of root node. Now we again check the balance condition, still root node is an unbalaced. so we shall do the second rotation is that rotate the root node to right. Finally we will get the balanced tree.