Albero binario di ricerca ottimo

[marx1]

Come da oggetto qualcuno sa dirmi quando un abr si dice ottimo.
Inoltre mi servirebbe un algoritmo che in O(n^3) lo costruisca

[Umby2]

Posso immaginare che possa trattarsi di un albero bilanciato.
Voglio dire di un albero, che non avendo subito molti inserimenti, ha i suoi rami della stessa grandezza, e quindi non necessita di un bilanciamento.

[Nidhogg]

"marx":Come da oggetto qualcuno sa dirmi quando un abr si dice ottimo.
Inoltre mi servirebbe un algoritmo che in O(n^3) lo costruisca

Data una sequenze $K=(:k_1,k_2,...,k_n:)$ di $n$ chiavi distinte e ordinate (con $k_1 E[costo di una ricerca in T] = $sum_{i=1}^n ("profondità"_T(k_i)+1)*p_i + sum_{i=o}^n("profondità"_T(d_i)+1)*q_i = 1 +sum_{i=1}^n"profondità"_T(k_i)*p_i+sum_{i=0}^n"profondità"_T(d_i)*q_i$, dove $"profondità"_T$ indica la profondità di un nodo nell'albero $T$.
Per un dato insieme di probabilità, l'obiettivo è di costruire un albero binario di ricerca il cui costo atteso di ricerca è minimo. Questo albero è propriamente detto albero binario di ricerca ottimo.

Ora il controllo completo di tutte le possibilità non riesce a produrre un algoritmo efficiente. Il numero di alberi binari con n foglie è $Omega((4^n)/(n^(3/2)))$, quindi per una ricerca completa dovremmo esaminare un numero esponenziale di alberi binari di ricerca. Utilizziamo quindi la programmazione dinamica per risolvere questo problema.

Per l'algoritmo devi analizzare la struttura di un albero binario di ricerca ottimo e utilizzare i concetti della programmazione dinamica.


A presto, Ermanno.

[marx1]

grazie per la risposta sei stato piu che esauriente
a presto

[Ext3rmin4tor]

L'algoritmo per la costruzione dell'albero sfrutta un'idea molto simile a quella utilizzata nel matrix chain, non so se l'hai mai visto

[marx1]

si avevo gia visto la possibile analogia grazie lo stesso