Alberi binari di ricerca

[giacomovicinanza]

Salve a tutti. Non riesco a capire come impostare questo determinato problema. Grazie mille per chi mi aiuterà. DI seguito la traccia.
"Indicare e commentare brevemente il tempo di esecuzione nel caso pessimo della cancellazione in un albero binario in cui in precedenza è stata inserita la seguente sequenza (nell'ordine indicato) di elementi:
1,2,3,4,5,...,n-3,n-2,n-1,n
Mostrare inoltre l'output di una visita post-ordine in tale albero"

[Quinzio]

Com'e' fatto l'albero dopo che hai inserito quegli elementi ?
Com'e' l'output della visita post-order ?

[apatriarca]

Il problema mi sembra un po' ambiguo perché non è specificato un particolare algoritmo di inserimento né di struttura dell'albero. Sappiamo solo che è stata data in input una particolare sequenza. Alcune interpretazioni possono essere:
1. Si tratta di un albero binario di ricerca. In questo caso l'albero diviene in pratica una lista.
2. Gli elementi vengono inseriti come in un heap. In questo caso si ha un albero binario completo.

Suppongo l'interpretazione "corretta" sia la prima, ma è importante sapere che non ogni albero binario è di ricerca se il professore ha fatto questa associazione.

[giacomovicinanza]

Il tempo di esecuzione nel caso pessimo della cancellazione è dovuto da O(n) essendo dovuto da alberi molto sbilanciati e profondi. Una visita in post-ordine avviene in questo modo:
I. entro nel generico nodo n
II. e III: lancio la procedura sul figlio sinistro e destro. raccolgo gli output dalle procedure lanciate sui figli
IV. eseguo la computazione su n, mi avvalgo dei valori computati sui figli
V. esco dal nodo n. restituisco un output alla procedura lanciata sul genitore
ordine di visita: n, n-1, n-2, n-3, ..., 5, 4, 3, 2, 1

[apatriarca]

@giacomovicinanza Mi sembra corretto

[giacomovicinanza]

Grazie mille

[vict85]

Comunque il tuo professore di strutture dati dà molte cose per scontato che non andrebbero considerate tali. Per esempio, non ogni albero binario è di ricerca e non ogni lista è ordinata (anzi, trovo che le liste ordinate non andrebbero mai insegnate perché sono peggio di ogni loro alternativa e che tutti gli utilizzi sensati delle liste siano con liste non ordinate). Inoltre, relativamente al tuo problema, esistono algoritmi per bilanciare l'albero di ricerca in modo da eliminare questo caso. Si tratta, tra l'altro, di un problema interessante. Quasi tutti gli alberi di ricerca che troverai a livello professionale saranno bilanciati (se ti interessa puoi cercare RB-albero o quelli AVL su wiki).