[C++] BST - FOGLIE SULLO STESSO LIVELLO

[Doraemond]

devo creare un algoritmo che dato un albero binario bst mi controlli tramite una funzione booleana se l'albero ha tutte le foglie sullo stesso livello,ho buttato giu un pezzo di codice ma nn mi si impalla xkè probabilmente quando vado a conftollare se il nodo è una foglia o meno nel caso in cui il nodo è nullo vado a deferenziare una zona di memoria non allocata,almeno credo.
posto il codice che ho iniziato a scrivere:

bool stesso_lev(Pnodo L){
    if(L==NULL)
        return true;
    else
        return confronta(L->sx,L->dx);
}

bool confronta(Pnodo x,Pnodo y){
        if(x->sx==NULL && x->dx==NULL && y->sx==NULL && y->dx==NULL) 
            return true;
        else if(x->sx==NULL && x->dx==NULL)
            return false;
        else if(y->sx==NULL && y->dx==NULL)
            return false;
        else
            return (confronta(x->sx,x->dx) && confronta(y->sx,x->dx));
}

dove e molto probabilmento ho sbagliato??

[fero86]

ho capito bene?

[...] edit - vedi post #4

[DanieleC88]

Il tuo errore è di cercare di leggere subito i vari x->sx o x->dx senza controllare che il nodo x stesso in questione sia valido o meno.

Secondo me puoi fare anche un'altra cosa figa.
Puoi fare una visita per livelli, e per ogni livello controllare che siano tutte foglie o tutte non foglie. In altre parole, partendo dal primo nodo di ogni livello, se quel nodo non è una foglia, tutti gli altri nodi del livello non devono essere foglia, e simmetricamente se quel nodo è una foglia, tutti gli altri nodi del livello devono essere foglie.

ciao

[fero86]

pardon, posto una versione un po' migliore
avevo scritto un metodo "Greatest" inutile, c'é giá std::max.

#include <iostream>
#include <algorithm>
using namespace std;


class CNode {
public:
	virtual unsigned int Height() const = 0;
	virtual bool Complete() const = 0;
};

class CLeaf :
	public CNode {
public:
	virtual unsigned int Height() const {
		return 0;
	}

	virtual bool Complete() const {
		return true;
	}
};

class CTree :
	public CNode {
private:
	const CNode &m_rLeft;
	const CNode &m_rRight;

public:
	CTree(const CNode &a_rLeft, const CNode &a_rRight)
		:
	m_rLeft(a_rLeft),
		m_rRight(a_rRight) {
	}

	virtual unsigned int Height() const {
		return 1 + max(m_rLeft.Height(), m_rRight.Height());
	}

	virtual bool Complete() const {
		return m_rLeft.Complete() && m_rRight.Complete() && (m_rLeft.Height() == m_rRight.Height());
	}
};


int main() {
	cout << CTree(CLeaf(), CLeaf()).Complete() << endl;
	cout << CTree(CTree(CLeaf(), CLeaf()), CLeaf()).Complete() << endl;
	return 0;
}

[marco.r]

Originariamente inviato da Doraemond

bool stesso_lev(Pnodo L){
    if(L==NULL)
        return true;
    else
        return confronta(L->sx,L->dx);
}

bool confronta(Pnodo x,Pnodo y){
        if(x->sx==NULL && x->dx==NULL && y->sx==NULL && y->dx==NULL) 
            return true;
        else if(x->sx==NULL && x->dx==NULL)
            return false;
        else if(y->sx==NULL && y->dx==NULL)
            return false;
        else
            return (confronta(x->sx,x->dx) && confronta(y->sx,x->dx));
}

dove e molto probabilmento ho sbagliato??

Chiami confronta senza verificare se sono puntatori nulli o meno.
In ogni caso l'algoritmo che proponi lo vedo sbagliato (funziona se un nodo ha solo una foglia, ma non se due interi sottorami hanno altezze diverse).
Vedo due alternative (relativamente simili).
La prima e' di verificare che ogni nodo dell'albero ha i due sottorami sinistro e destro di uguale altezza. L'altra e' quella di percorrere l'albero e controllare l'altezza di ogni foglia, controllandola con quella precedentemente trovata tramite una variabile condivisa.

[Doraemond]

hai usato le classi nel tuo codice ma purtroppo le classi nn le ho ancora studiate qnd nn c capisco nnt del tuo codice!!

[Doraemond]

daniele esiste un metodo per scorrere l'albero per livelli??

[DanieleC88]

Certo che esiste.
Crei una coda vuota, e le aggiungi la radice dell'albero.
Poi in un ciclo while (che si fermerà solo quando la coda è vuota) prendi un nodo alla volta dalla coda e lo "visiti". Poi aggiungi alla coda i suoi figli (se esistono) e ripeti il ciclo.
In questo modo avrai una visita per livelli.

