Sia dato il seguente algoritmo basato su ABR che, dato un array A, stampa la sequenza ordinata dei suoi valori:

fun treeSort(A, n) {
	T = insert(A[0])

	for i=1..n-1
		T.insert(A[i])

	inorder(T)
}

D1: Dettagliare il corso dell'algoritmo treeSort in funzione di n nel caso migiore e peggiore.
Si diano esempi di input corrispondenti al caso migliore e peggiore per un generico valore n.

D2: Se si utilizzassero alberi AVL al posto di ABR cambierebbe il costo dell'algoritmo? Se si come?

D3: Eseguire treeSort(A) sia con ABR che con AVL sui seguenti input:
A = [50, 25, 75, 12, 60, 80]
A = [10, 20, 30, 40, 50, 60, 70]
A = [70, 60, 50, 40, 30, 20, 10]