Question

Insert the list of elements [11, 14, 16, 4, 7, 2, 23, 28, 19] in this order, into an initially empty AVL tree.     Show the details of the insertion process.       Note:    You must draw a different tree to show the result of each rotation involved. If an insertion requires a double rotation, you must show the result of each rotation separately.

Answer 1

The list of elements is given as [11, 14, 16, 4, 7, 2, 23, 28, 19] .

The balance factor of a node is the difference between the height of its left subtree and the height of its right subtree and in an AVL tree, the balance factor of a node must be either -1, 0 or 1.

The insertion process into an AVL tree takes place as follows :

Step 1 :

The first element to be inserted is 11.

The AVL tree becomes :

Step 2 :

The next element to be inserted is 14. Since 14 is greater than 11, it is placed as the right child of 11.

The AVL tree becomes :

Step 3 :

The next element to be inserted is 16. Since 16 is greater than 14, it is placed as the right child of 16.

The AVL tree becomes :

But here the balance factor of node with key 11 is violated as it is 0 - 2 = -2.

Perform single left rotation with respect to node with key 11.

The AVL tree becomes :

Step 4 :

The next element to be inserted is 4. Since, 4 is less than 11, it is placed as the left child of 11.

The AVL tree becomes :

Step 5 :

The next element to be inserted is 7. Since, 7 is greater than 4 and less than 11, it is added as the right child of 4.

The AVL tree becomes :

But here the balance factor of node with key 11 is violated 2 - 0 = 2.

Perform double right rotation on the nodes with key 4 and key 11.

So, at first, left rotation is performed with respect to node 4.

The AVL tree becomes :

Then, right rotation is performed.

The AVL tree becomes :

Step 6 :

The next element to be inserted is 2. Since, 2 is less than 4, it is added as the left child of 4.

The AVL tree becomes :

But here the balance factor of node with key 14 is violated as 3 - 1 = 2.

Perform single right rotation with respect to node with key 14 that is the root node.

The AVL tree becomes :

Step 7 :

The next element to be inserted is 23. Since, 23 is greater than 16, it is added as the right child of node with key 16.

The AVL tree becomes :

Step 8 :

The next element to be inserted is 28. Since, 28 is greater than 23, it is added as the right child of 23.

The AVL tree becomes :

But here the balance factor of node with key 16 is violated as 0 - 2 = -2.

Perform single left rotation with respect to node with key 16.

The AVL tree becomes :

Step 9 :

The next element to be inserted is 19. Since, 19 is greater than 16 and less than 23, it is added as the right child of 16.

The AVL tree becomes :

But here the balance factor of node with key 14 is violated as 1 - 3 = -2.

Perform double left rotation with respect to node with key 14.

So, at first perform the right rotation in double rotation technique and the AVL tree becomes :

Now perform left rotation with respect to node with key 16.

The AVL tree becomes :

The final AVL tree after the insertion of the given elements is :