Question

(b) You are given the AVL Tree in the figure below. Assume that the nodes are sorted in alphabetical order. E J B D K A F L H Draw the resulting BST after node E is removed. To construct the new BST replace node E with an appropriate node from the left subtree of E. Do not rebalance the resulting tree. Label each node in the resulting tree with its balance factor. (e) Now rebalance the tree from the previous task. Draw a new tree for each rotation that occurs when rebalancing the tree. You do not need to label the trees with the balance factors. Hint: You may need to perform more than one rotation to rebalance the tree.

Answer 1

SOLUTION:-

SOLUTION-(b):- We have given that : After removing E, the resulting non-balanced tree is given below :- STEPS: (0) E == E, Found node to delete. (ii) Node to delete has 2 children, find largest node in left subtree. (iii) Copy largest value of left subtree into node to delete. (iv) Remove node whose value we copied. 1 L с K

SOLUTION-(C):- Now, we will rebalance the tree from the previous task. First of all, SINGLE ROTATE RIGHT :- G H Then, DOUBLE ROTATE LEFT :- B H H

=====================================================================