[Algoritmi] Complessità spaziale visita anticipata iterativa

[xneo1]

Salve a tutti,
L'algoritmo di visita anticipata (detta anche visita pre-order o prefissa) di un albero binario, consiste nel visitare prima la radice, poi il figlio sinistro e poi il figlio destro, il tutto ricorsivamente.

Poichè l'algoritmo è naturalmente e facilmente implementabile attraverso la ricorsione, per ottenere una versione iterativa si deve ricorrere al supporto di uno stack.

Comincio nel dire che per l'algoritmo ricorsivo la complessità spaziale è, nel caso migliore \(\displaystyle O(log(n)) \), mentre nel caso peggiore è \(\displaystyle O(n) \).
Il caso migliore si ha quando l'albero è completo e quindi l'altezza dell'albero è \(\displaystyle log_2(n) \)
(Fin qui sono abbastanza sicuro delle mie affermazioni)

Ora posto l'algoritmo in forma iterativa:

void visitaAnticipataIterativa(AlberoBin a) {
    LinkedList<AlberoBin> stack=new LinkedList<AlberoBin>();
    stack.push(a);
		
    while(!stack.isEmpty()) {
        AlberoBin nodo=stack.pop();
	if(nodo!=null) {
	    System.out.println(nodo.val());
				
	    AlberoBin figlioDestro=nodo.des();
	    if(figlioDestro!=null) {
	        stack.push(figlioDestro);
	    }
	    AlberoBin figlioSinistro=nodo.sin();
	    if(figlioSinistro!=null) {
	        stack.push(figlioSinistro);
	    }
	}
    }
}

Penso che la complessità spaziale, dipenda dal numero di "riferimenti" dell'albero presenti nello stack.

Se dovessi fare un analisi della complessità spaziale, distinguendo il caso migliore e il caso peggiore, mi sentirei di dire che
il caso migliore corrisponde all'albero degenere e quindi la complessità spaziale sarebbe \(\displaystyle O(1) \), il caso peggiore corrisponde all'albero completo è la complessità spaziale sarebbe \(\displaystyle O(2^h) \) con h altezza dell'albero, in particolare se \(\displaystyle h=log_2(n \)) la complessità spaziale sarebbe lineare.

Secondo voi è giusta questa analisi?

[onlyReferee]

Ciao xneo
Sì, analisi perfetta. Hai correttamente considerato come complessità spaziale di fatto la dimensione dello stack che è dato dal numero massimo di riferimenti ad un nodo dell'albero contenuti nello stesso in un dato momento.
Unico appunto sull'ultima considerazione: che cos'è $n$ nella tua formula $h = \log_2 (n)$ Il numero di nodi dell'albero Lo chiedo ovviamente solo per comprendere appieno la stessa.

[xneo1]

si n è il numero di nodi dell'albero. Lo so che dovrebbe essere sempre specificato.
Comunque la ringrazio Professore per la conferma.

[onlyReferee]

La prossima volta che mi dai del lei non rispondo più .
[size=50]Scherzo, tranquillo, lo dico solo perché in realtà non sono professore anche se spero di diventarlo tra non molto.[/size]
Comunque se noti volendo essere precisi $h = \log_2 n$ avviene soltanto nel caso in cui si ha un solo nodo (nella fattispecie quello più a sinistra essendo l'albero in questione completo) nell'ultimo livello dell'albero. Pertanto è questo l'unico caso in cui la complessità è lineare. Sei d'accordo

[xneo1]

Si, d'accordissimo.
Completo nella definizione "originale" (per intenderci il mio prof lo chiama albero pieno).

[onlyReferee]

Esatto, mi sono ricordato delle definizioni che avevi dato nell'altro thread .