Question

1. Starting with an empty tree, show each step in the construction of an AVL tree using the following input in the order given. For full credit, you must show the tree after each new input is added. 16, 7, 14, 18, 6, 17, 2, 5, 13, 22, 4 (6 pts.)

2. Show how the AVL tree in previous changes with the following operations. For full credit, you must show the tree after each iteration.

Remove: 17

Remove: 18

Remove: 22

Answer 1

Hello,

I am glad to help you with this question.

An avl tree is a self balancing tree in which the difference of height can be -1,0,1.

1)

the first part needs the insertion of each node in the avl tree.

we need to keep in mind that an avl tree is also a bst (binary search tree).

Now ,

for insertion if there are 2 nodes with non permitted balance factor(i.e height difference of left sub tree and right sub tree) then firstly we start with deepest node.

-ve balance factor needs left rotation .

+ve balance factor needs right rotation .

i have attached the photos at each insertion .

The balancing factor is written at each node.

2) Now for the deletion of 17 .

Now to delete 22 , we simply delete it as it is a leaf node and then fiorm the balanced avl tree .

final tree is as follows :

Thank you .

I hope i was able to solve you problem .

If you have any queries please be comfortable to ask in the comments i will be glad to help you.

:).