Java Data structure Question 2 Consider the following procedure input A list of integers a of size

Java Data structure

Transcribed Image Text:

Question 2 Consider the following procedure input A list of integers a of size n local A binary search tree t output: A list t+D; foreach x a do end tinsert (t, x); return visit(t); // Iterate over all elements of a and assume that function visit is defined as follows visit() = [] visit (Fork(x, I. r)) = visit(r) + [x] + visit(/) where [...] denotes a list of elements (in particular. [] denotes the empty list) and + denotes list concatenation. For example, [3,4, 1] + [2, 3, 5] results in [3, 4, 1, 2, 3, 5]. (a) Briefly describe the task this algorithm performs. In particular, be precise about the relation between the elements in the input list and the output list. [4 marks] (b) Give the worst case time complexity of this algorithm in terms of n using big-Oh notation. Explain your answer and, in particular, be precise about the kind of binary search tree you refer to and about the complexity of insert and visit. [3 marks] (c) Give the best case time complexity of this algorithm in terms of n. As above, explain [3 marks] your answer. Question 2 Consider the following procedure input A list of integers a of size n local A binary search tree t output: A list t+D; foreach x a do end tinsert (t, x); return visit(t); // Iterate over all elements of a and assume that function visit is defined as follows visit() = [] visit (Fork(x, I. r)) = visit(r) + [x] + visit(/) where [...] denotes a list of elements (in particular. [] denotes the empty list) and + denotes list concatenation. For example, [3,4, 1] + [2, 3, 5] results in [3, 4, 1, 2, 3, 5]. (a) Briefly describe the task this algorithm performs. In particular, be precise about the relation between the elements in the input list and the output list. [4 marks] (b) Give the worst case time complexity of this algorithm in terms of n using big-Oh notation. Explain your answer and, in particular, be precise about the kind of binary search tree you refer to and about the complexity of insert and visit. [3 marks] (c) Give the best case time complexity of this algorithm in terms of n. As above, explain [3 marks] your answer.

Answer rating: 100% (QA)

The image presents a question which asks about the details of a given algorithm that performs a task using binary search trees and lists in Java Heres ... View the full answer