(a) Given the following AVL tree 7: 24 (i) (ii) (iii) 30 37 38 42 48...

 

Transcribed Image Text:

(a) Given the following AVL tree 7: 24 (i) (ii) (iii) 30 37 38 42 48 60 89 We will insert several keys into T. For each part of this question, show ALL steps for each insertion, including the trees after each appropriate rotation and the resulting trees after each insertion. Based on the given AVL tree, insert 40 into the AVL tree. Based on the AVL tree in (i), insert 99 into the AVL tree. Based on the AVL tree in (ii), insert 45 into the AVL tree. (4 marks) (3 marks) (4 marks) (b) Is the array with values [1,3,7,9,10,21,13,44,99,10,10,20] a min-heap? If yes, explain why. If no, state clearly ALL the index(s) of the array element(s) that make(s) the array not a min-heap. (4 marks) (c) Draw the resulting tree and array after calling max_heapify (input-a, index=0) on the array a [1,12,11,5,6,9,8,4,3,2,0] where the function would heapify the input array from the index. Note that the function max_heapify assumes the index of the first element is 0. (5 marks) (a) Given the following AVL tree 7: 24 (i) (ii) (iii) 30 37 38 42 48 60 89 We will insert several keys into T. For each part of this question, show ALL steps for each insertion, including the trees after each appropriate rotation and the resulting trees after each insertion. Based on the given AVL tree, insert 40 into the AVL tree. Based on the AVL tree in (i), insert 99 into the AVL tree. Based on the AVL tree in (ii), insert 45 into the AVL tree. (4 marks) (3 marks) (4 marks) (b) Is the array with values [1,3,7,9,10,21,13,44,99,10,10,20] a min-heap? If yes, explain why. If no, state clearly ALL the index(s) of the array element(s) that make(s) the array not a min-heap. (4 marks) (c) Draw the resulting tree and array after calling max_heapify (input-a, index=0) on the array a [1,12,11,5,6,9,8,4,3,2,0] where the function would heapify the input array from the index. Note that the function max_heapify assumes the index of the first element is 0. (5 marks)

Answer rating: 100% (QA)

a i Insert 40 into the AVL tree Initial tree 37 24 48 7 30 42 60 ... View the full answer