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

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 .

Quindi l'albero finale sarebbe il seguente?

Schermata 2015-01-25 alle 15.08.57.png

(17.24 KiB) Mai scaricato

Grazie

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.

Ti ringrazio