> Construct an AVL tree by inserting the input array {13, 25, 58, 80, 15, 82,...

Transcribed Image Text:

> Construct an AVL tree by inserting the input array {13, 25, 58, 80, 15, 82, 6, 65, 29, 70, 68). Draw the tree after inserting all the nodes and the trees after deleting each of the two elements: 13 and 58, respectively. (You need to draw three trees in total) 2.2. (25') Given an array A of distinct integers, make use of the AVL tree to sort A in ascending order. (20) Write the C code for your algorithm. Note that : a) • you may use the Node struct and the functions insertNode(), destroy Tree() defined in the lecture notes without implementation; you may define auxiliary functions; and you do not have to write any include preprocessor. void AVLSort(int *A, int n){ // input: A // an array containing distinct integers n- the size of A - // output: when AVLSort() completes, A is sorted. // Your code here } b) (5') Prove that the time complexity of your algorithm is O(nlogn). Note: you do not have to prove the complexity of insertNode() and destroy Tree(). > Construct an AVL tree by inserting the input array {13, 25, 58, 80, 15, 82, 6, 65, 29, 70, 68). Draw the tree after inserting all the nodes and the trees after deleting each of the two elements: 13 and 58, respectively. (You need to draw three trees in total) 2.2. (25') Given an array A of distinct integers, make use of the AVL tree to sort A in ascending order. (20) Write the C code for your algorithm. Note that : a) • you may use the Node struct and the functions insertNode(), destroy Tree() defined in the lecture notes without implementation; you may define auxiliary functions; and you do not have to write any include preprocessor. void AVLSort(int *A, int n){ // input: A // an array containing distinct integers n- the size of A - // output: when AVLSort() completes, A is sorted. // Your code here } b) (5') Prove that the time complexity of your algorithm is O(nlogn). Note: you do not have to prove the complexity of insertNode() and destroy Tree().