Esercizio
Progettare un algoritmo non ricorsivo che, dato un albero binario di ricercaT contenete entry con chiavi reali distinte, determina la pi`u piccola chiave positiva presente inT, e analizzarne la complessit`a. Se in T non esistono chiavi positive, l’algoritmo deve restituire ’no positive key’.
Esercizio
Analizzare la complessit`a dell’algoritmo sviluppato per l’esercizio del Lucido 57 assumendo che al posto della variabile v.size si abbia a disposizione un metodoT .size(v)che restituisce il numero di entry in Tv, con complessit`a lineare nel valore restituito. (Suggerimento:
esprimere la complessit`a come somma di due termini, uno dei quali `e il costo aggregato di tutte le invocazioni del metodo size.)
Esercizio
Come cambia l’algoritmo sviluppato per l’esercizio del Lucido 57 se non si hanno a disposizione le variabili size?
Esercizio
SiaT un albero binario di ricerca le cui entry rappresentano studenti di un’universit`a. Ogni studente `e associato a una entry(k, x ), dovek `e la matricola, ex indica se lo studente `e straniero (x = 1) o italiano (x = 0). Per ogni nodov ∈ T esiste un interov.numStr che riporta il numero di studenti stranieri inTv (sottoalbero con radicev). Progettare un
algoritmo ricorsivo MinMatStraniero(T , v )che dato un nodov ∈ T restituisce la pi`u piccola matricola di uno studente straniero inTv, e
analizzarne la complessit`a. Se non ci sono studenti stranieri inTv
l’algoritmo restituisce null.
