[C] alberi binari di ricerca

[Angelmax]

Ciao a tutti, avrei un dubbio sugli alberi binari in C, l'operazione di selezione e l'operazione di ricerca non sono la stessa cosa? non fanno la stessa identica cosa? cioè alla fine io do in input la chiave e la funzione, ad esempio, deve restituirmi la chiave data in input, ma perchè allora per la ricerca mi basta confrontare la chiave e da quello decidere poi dove andare mentre per la selezione devo avere un indice k che mi permette dove andare?

[Luc@s]

Per quanto ricordo, per ricerca tu trovi l'info che ti serve, per selezione tu sai già dove si trova e la porti all'attenzione.

[Angelmax]

Sì infatti, ma non è essenzialmente la stessa cosa? cioè quando devo selezionare un nodo non vado a fare un'operazione di ricerca? Quindi posso usare anche l'algoritmo che uso per la ricerca per la selezione, no?

[Luc@s]

Nope.
In un libro tu cerchi un capitolo (se non sai dov'è) ma ne selezioni la prima pagina sapendo il numero.

[Angelmax]

Non sono molto convinto...non capisco bene il perché non posso usare l'algoritmo di ricerca una volta che io ho trovato la mia chiave ritorno il nodo con la chiave inserita, dall'utente ad esempio, e poi posso usare quel nodo per i più svariati motivi quindi è come se selezionassi quel determinato nodo.

[Luc@s]

Trovi la chiave, selezioni il nodo.
Ecco la differenza.
A me sembra ovvio, ma forse non è così evidente.

[Angelmax]

Ma se trovo la chiave è come se la "selezionassi" se la faccio ritornare, è questo il mio dubbio...

[Luc@s]

Trovare != selezionare

Trovare implica che non sai dov'è quello che cerchi.
Selezionare vuol dire che sai esattamente dov'è quello che cerchi e lo porti all'attenzione.

In un asilo, tu cerchi tuo figlio, ma lo selezioni tra tutti una volta che sai dove si trova.

Non so come spiegarti meglio la differenza.

[Angelmax]

"ma lo selezioni tra tutti una volta che sai dove si trova" esattamente quello che intendo io una volta che so dove si trova il tal elemento (quindi lo cerco) lo seleziono(l'ho trovato e lo restituisco)

[Luc@s]

Per selezionarlo lo devi cercare, a priori non sai dove sia.

[Angelmax]

Sì appunto, volevo quindi sapere se fosse fossibile usare l'algoritmo di ricerca per quello di selezione evitando gli indici che normalmente si usano nella selezione

[vict85]

Sinceramente mi stupisce che sia necessario fare una funzione per la selezione. Ma se è così allora dovrebbe ritornare un puntatore al nodo corrente.

[Angelmax]

Questo è l'algoritmo proposto dai miei professori universitari, i quali hanno fatto due algoritmi diversi uno per la ricerca ed uno per la selezione, per questo mi è venuto il dubbio e penso che il secondo sia superfluo.

[vict85]

Puoi copirare il codice così

[code]codice qui dentro

[/code]


Come è fatto invece la ricerca?

[Angelmax]

Grazie per la dritta, quello per la ricerca invece è così:

link bst_searchNode(link p, Item key)
{
 if ((p == NULL)||(p->item == key)) /*sono arrivato ad una foglia oppure ho trovato l’elemento cercato */ 
return p;
 if(key < p->item) /*visita il sottoalbero sinistro*/ 
return bst_searchNode(p->left, key);
 else /*visita il sottoalbero destro*/
 return bst_searchNode(p->right, key); 
}

[Angelmax]

e sinceramente penso di usare questo algoritmo per la selezione, e non capisco perchè abbiano usato per la selezione degli indici k, eccetera.

[apatriarca]

Che cosa rappresenta la variabile membro N? Rappresenta il numero di nodi del sottoalbero? Altro? Una prima impressione è che la ricerca vada a selezionare il nodo con un determinato valore della chiave, mentre la selezione vada a selezionare il nodo data la sua posizione secondo un qualche ordinamento.

[Angelmax]

nel caso della selezione:
Rappresentazione nodo
–Si aggiunge un campo in cui memorizzo l’informazione relativa al numero totale di nodi appartenenti al suo sottoalbero destro e sinistro (N).

struct bst_node{
 char item;
 int N; 
struct bst_node *left; 
struct bst_node *right; }