Dubbi sul conteggio passi in una funzione ricorsiva

di il
5 risposte

Dubbi sul conteggio passi in una funzione ricorsiva

Salve a tutti,
Sto facendo un progetto per l'università, dove si richiede, tra le altre cose, di creare degli alberi binari di ricerca e calcolare la complessità con uno studio sperimentale.
Ho creato una funzione ricorsiva (funzionante) che cerca i vari nodi e li stampa, il problema è che non sono sicuro che conti correttamente i passi svolti, dato che come risultato mi da un valore che secondo me è troppo basso. Dato che non sono molto familiare con i puntatori, indirizzi ecc... ho paura che in qualche modo, dopo la chiamata ricorsiva, la variabile non si incrementi come dovrebbe.
Di seguito il codice della funzione, grazie in anticipo

void cerca_in_albero_ric(nodo_albero_bin_t *radice, char nome_cpu[7], int *passi)
{

    nodo_albero_bin_t *nodo_p;
        for (nodo_p = radice;
        ((nodo_p != NULL) && strcmp(nodo_p->nome,nome_cpu)!=0);
                nodo_p = strcmp(nome_cpu,nodo_p->nome)<0?
                            nodo_p->sx:
                            nodo_p->dx)
                            (*passi)++;


        if(nodo_p!=NULL)
        {
            stampa_valori(nodo_p);
            (*passi)++;
            cerca_in_albero_ric(nodo_p->dx, nome_cpu, passi);

        }

}

5 Risposte

  • Re: Dubbi sul conteggio passi in una funzione ricorsiva

    Troppo basso in che senso? Che valori hai inserito? Considera che se l'albero è ben bilanciato (cioè non degenera in una lista), il numero di passi è logaritmico in base 2, cioè avrai, nel caso peggiore, una ventina di passi in un albero da un milione di elementi.
  • Re: Dubbi sul conteggio passi in una funzione ricorsiva

    Perché c'è un for e una chiamata ricorsiva dopo? È un errore di trascrizione? O l'uno o l'altro...
  • Re: Dubbi sul conteggio passi in una funzione ricorsiva

    Alexv ha scritto:


    Troppo basso in che senso? Che valori hai inserito? Considera che se l'albero è ben bilanciato (cioè non degenera in una lista), il numero di passi è logaritmico in base 2, cioè avrai, nel caso peggiore, una ventina di passi in un albero da un milione di elementi.
    No infatti a quanto pare è efficiente, sono stato paranoico io
  • Re: Dubbi sul conteggio passi in una funzione ricorsiva

    Alexv ha scritto:


    Perché c'è un for e una chiamata ricorsiva dopo? È un errore di trascrizione? O l'uno o l'altro...
    Allora, il for serve per arrivare al nodo giusto, poi tramite la ricorsione scorro l'albero per ritrovare, di nuovo, il nodo giusto.
    Perché all'interno dell'albero ci sono nodi che hanno la stessa chiave, quindi mi serve farlo più volte.
    Non so se mi sono spiegato ma forse è difficile capire senza la specifica sotto, l'ho postato più che altro per sicurezza, grazie per la risposta
  • Re: Dubbi sul conteggio passi in una funzione ricorsiva

    Zack909 ha scritto:


    Allora, il for serve per arrivare al nodo giusto, poi tramite la ricorsione scorro l'albero per ritrovare, di nuovo, il nodo giusto.
    Perché all'interno dell'albero ci sono nodi che hanno la stessa chiave, quindi mi serve farlo più volte.
    Non so se mi sono spiegato ma forse è difficile capire senza la specifica sotto, l'ho postato più che altro per sicurezza, grazie per la risposta
    Ah avevo in mente l'albero con valori univoci. Allora ha senso se per costruzione il nodo uguale al nodo padre si trova a destra.
Devi accedere o registrarti per scrivere nel forum
5 risposte