Insertion in AVL Tree In C++
Insertion In AVL Tree
AVL tree is self balancing tree in which for all nodes, the difference of height between the left subtree and the right subtree is less than or equal to 1. In this article, an avl tree is created and the difference of height is printed for each node.
Insertion and Creation of an AVL Tree
- A new node can be inserted in an AVL tree by determining the correct position of the node. But insertion of a new node into the tree may affect the height of the tree and the tree might become unbalanced.
- If the new nodes are inserted as child nodes on a non- leaf node there will be no alteration since there will be no effect on the balancing as there is no increase in the height of the tree.
- If the new nodes are inserted as child nodes on a leaf node, the balancing of the tree might get distorted. This depends on whether the node is added to the left subtree or the right subtree.
- Thus to re-balance the tree in order to conserve it’s characteristics we use Rotation Mechanism. There are four types of rotations which help maintain the balancing of the tree as specified above.
- If, due to insertion,the b_fact of multiple nodes is disturbed, balancing occurs on the first ancestor of the node that has been inserted.
Note: During the process of insertion it is important to check the balancing factor of each node at each step, until the process end.
Let us understand with the help of an example. Consider we have following elements given to us: [ 15 , 18 , 12 , 8 , 54 , 5 , 14 , 13 , 9 , 60].
- Insert the first element 15.
- Check for the b_fact of the node.
- b_fact= 0
- Insert the next element 18.
- Check the b_fact each node.
- Insert the next element .
- Check for the b_fact each node.
- The b_fact of each node in this case is 0.
- Insert the next element 8.
- Check for the b_fact of each node.
- Insert the next element 54.
- Check if the b_fact is anything other than -1 , 0 , 1.
- Insert the next element 5.
- Check the b_fact of each node.
- We can see the b_fact of the node 12 is 2. The tree becomes unbalanced.
- We have to balance the tree by identifying the rotation mechanism to be applied.
- We observe the element is inserted to the ,left of the left subtree.
- Thus we have to apply LL Rotation.
- The nodes involved in the rotation are shown in red.
- In order to balance the tree, the tree is rotated towards the right.
- In this case the new parent is 8 and the nodes 5 and 12 becomes the child nodes.
- The next element inserted in the tree is 14.
- Again check the b_fact of each node of the tree.
- The next element to be inserted in the tree is 13.
- After the insertion of the new node, we check for the b_fact of each node.
- Now due to the latest insertion to the tree we can see that the balancing factor of multiple nodes is distorted
- We look for the first ancestor on which the balance factor is disturbed.
- We identify the rotation mechanism to be used.
- To balance the tree we use the RL Rotation Mechanism.
- We identify the nodes that are involved in thre rotation mechanism which are shown in red.
- In this scenario, first a right rotation is applied.
- The tree after right rotation is shown as follows.
- Now to balance the tree, we apply a left rotation.
- After the rotation, the node 13 becomes the new parent node and the nodes 12 and 14 become the new child nodes.
- If we check the balance factor for each node, the balance factor is eithe 0 , 1 or -1.
- The next element to be inserted is 9.
- As the new element is inserted, we observe that the balance factor of the node 8 becomes (-2).
- We can see from the image that for balancing the tree we need to apply RL Rotation.
- Again, first a right rotation is applied and then a left rotation is applied to the tree structure.
- After applying the RL Rotation, the tree structure with the optimal b_fact is shown as follows.
- We can see that the b_fact ranges between 0 , 1 and -1.
- Thus it is an AVL tree.
- The next element to be inserted is 60.
- As 60 is inserted the b_fact of the nodes of right subtree is disturbed.
- Since the disturbance in the balance factor is due to the insertion of an element to the right of the right subtree, we use RR Rotation.
- After applying the RR Rotation the tree so obtained is shown below.
- All the nodes satisfy the condition of an AVL tree.
- The final tree at the end of insertion process with balanced nodes is shown below.
1. Create AVL Tree
2. End Program
Enter your choice 1
Enter no. of elements : 10
Enter element of tree 15
Enter element of tree 18
Enter element of tree 12
Enter element of tree 8
Enter element of tree 54
Enter element of tree 5
Enter element of tree 14
Enter element of tree 13
Enter element of tree 9
Enter element of tree 60
Balance factor 15 1
Balance factor 12 0
Balance factor 8 0
Balance factor 5 0
Balance factor 9 0
Balance factor 13 -1
Balance factor 14 0
Balance factor 54 0
Balance factor 18 0
Balance factor 60 0
Balance Factor 5 0
Balance Factor 8 0
Balance Factor 9 0
Balance Factor 12 0
Balance Factor 13 -1
Balance Factor 14 0
Balance Factor 15 1
Balance Factor 18 0
Balance Factor 54 0
Balance Factor 60 0
1. Create AVL Tree
2. End Program
Enter your choice 2
Time Complexity For Insertion In AVL Tree