DAA - Alberi di ricerca binaria a costo ottimale

Un albero di ricerca binario (BST) è un albero in cui i valori delle chiavi sono memorizzati nei nodi interni. I nodi esterni sono nodi nulli. Le chiavi sono ordinate lessicograficamente, cioè per ogni nodo interno tutte le chiavi nel sottoalbero di sinistra sono minori delle chiavi nel nodo e tutte le chiavi nel sottoalbero di destra sono maggiori.

Quando conosciamo la frequenza di ricerca di ciascuna delle chiavi, è abbastanza facile calcolare il costo previsto per l'accesso a ciascun nodo dell'albero. Un albero di ricerca binario ottimale è un BST, che ha un costo minimo previsto per l'individuazione di ciascun nodo

Il tempo di ricerca di un elemento in un BST è O(n), mentre in una ricerca Balanced-BST il tempo è O(log n). Anche in questo caso il tempo di ricerca può essere migliorato in Optimal Cost Binary Search Tree, posizionando i dati utilizzati più di frequente nella radice e più vicini all'elemento radice, mentre i dati utilizzati meno frequentemente vicino alle foglie e nelle foglie.

Qui viene presentato l'algoritmo dell'albero di ricerca binaria ottimale. Per prima cosa, costruiamo un BST da una serie di filen numero di chiavi distinte < k₁, k₂, k₃, ... k_n >. Qui assumiamo la probabilità di accedere a una chiaveK_i è p_i. Alcune chiavi fittizie (d₀, d₁, d₂, ... d_n) vengono aggiunti in quanto potrebbero essere eseguite alcune ricerche per i valori che non sono presenti nel Key set K. Assumiamo, per ogni chiave fittiziad_i la probabilità di accesso è q_i.

Optimal-Binary-Search-Tree(p, q, n) 
e[1…n + 1, 0…n],  
w[1…n + 1, 0…n], 
root[1…n + 1, 0…n]  
for i = 1 to n + 1 do 
   e[i, i - 1] := qi - 1 
   w[i, i - 1] := qi - 1  
for l = 1 to n do 
   for i = 1 to n – l + 1 do 
      j = i + l – 1 e[i, j] := ∞ 
      w[i, i] := w[i, i -1] + pj + qj 
      for r = i to j do 
         t := e[i, r - 1] + e[r + 1, j] + w[i, j] 
         if t < e[i, j] 
            e[i, j] := t 
            root[i, j] := r 
return e and root

Analisi

L'algoritmo richiede O (n³) tempo, poiché tre annidati forvengono utilizzati i loop. Ciascuno di questi cicli assume al massimon valori.

Esempio

Considerando il seguente albero, il costo è 2,80, anche se questo non è un risultato ottimale.

Nodo	Profondità	Probabilità	Contributo
k 1	1	0.15	0.30
k 2	0	0.10	0.10
k 3	2	0,05	0.15
k 4	1	0.10	0.20
k 5	2	0.20	0.60
d 0	2	0,05	0.15
d 1	2	0.10	0.30
d 2	3	0,05	0.20
d 3	3	0,05	0.20
d 4	3	0,05	0.20
d 5	3	0.10	0.40
Total			2.80

Per ottenere una soluzione ottimale, utilizzando l'algoritmo discusso in questo capitolo, vengono generate le seguenti tabelle.

Nelle tabelle seguenti, l'indice di colonna è i e l'indice di riga è j.

e	1	2	3	4	5	6
5	2.75	2.00	1.30	0.90	0.50	0.10
4	1.75	1.20	0.60	0.30	0,05
3	1.25	0.70	0.25	0,05
2	0.90	0.40	0,05
1	0.45	0.10
0	0,05

w	1	2	3	4	5	6
5	1.00	0.80	0.60	0.50	0.35	0.10
4	0.70	0.50	0.30	0.20	0,05
3	0,55	0.35	0.15	0,05
2	0.45	0.25	0,05
1	0.30	0.10
0	0,05

radice	1	2	3	4	5
5	2	4	5	5	5
4	2	2	4	4
3	2	2	3
2	1	2
1	1

Da queste tabelle è possibile formare l'albero ottimale.