2° Appello - 08/02/2019 - Domanda 3

2° Appello – 08/02/2019 – Domanda 3

  • (probabilmente ho fatto qualche errore, ditemi se anche a voi risultano questi numeri)
  • la funzione che ho scritto forse non è efficiente, ma a me pare vada bene
  • Non saprei come rispondere alla domanda "qual è la complessità di un algoritmo della funzione così realizzata :slight_smile:)

Mi sembra corretto, solamente la visita in-ordine a me è venuta: 1,1,2,3,4,5,5,7,8.
Per il resto anche a me è risultato uguale, la complessità credo sia O(n), essendo che deve passare tutti i nodi almeno una volta, ma non ne son sicuro…

1 Mi Piace

Ciao, non sono sicuro che sia corretto ma risponderei cosi. Visto che la complessità di una algoritmo di sort in un bst è o(n) e il confronto if di costo o(1) per ogni nodo, la complessità resta asintotica a o(n). Quindi io direi che va asintoticamente come o(n). Non so se al professore basti una spiegazione del genere ma non ho altre idee.

1 Mi Piace

solamente la visita in-ordine a me è venuta: 1,1,2,3,4,5,5,7,8.

Hai ragione! Grazie :v:

La funzione proposta non mi sembra corretta. La consegna chiede di contare solo le foglie contenenti un valore pari.

Propongo la mia soluzione

int contaFogliePari(Tree* tree){
    Tree* tmp = tree;
    int tot = 0;
    tot = contaFoglieRic(tmp);
    return tot;
}

int contaFoglieRic(Tree* tree){
    if(tree->left==NULL && tree->right==NULL){
        if(tree->value%2==0)
            return 1;
        else
            return 0;
    }
    return contaFoglieRic(tree->left) + contaFoglieRic(tree->right);
}

Per quanto riguarda la complessità. L’algoritmo visita tutti i nodi dell’albero durante l’esecuzione. Per ogni nodo interno viene fatto un confronto mentre per ogni nodo foglia ne vengono fatti due. In definitiva penso quindi che la complessità sia un O(n), con n numero di nodi dell’albero.

1 Mi Piace

Io non ho capito nella domanda 3 [A] cosa vuol dire “mettendo i valori uguali nel sottoramo di DX”… uguali tra di loro? uguali a cosa? Pensavo di aver capito poi ho visto due volte il valore “1” a sinistra

Spiego brevemente in modo informale.
Quando viene inserito per la seconda volta il valore 1 si deve proseguire nel sotto albero destro di 1 (quello già presente) (i due valori infatti sono uguali) contenente valore 2 che è maggiore di uno. Di conseguenza, a questo punto, si inserisce nel sotto albero sinistro di 2 il valore.
Se non fosse stato inserito il 2 precedentemente, l’1 sarebbe stato figlio destro di 1.

Consiglio di ragionare ricorsivamente nell’inserimento dei valori dell’albero “visitando nodo per nodo” chiedendosi:

  • Quello che devo inserire è maggiore (o UGUALE in questo caso) del nodo che sto guardando? Allore vado a destra.
  • Quello che devo inserire è minore del nodo che sto guardando? Allora vado a sinistra.
    Si procede in questo modo fino a che si trova “uno spazio libero”.

A me sembrano entrambe corrette. L’unica pecca del tuo algoritmo è che non gestisce il caso in cui il puntatore passato contiene un valore nullo.