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.
Alberi AVL
-
- Messaggi: 5
- Iscritto il: 01 gen 1970, 01:00
- Località: Pisa
- Contatta:
Re: Alberi AVL
Zero, basta costruirsi un albero bilanciato qualsiasi ed inserire gli elementi visitandolo in ampiezza!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?