Il problema è che in questo modo ti trovi a prendere un nodo alla volta e non sai a quale livello apparteneva. Direi che ti basterà aggiungere un'informazione "livello" ai nodi che inserirai nella coda, in modo da poter poi inserire i figli del nodo estratto nella coda con un valore del livello incrementato di 1. (Ok?)

A quel punto diventa una fesseria.

[marco.r]

Originariamente inviato da DanieleC88

Certo che esiste.
Crei una coda vuota, e le aggiungi la radice dell'albero.
Poi in un ciclo while (che si fermerà solo quando la coda è vuota) prendi un nodo alla volta dalla coda e lo "visiti". Poi aggiungi alla coda i suoi figli (se esistono) e ripeti il ciclo.
In questo modo avrai una visita per livelli.

Il problema è che in questo modo ti trovi a prendere un nodo alla volta e non sai a quale livello apparteneva. Direi che ti basterà aggiungere un'informazione "livello" ai nodi che inserirai nella coda, in modo da poter poi inserire i figli del nodo estratto nella coda con un valore del livello incrementato di 1. (Ok?)

A quel punto diventa una fesseria.

Direi che una cosa in questo caso e' un tantino overkill. Molto piu' semplice:

istanzi una variabile intera "altezzaFoglie" a -1
chiami ricorsivamente una funzione sulla radice alla quale passi
- altezza corrente dell'albero (all'inizio ovviamente 0)
- puntatore ad "altezzaFoglie"
il valore di ritorno sara true se il (sotto)albero e' bilanciato, false altrimenti

quando trovi una foglia verifichi il valore di "altezzaFoglie". Se e' -1 hai trovato la prima foglia e quindi imposti il valore all'altezza corrente e ritorni true. Se e' >= 0 confronti i due valori e ritorni true solo se sono uguali.

quando hai un nodo interno non fai che chiamare ricorsivamente la funzione sui due figli aumentando di uno l'altezza e ritornando l'OR tra i due risultati.

e' piu' corto da scrivere che da spiegare

[DanieleC88]

Sicuramente ci sono modi migliori di farlo (basta una funzione ricorsiva che controlli se l'albero è completo, come ha fatto fero86), però è una soluzione simpatica.
Perché non fargli sperimentare più di una strada?

[fero86]

Originariamente inviato da Doraemond

hai usato le classi nel tuo codice ma purtroppo le classi nn le ho ancora studiate qnd nn c capisco nnt del tuo codice!!

sono indubbiamente il modo migliore per risolvere l'esercizio, infatti quelle assieme all'uso dei reference ti risparmiano da qualunque controllo di puntatori nulli, che sono la fonte dei tuoi problemi; se ci fai caso il mio codice non contiene manco un if.

studialo tutto il C++, é molto potente e ti permette di essere molto piu produttivo del C

[Doraemond]

uff...mi sto esaurendo io e quest'esercizio,qualcuno potrebbe postarmi un po di pseudocodice??

P.s.
anke io volevo farlo con la variabile che mi segnava il livello del nodo foglia ma il prof mi disse che dovevo afrlas senza ausilio di variabili,così mi scocciai e abbandonai l'esercizio,ma ora volendo imparare bene a programmare voglio risolvere anke questo problema,mi ricordo cmq che il prof mi disse che dovevo prima controllare se l'albero era bilanciato,e nel caso in cui fosse bilanciato effettuare i controlli sulle foglie...

[DanieleC88]

Be', perché lo pseudocodice? fero86 ti ha dato un codice completo e funzionante. L'idea è quella che ha utilizzato lui, ed è banalissima. Se tutte le foglie si trovano sullo stesso livello, allora quello deve necessariamente essere l'ultimo livello preso per intero. E ciò accade in un albero binario (di ricerca o no, non ha importanza) quando quest'ultimo è completo. (E quando è completo, tutti i suoi nodi hanno un coefficiente di bilanciamento pari a 0, per cui non capisco del tutto il suggerimento del tuo professore.)

Quindi, ti basta controllare che, per ogni nodo, il sottoalbero radicato nel figlio sinistro ed il sottoalbero radicato nel figlio destro abbiano la stessa identica altezza.

[Doraemond]

ho visto ke mi ha dato il codice ma nn ci capisco nulla,siccome fatto cn le classi,quindi nn saprei come adattarlo al mio codice !!
in pseudocisice sarebbe + facile x me capirlo!!

[DanieleC88]

Lo pseudocodice viene quasi identico al codice di fero86 per quel che riguarda le parti "interessanti".

Sarebbe una cosa del tipo:

algoritmo Albero-Altezza(albero T) → intero {
    se (T è vuoto) {
        restituisci 0;
    }
    altrimenti {
        restituisci 1 + max{ Albero-Altezza(T->sinistro), Albero-Altezza(T->destro) };
    }
}

algoritmo Albero-Completo(albero T) → booleano {
    se (T è vuoto) {
        restituisci vero;
    }
    altrimenti {
        se (Albero-Completo(T->sinistro) AND Albero-Completo(T->destro)) {
            restituisci (Albero-Altezza(T->sinistro) == Albero->Altezza(T->destro));
        }
        altrimenti {
            restituisci falso;
        }
    }
}

[marco.r]

Originariamente inviato da DanieleC88

Lo pseudocodice viene quasi identico al codice di fero86 per quel che riguarda le parti "interessanti".

Sarebbe una cosa del tipo:

algoritmo Albero-Altezza(albero T) → intero {
    se (T è vuoto) {
        restituisci 0;
    }
    altrimenti {
        restituisci 1 + max{ Albero-Altezza(T->sinistro), Albero-Altezza(T->destro) };
    }
}

algoritmo Albero-Completo(albero T) → booleano {
    se (T è vuoto) {
        restituisci vero;
    }
    altrimenti {
        se (Albero-Completo(T->sinistro) AND Albero-Completo(T->destro)) {
            restituisci (Albero-Altezza(T->sinistro) == Albero->Altezza(T->destro));
        }
        altrimenti {
            restituisci falso;
        }
    }
}

Resto dell'idea che una singola funzione che fa tutto il lavoro sia una soluzione piu' adatta, non fosse altro perche' puoi evitare di visitare tutto l'albero qualora non sia necessario.

algoritmo alberoCompleto(albero T,int altezzaFoglie,altezzaCorrente) → booleano

    se t vuoto
        se altezzaFoglie==-1
            altezzaFoglie = altezzaCorrente
            restituisci vero
        altrimenti
            restituisci altezzaCorrente == altezzaFoglie
    altrimenti
        restituisci alberoCompleto( t->sinistro, altezzaFoglie, altezzaCorrente+1 ) e
                       alberoCompleto( t->destro, altezzaFoglie, altezzaCorrente+1 )

Da usare con chiamata iniziale

altezzaFoglie = -1
alberoCompleto( radice, altezzaFoglie, 0 )

[DanieleC88]

Non è che cambi molto, la complessità asintotica è la stessa per il caso peggiore (cioè quello in cui effettivamente l'albero è completo, in cui è richiesto comunque un attraversamento di ogni nodo, rendendo la complessità Θ(n), con n numero di nodi nell'albero).
In questo modo riusciresti tutt'al più a minimizzare il costo nel caso migliore, che è quello in cui l'albero è evidentemente non completo.

ciao

[marco.r]

Originariamente inviato da DanieleC88

Non è che cambi molto, la complessità asintotica è la stessa per il caso peggiore (cioè quello in cui effettivamente l'albero è completo, in cui è richiesto comunque un attraversamento di ogni nodo, rendendo la complessità Θ(n), con n numero di nodi nell'albero).
In questo modo riusciresti tutt'al più a minimizzare il costo nel caso migliore, che è quello in cui l'albero è evidentemente non completo.

ciao

Non hai fatto i conti con il caso medio .
Con la mia soluzione, il costo C per l'algoritmo e' il seguente:

C(t) = C(t->left) + 1 se t->left non e' bilanciato
= C(t->left) + 1 + C(t->right) altrimenti

Visto che nulla e' stato detto a riguardo, immagino che la distribuzione degli alberi sia uniforme. Ora, gli alberi completi sono solo una minima parte dei possibili ( O(log(n)) contro O(n) sul numero di nodi)
Nel primo caso il costo e' O(n), nel secondo O(log(n)). Il costo dell'algoritmo per tutti gli alberi e' quindi O(n)log(n) e quindi log(n) nel caso medio (invece che O(n)).

La dimostrazione non e' proprio formale, ma spero renda l'idea.

[DanieleC88]

Ma infatti io stavo parlando del caso peggiore.

[Doraemond]

marco.r ma net tuo pseudocodice

algoritmo alberoCompleto(albero T,int altezzaFoglie,altezzaCorrente) → booleano

se t vuoto
se altezzaFoglie==-1
altezzaFoglie = altezzaCorrente
restituisci vero
altrimenti
restituisci altezzaCorrente == altezzaFoglie
altrimenti
restituisci alberoCompleto( t->sinistro ) e alberoCompleto( t->destro )

dove ho segnato in rosso,fai delle chiamate della funzione albero completo senza passargli i parametri altezza foglie e altezza corrente...
in quel passaggio devo riportare i parametri così come sono o devo incrementarli/decrementarli??