Please add the nodes given below to construct the AVL tree show all the necessary steps, 20,21,22,17,18,23,27,25,30,33,34

There are four cases and any node insertion will be one of these four cases,

1.         An insertion into left subtree of the left child of a.

2.         An insertion into right subtree of the left child of a.

3.         An insertion into left subtree of the right child of a.

4.         An insertion into right subtree of the right child of a.

Answer:

 

Step 1: Inserting 20

Step 2: Inserting 21

 

Step 3: Inserting 22

Node 20 has balance -2 so this tree is not AVL tree.

Case 4 An insertion into right sub tree of the right child of a.

So applying single left rotation  

Step 4: Inserting 17

Step 5: Inserting 18

Node 20 has become unbalanced

Case 2 An insertion into right sub tree of the left child of a.

An insertion into right sub tree of the left child of a.

So applying two rotations first left rotation and then right rotation.

Step 6: Inserting 23

Step 7: Inserting 27

Case 4 An insertion into right sub tree of the right child of a.

So applying single left rotation,

Step 8: Inserting 25

Still an AVL tree,

Step 9: Inserting 30

Still an AVL tree,

Step 10: Inserting 33

It is Case 4 mean insertion on right side of right node. So applying left rotation on the edge of the node where imbalance occured,

Step 11: Inserting 34

Case 4 insertion in right node of right sub tree, so applying single left rotation,

This is our Final Tree.