Alberi AVL

Programmazione, algoritmica, teoria dell'informazione, ...
Rispondi
Manugal
Messaggi: 6
Iscritto il: 13 mar 2007, 11:09

Alberi AVL

Messaggio da Manugal »

Ciao a tutti!!

Ho un problema con questo esercizio d'esame:

a) In un albero AVL inizialmente vuoto vengono inseriti nell'ordine i valori 1,2,3,...,100. Sia R il numero totale di rotazioni che sono state eseguite durante i 100 inserimenti, dire quale delle seguenti tre disuguaglianze è quella giusta e spiegare perché:

0 <= R <= 52 ; 53 <= R <= 95 ; 96 <= R

b) In un albero AVL inizialmente vuoto si vogliono inserire i valori 1,2,3,...,K. Specificare un ordine di inserimento per i K valori che minimizza il numero totale di rotazioni che vengono eseguite durante tutti gli inserimenti. Quante rotazioni saranno eseguite?


Mi potete dare una mano? Grazie.
gmascellani
Messaggi: 5
Iscritto il: 01 gen 1970, 01:00
Località: Pisa
Contatta:

Re: Alberi AVL

Messaggio da gmascellani »

Manugal ha scritto:b) In un albero AVL inizialmente vuoto si vogliono inserire i valori 1,2,3,...,K. Specificare un ordine di inserimento per i K valori che minimizza il numero totale di rotazioni che vengono eseguite durante tutti gli inserimenti. Quante rotazioni saranno eseguite?
Zero, basta costruirsi un albero bilanciato qualsiasi ed inserire gli elementi visitandolo in ampiezza!
Rispondi