Vettore e Albero dei confronti per la Ricerca Binaria

Messaggioda sc1512 » 24/01/2015, 17:53

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 :D
sc1512
Starting Member
Starting Member
 
Messaggio: 1 di 10
Iscritto il: 24/01/2015, 17:46

Re: Vettore e Albero dei confronti per la Ricerca Binaria

Messaggioda onlyReferee » 24/01/2015, 19:25

Ciao sc1512 e benvenuto nel forum :!:
Trovi proprio un informatico che ti risponde (laureando magistrale) :D.
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 :D .
Per aspera sic itur ad astra
onlyReferee
Advanced Member
Advanced Member
 
Messaggio: 625 di 2046
Iscritto il: 20/08/2013, 21:20
Località: Musile di Piave (VE)

Re: Vettore e Albero dei confronti per la Ricerca Binaria

Messaggioda sc1512 » 25/01/2015, 15:06

Quindi l'albero finale sarebbe il seguente?

Schermata 2015-01-25 alle 15.08.57.png
(17.24 KiB) Mai scaricato


Grazie :D
sc1512
Starting Member
Starting Member
 
Messaggio: 2 di 10
Iscritto il: 24/01/2015, 17:46

Re: Vettore e Albero dei confronti per la Ricerca Binaria

Messaggioda onlyReferee » 25/01/2015, 22:12

Sì, uniche note (dove $A$ indica il nostro array):
  • In realtà nei nodi vanno messi i confronti veri e propri più che soltanto le posizioni (ad esempio la radice diventa $x = A[7]$);
  • 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]$;
  • 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.
Per aspera sic itur ad astra
onlyReferee
Advanced Member
Advanced Member
 
Messaggio: 626 di 2046
Iscritto il: 20/08/2013, 21:20
Località: Musile di Piave (VE)

Re: Vettore e Albero dei confronti per la Ricerca Binaria

Messaggioda sc1512 » 26/01/2015, 11:34

Ti ringrazio :D
sc1512
Starting Member
Starting Member
 
Messaggio: 3 di 10
Iscritto il: 24/01/2015, 17:46


Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite