Vettore e Albero dei confronti per la Ricerca Binaria
Ciao a tutti,
sono nuovo del forum e attualmente frequento il primo anno di Informatica..
Ho trovato delle difficoltà a capire cosa significhi questa domanda in un esercizio:
"Dato il vettore ordinato |1|2|3|4|5|6|7|8|9|10|11|12| costruire l'albero dei confronti per la ricerca binaria".
Sarò grato a chiunque riesca ad aiutarmi a risolvere questo esercizio
sono nuovo del forum e attualmente frequento il primo anno di Informatica..
Ho trovato delle difficoltà a capire cosa significhi questa domanda in un esercizio:
"Dato il vettore ordinato |1|2|3|4|5|6|7|8|9|10|11|12| costruire l'albero dei confronti per la ricerca binaria".
Sarò grato a chiunque riesca ad aiutarmi a risolvere questo esercizio
Risposte
Ciao sc1512 e benvenuto nel forum 
Trovi proprio un informatico che ti risponde (laureando magistrale).
Venendo al tuo quesito bisogna che scrivi sotto forma di albero binario di ricerca i vari confronti tra gli elementi che avvengono quando si ricerca un determinato elemento $x$ mediante l'algoritmo di ricerca binaria. Sicuramente il primo confronto verrà effettuato con l'elemento mediano del'array e poi di conseguenza tale ricerca verrà ristretta ad una delle due metà dell'array e così via fino a che l'elemento non è stato trovato o non si è terminata la ricerca. Nel caso specifico, ai fini dell'albero che hai da costruire, dobbiamo supporre che l'elemento non venga trovato e pertanto che la ricerca termini perché si è finito di analizzare l'array, altrimenti se ci pensi il nostro albero risulterebbe incompleto .
Trovi proprio un informatico che ti risponde (laureando magistrale)
.Venendo al tuo quesito bisogna che scrivi sotto forma di albero binario di ricerca i vari confronti tra gli elementi che avvengono quando si ricerca un determinato elemento $x$ mediante l'algoritmo di ricerca binaria. Sicuramente il primo confronto verrà effettuato con l'elemento mediano del'array e poi di conseguenza tale ricerca verrà ristretta ad una delle due metà dell'array e così via fino a che l'elemento non è stato trovato o non si è terminata la ricerca. Nel caso specifico, ai fini dell'albero che hai da costruire, dobbiamo supporre che l'elemento non venga trovato e pertanto che la ricerca termini perché si è finito di analizzare l'array, altrimenti se ci pensi il nostro albero risulterebbe incompleto
.
Quindi l'albero finale sarebbe il seguente?
Grazie
Grazie
Sì, uniche note (dove $A$ indica il nostro array):
[*:dpypyara]In realtà nei nodi vanno messi i confronti veri e propri più che soltanto le posizioni (ad esempio la radice diventa $x = A[7]$);[/*:m:dpypyara]
[*:dpypyara]Nelle linee che portano da un nodo all'altro sarebbe meglio mettere anche i confronti di disuguaglianza per far capire meglio il confronto che porta ad un nodo. Ad esempio nel nodo che va da $7$ a $10$ si può mettere $x > A[7]$;[/*:m:dpypyara]
[*:dpypyara]Dai nodi $1, 3, 5, 8$ e $12$ partono due frecce che vanno a finire a NULL poiché teoricamente possono venire fatti due altri confronti a partire dagli stessi.[/*:m:dpypyara][/list:u:dpypyara]
Ti ringrazio
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo