[Algoritmi] verifica Albero binario completo
salve a tutti,
come il titolo suggerisce dovrei implementare un algoritmo che mi verifichi se l'albero che passo come input è completo.
Per chi non lo sapesse un albero si dice completo se è pieno almeno fino al penultimo livello e nell'ultimo livello le foglie sono compattate a sinistra.
Un albero binario è pieno se ogni nodo interno ha tutti e due i figli e le foglie si trovano tutte alla stessa profondità.
Non ho nessuna difficoltà a verificare se un albero è pieno.
Mostro l'algoritmo (il codice è un misto di Java)
Per quanto riguarda L'albero completo ho pensato a questo approccio
if(verificaPieno(a, livello-1)) {
controllaFoglieASinistra(a);
}
purtroppo ho difficoltà a controllare che tutte le foglie sono controllate a sinistra
come il titolo suggerisce dovrei implementare un algoritmo che mi verifichi se l'albero che passo come input è completo.
Per chi non lo sapesse un albero si dice completo se è pieno almeno fino al penultimo livello e nell'ultimo livello le foglie sono compattate a sinistra.
Un albero binario è pieno se ogni nodo interno ha tutti e due i figli e le foglie si trovano tutte alla stessa profondità.
Non ho nessuna difficoltà a verificare se un albero è pieno.
Mostro l'algoritmo (il codice è un misto di Java)
boolean verificaPieno(Albero a, int livello) {
if(livello<0) return false;
if(livello==0) return a!=null;
if(a==null) return false;
Albero figlioSin=a.sin();
Albero figlioDes=a.des();
if(figlioSin==null && figlioDes!=null) return false;
if(figlioSin!=null && figlioDes==null) return false;
return pieno(figlioSin, livello-1) && pieno(figlioDes, livello-1);
}Per quanto riguarda L'albero completo ho pensato a questo approccio
if(verificaPieno(a, livello-1)) {
controllaFoglieASinistra(a);
}
purtroppo ho difficoltà a controllare che tutte le foglie sono controllate a sinistra
Risposte
Se si potesse avere un attributo tipo int come v.livello che possiede ciascun nodo sarebbe fattibile, mi da informazione utile. Quindi si potrebbe creare un solo array per il solo livello ultimo (dato in input) con le sentinelle messe quando ho nodi NIL. Dimensione sarà $A[1..2^(livellol-1)]$ 
Poi ricerca dicotomica che divide la ricerca per 2 ogni volta
Facciamo il codice? XNEO?!?!?!?!?
Poi ricerca dicotomica che divide la ricerca per 2 ogni volta
Facciamo il codice? XNEO?!?!?!?!?
Per la complessità temporale di verificaCompleto provo a fare questo ragionamento:
verificaPieno() ha complessità O(n)
poi c'è la fase di riempimento della coda, che è una sorta di visita per livelli e richiede tempo O(n)
infine abbiamo la verifica se le foglie sono tutte a sinistra e questa fase richiede tempo O(2^livello)
per cui ne deduco che la complessità spaziale è O(n)
Per quanto riguarda quella temporale:
verifica pieno richiede O(log(n)) spazio
mentre per la coda richiede al più O(2^livello) di spazio.
Quindi la complessità spaziale è 2^livello.
Se si riuscisse a non usare nessuna struttura dati per controllare che le foglie siano compattate a sinistra si avrebbe complessità spaziale logaritmica. Tuttavia così come stanno le cose siamo sotto una complessità spaziale lineare
verificaPieno() ha complessità O(n)
poi c'è la fase di riempimento della coda, che è una sorta di visita per livelli e richiede tempo O(n)
infine abbiamo la verifica se le foglie sono tutte a sinistra e questa fase richiede tempo O(2^livello)
per cui ne deduco che la complessità spaziale è O(n)
Per quanto riguarda quella temporale:
verifica pieno richiede O(log(n)) spazio
mentre per la coda richiede al più O(2^livello) di spazio.
Quindi la complessità spaziale è 2^livello.
Se si riuscisse a non usare nessuna struttura dati per controllare che le foglie siano compattate a sinistra si avrebbe complessità spaziale logaritmica. Tuttavia così come stanno le cose siamo sotto una complessità spaziale lineare
secondo me non serve fare la ricerca binaria. In quanto non si avrebbero significativi vantaggi.
Così come è scritto adesso la complessità temporale è 2O(n)+O(2^livello)
Se facciamo la ricerca binaria la complessità diventa 2O(n)+O(log(n))
Attenzione:
2^livello sembrerebbe un termine esponenziale, ma in realtà è minore di n, anzi sono (n/2)+1.
Così come è scritto adesso la complessità temporale è 2O(n)+O(2^livello)
Se facciamo la ricerca binaria la complessità diventa 2O(n)+O(log(n))
Attenzione:
2^livello sembrerebbe un termine esponenziale, ma in realtà è minore di n, anzi sono (n/2)+1.
Ma io ho proposto una ricerca binaria in un array che contiene le sole foglie. Per l'albero che sta sopra non opero con nessuna struttura dati. Le sole foglie le metto in questo array e poi lì verifico se sono accatastate a sinistra.
Cmq non dare troppo peso alle mie deduzioni, Only potrebbe davvero segnarti una strada ALTERNATIVA E MIGLIORE a quella che hai trovato solo.
Però rileggi le cose che dicevamo. Se poi vuoi possiamo scrivere il codice che, in queso caso, prende quello mio "semplice" ed "elegante"
fino al penultimo livello. Poi arrivati all'ultimo "giochiamo" con un semplice array (e non una coda!) che non contiene tutti gli n elementi! Sole le foglie ed i NIL. Verifichiamo poi con sentinelle se codesti NIL sono tutti consecutivi a destra ed i valori reali delle foglie consecutive tutte a sinistra.
Che dici? Ma aspettiamo Only che, invece di fare la tesi, ha una pazienza $+oo$ verso gli utenti di Matematicamente ma, soprattutto, verso di noi
Cmq non dare troppo peso alle mie deduzioni, Only potrebbe davvero segnarti una strada ALTERNATIVA E MIGLIORE a quella che hai trovato solo.
Però rileggi le cose che dicevamo. Se poi vuoi possiamo scrivere il codice che, in queso caso, prende quello mio "semplice" ed "elegante"
fino al penultimo livello. Poi arrivati all'ultimo "giochiamo" con un semplice array (e non una coda!) che non contiene tutti gli n elementi! Sole le foglie ed i NIL. Verifichiamo poi con sentinelle se codesti NIL sono tutti consecutivi a destra ed i valori reali delle foglie consecutive tutte a sinistra.Che dici? Ma aspettiamo Only che, invece di fare la tesi, ha una pazienza $+oo$ verso gli utenti di Matematicamente ma, soprattutto, verso di noi
boolean completo(TREE t, integer l)
if t=nil return true
if t.left=nil and t.right=nil then return true
% t.livello si presuppone che sia memorizzato all'interno dei nodi in un campo speciale
else if (t.livello < l) then
if t.left=nil or t.right=nil then return false
if t.left!=nil and t.right!=nil then
return completo(t.left, t.livello) and completo(t.right, t.livello)
else return false
else if (t.livello = l) then
% siamo all'ultimo livello "problematico" delle foglie dato in input
integer[] A = new integer[1 .. 2^(livello−1) ]
integer i=1
while i<=2^(livello−1) do
if t.left != nil then
A[i] = t.value
i++
if t.right != nil then
A[i] = t.value
i++
else
A[i] = +oo
i++
% qui non so bene che fare, abbiamo riempito un array con valori e NIL (ma messi sottoforma di +oo)
% dobbiamo controllare questo array, anche in modo sequenziale ma avrei complessità non buona
integer i=1
boolean nodonil=false
% uso nodonil come semaforo
while( i<=2^(livello−1) and !nodonil) do
if !(A[i]< +oo) then nodonil=true
i++
i--
while(i<= 2^(livello−1) and nodonil) do
if (A[i]<+oo) then return false
i++
return true
Non vorrei che mi sfuggisse qualche dettaglio ma...la ricerca binaria (o dicotomica) che dir si voglia presuppone che l'array sia ordinato. Inoltre...per il controllo che abbiamo da implementare non vedo come possa essere utile (sempre se non ho preso abbagli).
"onlyReferee":
Non vorrei che mi sfuggisse qualche dettaglio ma...la ricerca binaria (o dicotomica) che dir si voglia presuppone che l'array sia ordinato. Inoltre...per il controllo che abbiamo da implementare non vedo come possa essere utile (sempre se non ho preso abbagli).
Sì non l'ho usata poi!
[size=50]SEI MITICO ONLY[/size]
Ovviamente dipende da cosa ci capita come albero!!! Se è veramente completo e pieno a sinistra abbiamo complessità peggiore in qualsiasi campo
Ii in effetti la ricerca binaria non si può fare, e comunque se si potesse fare richiederebbe tempo O(2^livello) (ho sbagliato prima).
Comunque per me il problema è risolto, perchè il codice che ho scritto funziona, con le modifiche proposte da onlyReferee si risparmia qualcosa a livello di occupazione di memoria.
L'unico modo per abbassare la complessità spaziale è implementare una procedura che controlla il compattamento delle foglie a sinistra in tempo O(log(n))
Comunque per me il problema è risolto, perchè il codice che ho scritto funziona, con le modifiche proposte da onlyReferee si risparmia qualcosa a livello di occupazione di memoria.
L'unico modo per abbassare la complessità spaziale è implementare una procedura che controlla il compattamento delle foglie a sinistra in tempo O(log(n))
Vi riporto solo la parte che ho corretto nel codice (commentato nelle parti sistemate):
while i<=2^(livello−1) do
if t.left != nil then
//In A[2 * i] (non in A[i]) devo mettere t.left.value (non t.value) ed in A[2 * i + 1] (non in A[i]) t.right.value (non t.value)
A[2 * i] = t.left.value
i++
if t.right != nil then
A[2 * i + 1] = t.right.value
i++
else
A[i] = +oo
i++
% qui non so bene che fare, abbiamo riempito un array con valori e NIL (ma messi sottoforma di +oo)
% dobbiamo controllare questo array, anche in modo sequenziale ma avrei complessità non buona
integer i=1
boolean nodonil=false
% uso nodonil come semaforo
while( i<=2^(livello−1) and !nodonil) do
if !(A[i]< +oo) then nodonil=true
i++
//Non serve i++, sono già posizionato giusto ed evito di fare un controllo in più
while(i<= 2^(livello−1) and nodonil) do
if (A[i]<+oo) then return false
i++
return true
@xneo: Secondo me sulla complessità spaziale ti sbagli perché utilizzi una coda in tutti i livelli e non serve. Immagina questa fisarmonica che si riempie e si svuota sommata allo stack che creano le ricorrenze..
Come detto prima, ma sopratutto da Only che è dotto, il codice delle prime pagine dovrebbe andare. =)
Se si hanno più versioni si impara molto in questa materia!!!
Come detto prima, ma sopratutto da Only che è dotto, il codice delle prime pagine dovrebbe andare. =)
Se si hanno più versioni si impara molto in questa materia!!!
Anche io notavo questo fatto della coda, Giova411. Non ci ho dato molto peso in fase iniziale. In realtà quando poi si lavora nell'area stack con la memoria statica ciò che viene memorizzato per la coda al momento della chiamata ricorsiva è la referenza (indirizzo) al primo elemento della stessa e non l'intera struttura (altrimenti si esaurirebbe la memoria nel giro di brevissimo tempo chiaramente). Almeno così funziona per Java (lo dico visto che è il linguaggio che sta usando xneo).
Certo, confrontare le versioni è sempre utilissimo.
Certo, confrontare le versioni è sempre utilissimo.
Non posso spannare!!!!
La prima versione di xneo, però, devo vederla meglio...
E' un po' disordinata quello sì 
e porta a casa il complimento! Da parte mia un grazie grande grande!!!!La prima versione di xneo, però, devo vederla meglio...
E' un po' disordinata
quello sì
Allora il massimo numero di puntatori (perchè alla fine di nella coda ci sono puntatori ai nodi degli alberi) e quindi la massima lunghezza della coda è 2^livello (se non erro).
Inoltre la coda viene riempita in una parte iterativa dell'algoritmo. Ciò che è ricorsivo è il metodo verificaPieno.
Dalle piccole conoscenze che ho (alcune grazie anche a onlyReferee) la complessità spaziale non è il risultato della somma della memoria occupata istante per istante durante l'esecuzione dell'algoritmo, ma la massima memoria utilizzata dall'algoritmo.
Faccio un esempio.
Istante t0 --> lunghezza coda=0
Istante t1 --> lunghezza coda=8
Istante t2 --> lunghezza coda=2
Istante t3 --> lunghezza coda=3
Istante t4 --> lunghezza coda=1, e qui termina l'algoritmo.
La complessità spaziale in base al numero di elementi della coda risulterebbe uguale a 8 e non uguale alla somma delle lunghezze istante per istante.
Inoltre la coda viene riempita in una parte iterativa dell'algoritmo. Ciò che è ricorsivo è il metodo verificaPieno.
Dalle piccole conoscenze che ho (alcune grazie anche a onlyReferee
) la complessità spaziale non è il risultato della somma della memoria occupata istante per istante durante l'esecuzione dell'algoritmo, ma la massima memoria utilizzata dall'algoritmo.Faccio un esempio.
Istante t0 --> lunghezza coda=0
Istante t1 --> lunghezza coda=8
Istante t2 --> lunghezza coda=2
Istante t3 --> lunghezza coda=3
Istante t4 --> lunghezza coda=1, e qui termina l'algoritmo.
La complessità spaziale in base al numero di elementi della coda risulterebbe uguale a 8 e non uguale alla somma delle lunghezze istante per istante.
Perdonami, ma al livello ultimo non riempi cmq al massimo la coda con valori NIL pure quando non ci sono foglie vere?
Si, certo.
Nell'ultimo livello ci sono 2^livello nodi (compresi i nodi=null)
Nell'ultimo livello ci sono 2^livello nodi (compresi i nodi=null)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo