[Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda Fra27 » 14/06/2017, 10:35

Salve a tutti, ho bisogno di un aiuto nella risoluzione di questo esercizio sugli alberi binari.
La traccia è la seguente:
Dato un albero T i cui nodi sono etichettati con uno dei due possibili colori verde e giallo, progettare un algoritmo che stabilisca se esiste un cammino monocromatico radice-foglia. Scrivi uno pseudo codice ed analizza la sua complessità.


Allora io ovviamente ho utilizzato la tecnica del Divide et impera però ho qualche dubbio sull'ultima restituzione. Il mio pseudo codice è il seguente:

Sia n la radice dell'albero:

Codice:
Alg(n)
If(n==NULL)
 Return true;

Else {
           If(n.dato.ch!=n.sx.dato.ch)
            { if(n.dato.ch!=n!dx.dato.ch)
               Return false;
               Else Return Alg(n.dx);
              }
            Else {
              If(n.dato.ch!=n.dx.dato.ch)
               Return Alg(n.sx);
     
               Else return Alg(n.sx) && Alg(n.dx);      (?????)
                }
           }


Mi rendo conto che la penultima riga di comando è scritta male ma non saprei come altro risolvere il problema.
Quando entrambi i figli hanno lo stesso colore cosa dovrebbe restituire il codice?
Grazie a chi risponderà!!
Fra27
Junior Member
Junior Member
 
Messaggio: 56 di 172
Iscritto il: 08/01/2015, 11:50

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda apatriarca » 14/06/2017, 10:56

L'ultima condizione dovrebbe essere un OR, non un AND. Hai infatti che la condizione è verificata se lo è in almeno uno dei due sottoalberi.

EDIT: Rimosso codice in quanto errato.
apatriarca
Moderatore
Moderatore
 
Messaggio: 4666 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda Fra27 » 14/06/2017, 11:09

apatriarca ha scritto:L'ultima condizione dovrebbe essere un OR, non un AND.



Ma se ad esempio restituisse il sottoalbero "sbagliato"? Faccio un esempio: restituisce alg(n.dx) che avrà un nodo di colore diverso dagli altri, quindi result= false; mentre se avesse restituito alg(n.sx), che presenta un cammino monocromatico radice-foglia, il risultato finale sarebbe stato true. (Scusa per la pessima spiegazione ma non saprei in quale altro modo scriverlo).


Edit: Ho riguardato il significato degli operatori booleani ed ora mi è tutto chiaro! Quindi nel caso in cui uno dei due fosse true allora l'algoritmo restituirà true altrimenti il risultato sarà false.
Fra27
Junior Member
Junior Member
 
Messaggio: 57 di 172
Iscritto il: 08/01/2015, 11:50

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda apatriarca » 14/06/2017, 11:30

Mi sono reso conto che ci sono molti casi che non sono stati considerati. Per prima cosa un figlio può essere NULL. Per comodità definisco quindi una funzione di supporto (uso python):
Codice:
def alg(node):
    return (not node) or alg_c(node.colour, node.left) or alg_c(node.colour, node.right)

def alg_c(colour, child):
    return (not child) or (child and child.colour == colour and alg(child))

In altre parole. Un figlio è parte di un percorso monocromatico se è una foglia (NULL) oppure se ha lo stesso colore del padre ed esiste un percorso monocromatico da esso. Percorso monocromatico il cui colore sarà necessariamente quello del padre. Esiste un percorso monocromatico se un nodo è una foglia o se almeno uno dei suoi due figli è parte di un percorso monocromatico come definito in precedenza.Ovviamente si poteva anche scrivere tutto come una singola espressione (o attraverso if annidati o meno).
apatriarca
Moderatore
Moderatore
 
Messaggio: 4667 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda Fra27 » 14/06/2017, 11:40

apatriarca ha scritto:Mi sono reso conto che ci sono molti casi che non sono stati considerati. Per prima cosa un figlio può essere NULL. Per comodità definisco quindi una funzione di supporto (uso python)


Phyton non lo ricordo molto bene purtroppo..

Do uno sguardo al linguaggio e poi mi rileggo il tuo codice.


Ma quello che ho proposto io inizialmente ,anche se contorto (e cambiando quell'and con l'or), è corretto?
Fra27
Junior Member
Junior Member
 
Messaggio: 58 di 172
Iscritto il: 08/01/2015, 11:50

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda apatriarca » 14/06/2017, 11:42

Manca il test per verificare se il nodo ha effettivamente dei figli destro o sinistro, ma per il resto l'idea è corretta.
apatriarca
Moderatore
Moderatore
 
Messaggio: 4668 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda Fra27 » 14/06/2017, 12:00

apatriarca ha scritto:Manca il test per verificare se il nodo ha effettivamente dei figli destro o sinistro, ma per il resto l'idea è corretta.


Quindi al primo rigo potrei scrivere:

Codice:
If (n==NULL) || (n.sx==NULL && n.dx==NULL)
Return true;


Così è completo?
Fra27
Junior Member
Junior Member
 
Messaggio: 59 di 172
Iscritto il: 08/01/2015, 11:50

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda apatriarca » 14/06/2017, 12:19

No, devi testare ogni ramo separatamente prima di cercare di accedere al suo colore. Un ramo può infatti avere anche solo uno dei due figli uguale a NULL..
apatriarca
Moderatore
Moderatore
 
Messaggio: 4669 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda Fra27 » 14/06/2017, 16:15

apatriarca ha scritto:No, devi testare ogni ramo separatamente prima di cercare di accedere al suo colore. Un ramo può infatti avere anche solo uno dei due figli uguale a NULL..


Quindi dovrei aggiungere parecchi if.. Mmmmm :roll:

E per quanto riguarda la complessità? Oltre a dire che è lineare potrei aggiungere qualcosa?
Fra27
Junior Member
Junior Member
 
Messaggio: 60 di 172
Iscritto il: 08/01/2015, 11:50

Re: [Algoritmi] Dubbi su algoritmi di alberi binari

Messaggioda apatriarca » 14/06/2017, 16:22

Non c'è nulla da aggiungere, a meno che non voglia anche la complessità della memoria utilizzata.
apatriarca
Moderatore
Moderatore
 
Messaggio: 4670 di 10435
Iscritto il: 08/12/2008, 20:37
Località: Madrid

Prossimo

Torna a Informatica

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite