[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
Ciao xneo 
Allora, ci servono (nella mia soluzione) due metodi. Il primo che visiti i nodi dell'albero del penultimo livello uno per uno partendo da quello più a sinistra e per ciascuno di essi verifichi quali figli ha. In tal caso:
dovresti cambiarla in
Prova a pensare: se non puoi verificare la proprietà su un livello negativo dell'albero esso sarà da considerarsi banalmente pieno fino a lì, no
Allora, ci servono (nella mia soluzione) due metodi. Il primo che visiti i nodi dell'albero del penultimo livello uno per uno partendo da quello più a sinistra e per ciascuno di essi verifichi quali figli ha. In tal caso:
[*:32wc44ut]Se il nodo ha entrambi i figli passa al successivo;[/*:m:32wc44ut]
[*:32wc44ut]Se ha solo il figlio destro e non quello sinistro può ritornare direttamente false;[/*:m:32wc44ut]
[*:32wc44ut]Se non ha figli oppure ha solo il figlio sinistro allora può richiamare il secondo metodo che ti descrivo di seguito.[/*:m:32wc44ut][/list:u:32wc44ut]
Il secondo deve verificare che tutti i nodi dell'albero del penultimo livello rimanenti (successivi all'ultimo analizzato) non abbiano figli. Se viene rilevato che uno di questi nodi ha uno o due figli allora restituisce false altrimenti procede con i successivi del penultimo livello (sempre nell'ordine da sinistra a destra). Se i nodi da analizzare sono terminati allora può ritornare true.
Spero di esserti stato abbastanza di supporto intanto.
Nota: nel tuo algoritmo per verificare se l'albero è pieno l'istruzione
[...] if(livello<0) return false; [...]
dovresti cambiarla in
[...] if(livello<0) return true; [...]
Prova a pensare: se non puoi verificare la proprietà su un livello negativo dell'albero esso sarà da considerarsi banalmente pieno fino a lì, no
Che bello che c'é qualcuno, diverso da Giova411, che scrive sugli ALBERI!!!!!
La natura va rispettata!!! (..e dopo questa mi banno da solo...)
Penso che ONLY ti abbia dato le dritte giuste! Complessità????
La natura va rispettata!!! (..e dopo questa mi banno da solo...)
Penso che ONLY ti abbia dato le dritte giuste! Complessità????
Allora, ci servono (nella mia soluzione) due metodi. Il primo che visiti i nodi dell'albero del penultimo livello uno per uno partendo da quello più a sinistra e per ciascuno di essi verifichi quali figli ha
Quindi provando ad abbozzare qualcosa:
boolean verificaCompleto(Albero a, int livello) {
if(!verificaPieno(a, livello-1)) return false;
// se fin qui sono ancora "vivo" significa
// che tutti i nodi fino al penultimo livello non sono null
//provo ad arrivare al penultimo livello
Coda<Albero> c=new Coda<Albero>()
coda.addLast(a);
while(livello>=1) {
int l=coda.size();
while(l>0) {
Albero nodo=coda.removeFirst();
l--;
coda.addLast(nodo.sin());
coda.addLast(nodo.des());
}
livello--;
}
//se tutte le cose sono andate per il verso giusto nella coda ci dovrebbero stare
// i nodi dell'ultimo livello alcuni eventualmente null
//a questo punto se in coda trovo un nodo uguale a null,
//tutti i nodi a destra devono essere anche null
//altrimenti l'albero non sarebbe completo
boolean nodoANull=false
while(!c.isEmpty()) {
Albero nodo=c.removeFirst();
if(nodo==null) nodoANull=true;
if(nodo!=null && nodoANull) return false;
}
return true;
}Ho scritto questa soluzione a caldo, ora, così come mi è venuta.
Non so se è giusta, perlomeno sono convinto che ci sia una soluzione più efficiente.
Penso che ONLY ti abbia dato le dritte giuste! Complessità????
Intendi complessità di verificaPieno()?
Comunque siccome non posso fare previsioni sulla numerosità di n, cioè non posso analizzare il metodo dicendo "se a è null o se a ha un solo elemento", e inoltre va considerato anche il parametro livello che passon in input
Se livello<=0 la complessità è O(1), indipendentemente dal numero di nodi che l'albero ha.
Se livello>0 invece si visitano (2^(livello+1)), quindi se livello è uguale all'altezza dell'albero la complessità è O(n).
Per quanto riguarda la complessità spaziale,
se livello<=0 complessità spaziale O(1)
se livello>0 posso distinguere un caso migliore e un caso peggiore.
Il caso peggiore è si ha quando l'albero è pieno fino al livello considerato in questo caso la complessità spaziale è O(l)
Il caso migliore si ha quando l'albero è degenere, in questo caso la complessità spaziale è costante.
(Ditemi se è giusto)
(Ditemi se è giusto????)
L'ultima parte del tuo codice a mio parere va modificata come segue (ho messo anche la dichiarazione della variabile nodo fuori dal ciclo altrimenti ne crea inutilmente una ad ogni iterazione):
Di fatto sono due cicli separati per i due differenti test da effettuare di cui ti parlavo nel mio post precedente. Ah, se esiste una soluzione più semplice sarò lieto di apprenderla chiaramente
Riguardo alla complessità di verificaPieno...
A livello temporale hai $O(n)$ (con $n$ numero di nodi dell'albero, sempre bene specificarlo) come hai affermato te: i nodi dell'albero vengono visitati una ed una sola volta. Quando si parla di complessità e non si fanno altre specifiche si intende sempre e comunque il caso peggiore pertanto non occorre che esegui distinzioni quali "se livello < 0 ", ecc.
A livello spaziale lo stesso poiché per ogni nodo bisogna memorizzare i valori dei puntatori ai suoi due figli più i valori dei due interi rappresentati il livello corrente (due chiamate ricorsive per ciascun nodo con quattro valori da memorizzare quindi fanno risultare la complessità $O(4 n) = O(n)$).
[...]
boolean nodoANull = false;
Albero nodo;
while(!c.isEmpty() && !nodoANull) {
nodo = c.removeFirst();
if(nodo == null) nodoANull = true;
}
while(!c.isEmpty() && nodoANull) {
nodo = c.removeFirst();
if(nodo != null) return false;
}
return true;
Di fatto sono due cicli separati per i due differenti test da effettuare di cui ti parlavo nel mio post precedente. Ah, se esiste una soluzione più semplice sarò lieto di apprenderla chiaramente
Riguardo alla complessità di verificaPieno...
A livello temporale hai $O(n)$ (con $n$ numero di nodi dell'albero, sempre bene specificarlo) come hai affermato te: i nodi dell'albero vengono visitati una ed una sola volta. Quando si parla di complessità e non si fanno altre specifiche si intende sempre e comunque il caso peggiore pertanto non occorre che esegui distinzioni quali "se livello < 0 ", ecc.
A livello spaziale lo stesso poiché per ogni nodo bisogna memorizzare i valori dei puntatori ai suoi due figli più i valori dei due interi rappresentati il livello corrente (due chiamate ricorsive per ciascun nodo con quattro valori da memorizzare quindi fanno risultare la complessità $O(4 n) = O(n)$).
ok per quanto riguarda la complessità temporale.
Per quanto riguarda la complessità spaziale, nel caso peggiore, non si hanno log(n) chiamate ricorsive innestate?
Ogni chiamata ricorsiva non ha costo O(1)?
Se così fosse la complessità spaziale risulterebbe O(log(n)).
Non capisco come può essere O(n) se non ci sono mai n chiamate ricorsive sospese "una dietro l'altra".
Per quanto riguarda la complessità spaziale, nel caso peggiore, non si hanno log(n) chiamate ricorsive innestate?
Ogni chiamata ricorsiva non ha costo O(1)?
Se così fosse la complessità spaziale risulterebbe O(log(n)).
Non capisco come può essere O(n) se non ci sono mai n chiamate ricorsive sospese "una dietro l'altra".
La tua osservazione sulla complessità spaziale è fondata però...in realtà non so fino a quando restano sospese tali chiamate. Ieri sera quando ti ho scritto ero un attimo di fretta. Francamente ripensandoci bene ora il numero di chiamate ricorsive effettuate sarà pari a (utilizzo la serie geometrica):
\[
\sum_{i = 0}^{l_{max}} 2^i = \frac{1 - 2^{l_{max} - 1}}{1 - 2} = 2^{l_{max} - 1} - 1
\]
dove $l_{max} - 1$ è chiaramente il penultimo livello dell'albero.
Questo perché nell'ordine abbiamo $1 + 2 + 2^2 + 2^3 + ... + 2^{l_{max} - 1}$ chiamate ricorsive effettuate.
Da qui deriva che la complessità di verificaPieno sarà $O(2^{l_{max} - 1})$.
Provo a spiegarti anche perché (secondo me) tale complessità non può essere $O(\log_2 n)$. Se lo spazio iniziale del nostro problema è pari ad $n$ (numero di nodi dell'albero) e dobbiamo nel caso peggiore eseguire un'operazione su tutti i nodi dell'albero (in tal caso una semplice verifica) dobbiamo per forza di cose scorrerli tutti e pertanto non possiamo pensare minimamente che lo spazio richiesto sia inferiore ad $O(n)$.
Diverso è il caso temporale che, in taluni problemi con un input di dimensione $n$, può richiedere un tempo inferiore (vedi ad esempio la ricerca binaria in un array di dimensione $n$ che richiede un tempo $O(\log_2 n)$).
\[
\sum_{i = 0}^{l_{max}} 2^i = \frac{1 - 2^{l_{max} - 1}}{1 - 2} = 2^{l_{max} - 1} - 1
\]
dove $l_{max} - 1$ è chiaramente il penultimo livello dell'albero.
Questo perché nell'ordine abbiamo $1 + 2 + 2^2 + 2^3 + ... + 2^{l_{max} - 1}$ chiamate ricorsive effettuate.
Da qui deriva che la complessità di verificaPieno sarà $O(2^{l_{max} - 1})$.
Provo a spiegarti anche perché (secondo me) tale complessità non può essere $O(\log_2 n)$. Se lo spazio iniziale del nostro problema è pari ad $n$ (numero di nodi dell'albero) e dobbiamo nel caso peggiore eseguire un'operazione su tutti i nodi dell'albero (in tal caso una semplice verifica) dobbiamo per forza di cose scorrerli tutti e pertanto non possiamo pensare minimamente che lo spazio richiesto sia inferiore ad $O(n)$.
Diverso è il caso temporale che, in taluni problemi con un input di dimensione $n$, può richiedere un tempo inferiore (vedi ad esempio la ricerca binaria in un array di dimensione $n$ che richiede un tempo $O(\log_2 n)$).
Se lo spazio iniziale del nostro problema è pari ad n (numero di nodi dell'albero) e dobbiamo nel caso peggiore eseguire un'operazione su tutti i nodi dell'albero (in tal caso una semplice verifica) dobbiamo per forza di cose scorrerli tutti e pertanto non possiamo pensare minimamente che lo spazio richiesto sia inferiore ad O(n).
Allora, il caso peggiore spazialmente si ha quando l'albero è effettivamente pieno.
In questo caso il massimo numero di chiamate ricorsive innestare è pari all'altezza dell'albero che, per un albero pieno, è \(\displaystyle log_2(n) \)
Supponiamo che questo sia l'albero:
1
2 3
4 5 6 7
le chiamate ricorsive sono verificaPieno(a.sin(), livello-1) e verificaPieno(a.des(), livello-1)
quando invoco verificaPieno(a.sin(), livello-1) ho 1 chiamata sospesa (quella in cui a ha radice 1)
a questo punto sto considerando il sotto albero sinistro con radice 2, e prima che possa invocare il metodo sul sotto albero destro che a radice 1, invoco nuovamente verificaPieno(a.sin(), livello-2); le chiamate sospese ora sono 2.
Da qui invoco sul sotto albero di radice 4 invoco ancora verificaPieno(a.sin(), livello-3) e sono a 3 chiamate sospese. Dopo questa chiamata srotolo la ricorsione fino ad arrivare alla radice 2, ecc.
Si può osservare come la complessità spaziale è pertanto \(\displaystyle O(log(n)) \).
Inoltre la relazione di ricorrenza per la complessità spaziale è:
\(\displaystyle S(n)=S(n/2)+O(1) \) che per Il Master Theorem ha soluzione \(\displaystyle O(log(n)) \).
"xneo":
[...]
quando invoco verificaPieno(a.sin(), livello-1) ho 1 chiamata sospesa (quella in cui a ha radice 1)
a questo punto sto considerando il sotto albero sinistro con radice 2, e prima che possa invocare il metodo sul sotto albero destro che a radice 1, invoco nuovamente verificaPieno(a.sin(), livello-2); le chiamate sospese ora sono 2.
Da qui invoco sul sotto albero di radice 4 invoco ancora verificaPieno(a.sin(), livello-3) e sono a 3 chiamate sospese. Dopo questa chiamata srotolo la ricorsione fino ad arrivare alla radice 2, ecc.
[...]
In realtà con l'implementazione attuale dell'algoritmo (la tua versione) dopo che è stato analizzato il nodo con chiave $4$ ne partono altre due di chiamate ricorsive (che poi però terminano in quanto individuano due nodi posti rispettivamente a null)...
A parte questo (potrei anche ricordarmi male io relativamente alle ricorrenze), l'importante è aver capito il ragionamento che sta alla base dell'algoritmo. A proposito: ti trovi con le mie correzioni dell'algoritmo
Scusate ma si poteva fare anche così senza badare al livello?
Albero se è vuoto è completo, se ha una sola foglia pure se no è sempre falso.
Il costo è costante per albero vuoto o con una sola foglia.
Se no penso sia strutturato come Merge $2T(n/2)$ quindi $theta(n)$
La complessià spaziale
abbiamo chiamate ricorsive e una sorta di stack creati di volta in volta ma sparo un $O(n)$ 
boolean completo(TREE t) if t= nil return true if t.left=nil and t.right=nil then return true if t.left=nil or t.right=nil then return false if t.left!=nil and t.right!=nil then return completo(t.left) and completo(t.right) else return false
Albero se è vuoto è completo, se ha una sola foglia pure se no è sempre falso.
Il costo è costante per albero vuoto o con una sola foglia.
Se no penso sia strutturato come Merge $2T(n/2)$ quindi $theta(n)$
La complessià spaziale
abbiamo chiamate ricorsive e una sorta di stack creati di volta in volta ma sparo un $O(n)$
No perché il problema è che tutte le foglie devono essere compattate a sinistra. Con l'algoritmo da te presentato se si ha un albero pieno fino al livello $l_{max} - 1$ avente (ad esempio) solo il nodo più a destra del livello $l_{max} - 1$ con due figli (e tutti gli altri nodi del livello $l_{max} - 1$ senza figli) viene restituito erroneamente true 
.
.
Ma la storia delle foglie a sinistra è un discorso, l'albero completo è un altro? O no?
L'albero è completo se tutti gli elementi che costituiscono l'albero hanno esattamente due figli, tranne ovviamente le foglie...
L'albero è completo se tutti gli elementi che costituiscono l'albero hanno esattamente due figli, tranne ovviamente le foglie...
"xneo":
[...]
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à.
[...]
Si ma poi ho cercato bene la definizione 
Un albero binario completo di altezza k è un albero binario in cui tutti i nodi, tranne le foglie, hanno esattamente due figli, e tutte le foglie si trovano al livello k.
Ma se vogliamo fare, per esercizio, che siano accatastati solo a sinistra (come un heap!), a me va benissimo!!!
Un albero binario completo di altezza k è un albero binario in cui tutti i nodi, tranne le foglie, hanno esattamente due figli, e tutte le foglie si trovano al livello k.
Ma se vogliamo fare, per esercizio, che siano accatastati solo a sinistra (come un heap!), a me va benissimo!!!
In effetti la definizione vera e propria sarebbe questa, hai ragione. Poi il nostro amico xneo ha proposto questa variante e...abbiamo cercato di venirgli incontro .
.
"onlyReferee":
In effetti la definizione vera e propria sarebbe questa, hai ragione. Poi il nostro amico xneo ha proposto questa variante e...abbiamo cercato di venirgli incontro
Only non fare il modesto! Lo stai aiutando solo tu il nostro amico, ed io sto qui a rompere!!!
Stavo, solo ora, cercando una soluzione diversa..
Utilizzando il fatto che la radice può essere messa (mi riferisco in una posizione di un ipotetico array creato ad hoc)
in $A[1]$ radice fissa sempre qui
figli sinistri LEFT(i) = 2i
figli destri RIGHT(i) = 2i + 1
per i rispettivi padri PARENT(i) = down|_ i/2 _|
Che si può fare con questi spunti?
](/datas/uploads/forum/emoji/eusa_wall.gif "Brick wall")
Mi sta antipatico mettere in una coda eventuali NIL
Ragazzi ci siete? Se dico cacchiatelle ditemelo.
Abbiamo il livello massimo (dato in input).
Io so che è binario quindi vale quanto scritto sopra.
Creo un array per il solo livello ultimo dove potrei avere foglie sparse e non tutte a sinistra.
Prima di arrivare a ciò faccio una verifica come quella suggerita prima da me senza badare al livello ma dalla radice fino al livello di altezza $h-1$. Se arrivo qui senza danno ho l'ultimo livello dove DEVONO stare a sinistra.
Da qui faccio una ricerca dicotomica che se ho un numero è occhei e cerco nella metà di destra dell'array.
Se ho un NIL cerco nella metà di sinistra. Appena trova la non continuità dei numeri allora FALSE
Non ricordo quall'algoritmo che trova subito un bit a zero dopo tanti uno consecutivi....
Dai ragazzi!!!!
Abbiamo il livello massimo (dato in input).
Io so che è binario quindi vale quanto scritto sopra.
Creo un array per il solo livello ultimo dove potrei avere foglie sparse e non tutte a sinistra.
Prima di arrivare a ciò faccio una verifica come quella suggerita prima da me senza badare al livello ma dalla radice fino al livello di altezza $h-1$. Se arrivo qui senza danno ho l'ultimo livello dove DEVONO stare a sinistra.
Da qui faccio una ricerca dicotomica che se ho un numero è occhei e cerco nella metà di destra dell'array.
Se ho un NIL cerco nella metà di sinistra. Appena trova la non continuità dei numeri allora FALSE
Non ricordo quall'algoritmo che trova subito un bit a zero dopo tanti uno consecutivi....
Dai ragazzi!!!!
La tua idea è niente male in effetti. In tal caso sappiamo che (supponendo che il livello minimo dell'albero sia $1$) se l'albero è pieno fino al livello $l_{max} - 1$ allora le prime $2^{l_{max} - 1}$ locazioni (celle) dell'array $A$ avranno un valore diverso da nil. Pertanto, analogamente alla mia soluzione proposta in origine, per avere la completezza dell'albero nel senso di avere tutte le foglie dell'ultimo livello $l_{max}$ accorpate a sinistra, dobbiamo verificare che celle vuote dell'array $A$ siano tutte in coda (non vi siano dunque in tal senso "buchi" di celle con nil in mezzo a celle con valore non nil).
Ciò detto secondo me la soluzione funziona, resta da capire se è preferibile o meno rispetto a quella originale che ho proposto in termine di complessità spaziale/temporale (sul primo aspetto sono un po' scettico però francamente).
PS: non è modestia, stiamo ragionando tutti assieme.
Ciò detto secondo me la soluzione funziona, resta da capire se è preferibile o meno rispetto a quella originale che ho proposto in termine di complessità spaziale/temporale (sul primo aspetto sono un po' scettico però francamente).
PS: non è modestia, stiamo ragionando tutti assieme
.
Only secondo me xneo l'ho fatto scappare! 
Per la complessità, se ci pensi, abbiamo la possibilità di accedere in modo diretto ad un array! Tempo costante!
(Ovvio che non sto dicendo che la procedura totale poi lo sia! Però credo si migliori qualcosa)
Che ne pensi di crearlo solo per l'ultimo livello e poi via di ricerca dicotomica
(Forse abbiamo scritto contemporaneamente e ti sei perso l'ultimo post)
Per la complessità, se ci pensi, abbiamo la possibilità di accedere in modo diretto ad un array! Tempo costante!
(Ovvio che non sto dicendo che la procedura totale poi lo sia! Però credo si migliori qualcosa)
Che ne pensi di crearlo solo per l'ultimo livello e poi via di ricerca dicotomica
(Forse abbiamo scritto contemporaneamente e ti sei perso l'ultimo post)
Abbiamo scritto quasi in contemporanea, sì. In realtà poi il sistema mi ha avvisato che nel frattempo avevi risposto ma ho voluto inviare il messaggio lo stesso per non mischiare troppe idee nella risposta, preferendo leggere prima il tuo nuovo post.
Creare l'array solo per l'ultimo livello... Si può fare: effettui una visita dell'albero per livelli scorrendo i nodi da sinistra a destra per ciascun livello. Poi una volta che arrivi all'ultimo livello se trovi un valore nel nodo inserisci quello nella posizione corrente dell'array (inizialmente settata ad $1$ ovviamente), altrimenti se trovi nil metti tale valore oppure uno sentinella scelto arbitrariamente ($-\infty$ ad esempio).
Creare l'array solo per l'ultimo livello... Si può fare: effettui una visita dell'albero per livelli scorrendo i nodi da sinistra a destra per ciascun livello. Poi una volta che arrivi all'ultimo livello se trovi un valore nel nodo inserisci quello nella posizione corrente dell'array (inizialmente settata ad $1$ ovviamente), altrimenti se trovi nil metti tale valore oppure uno sentinella scelto arbitrariamente ($-\infty$ ad esempio).
wow, ragazzi andateci piano con i post, non posso distrarmi un attimo che siamo arrivati già a 3 pagine.
Cerco di rispondere:
Per quanto riguarda le modifiche da apportare a verificaCompleto sono d'accordo, anche se il mio era già funzionante.
Si risparmia spazio in quanto la variabile nodo non viene dichiarata ogni volta nel while, anche se lo spazio occupato poi era costante.
Per quanto riguarda la complessità, è vero ci sono log(n)+1 chiamate, tuttavia la complessità risulta sempre O(log(n)) in quanto il termine additivo può essere trascurato passando alla notazione asintotica.
Per quanto riguarda la definizione, o meglio, le definizioni, in giro c'è ne stanno di diverse. Nel mio corso di studi il prof ha dato le definizioni che ho scritto.
In effetti se poi ci pensiamo bene la pienezza di un albero non è altro che un rafforzamento della proprietà di completezza.
Un albero pieno è anche un albero completo.
Un albero completo non è detto che sia pieno.
Cerco di rispondere:
Per quanto riguarda le modifiche da apportare a verificaCompleto sono d'accordo, anche se il mio era già funzionante.
Si risparmia spazio in quanto la variabile nodo non viene dichiarata ogni volta nel while, anche se lo spazio occupato poi era costante.
Per quanto riguarda la complessità, è vero ci sono log(n)+1 chiamate, tuttavia la complessità risulta sempre O(log(n)) in quanto il termine additivo può essere trascurato passando alla notazione asintotica.
Per quanto riguarda la definizione, o meglio, le definizioni, in giro c'è ne stanno di diverse. Nel mio corso di studi il prof ha dato le definizioni che ho scritto.
In effetti se poi ci pensiamo bene la pienezza di un albero non è altro che un rafforzamento della proprietà di completezza.
Un albero pieno è anche un albero completo.
Un albero completo non è detto che sia pieno.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo