Question

a) The keys 20, 15, 25, 12 and 18 are inserted (totally 5 keys, in that order) into an initially empty AVL tree. Show the final AVL tree (just 1 tree) after all the insertions. b) Delete the root node from the final tree in a). Take the root’s successor (we used predecessor in project 2) as the replacement. Show the AVL tree after the deletion. c) Delete the key 12 from the resulted tree in b). Show the AVL tree after the deletion.

Answer 1

AVL Tree are basically Binary Search Tree with special quality of self-balancing such that difference between heights of left and right subtrees cannot be more than one for each and every node.

Insertion in the AVL tree is normally performed as BST insertion but along with that we also need to ensure that the difference between hight of left and right subtree should be not be more than one and we can do that by performing left and right rotation.

AVL tree helps to achieve time complexity of O(logn) for every operation (search, insert,delete), whether BST will take O(h) time and in case of skewed binary search tree it will take O(n) time.

a) Look at the insertion process node by node and after every insertion the tree will be height balanced.

Insert 20...

Insert 15...

Insert 25...

Insert 12...

Insert 18 and the final tree will look like this...

b) Delete root node from final tree i.e 20.

c) Delete key 12...

Happy Learning!