DAA - optymalne kosztowe binarne drzewa wyszukiwania

Drzewo wyszukiwania binarnego (BST) to drzewo, w którym wartości kluczy są przechowywane w węzłach wewnętrznych. Węzły zewnętrzne są węzłami pustymi. Klucze są uporządkowane leksykograficznie, tj. Dla każdego węzła wewnętrznego wszystkie klucze w lewym poddrzewie są mniejsze niż klucze w węźle, a wszystkie klucze w prawym poddrzewie są większe.

Znając częstotliwość wyszukiwania każdego z kluczy, dość łatwo jest obliczyć oczekiwany koszt dostępu do każdego węzła w drzewie. Optymalnym drzewem wyszukiwania binarnego jest BST, który ma minimalny oczekiwany koszt lokalizacji każdego węzła

Czas wyszukiwania elementu w BST to O(n), podczas gdy w zbalansowanym BST czas wyszukiwania wynosi O(log n). Ponownie czas wyszukiwania można poprawić w drzewie wyszukiwania binarnego optymalnego kosztu, umieszczając najczęściej używane dane w korzeniu i bliżej elementu głównego, jednocześnie umieszczając najmniej często używane dane w pobliżu liści i liści.

W tym miejscu przedstawiono algorytm optymalnego drzewa wyszukiwania binarnego. Najpierw budujemy BST z zestawu dostarczonych plikówn liczba różnych kluczy < k₁, k₂, k₃, ... k_n >. Tutaj zakładamy prawdopodobieństwo uzyskania dostępu do kluczaK_i jest p_i. Niektóre atrapy kluczy (d₀, d₁, d₂, ... d_n) są dodawane, ponieważ niektóre wyszukiwania mogą być wykonywane dla wartości, których nie ma w zestawie kluczy K. Zakładamy, że dla każdego atrapy kluczad_i prawdopodobieństwo dostępu wynosi 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

Analiza

Algorytm wymaga O (n³) czas, ponieważ trzy zagnieżdżone forpętle są używane. Każda z tych pętli przyjmuje co najwyżejn wartości.

Przykład

Biorąc pod uwagę poniższe drzewo, koszt wynosi 2,80, choć nie jest to optymalny wynik.

Węzeł	Głębokość	Prawdopodobieństwo	Wkład
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

Aby uzyskać optymalne rozwiązanie, korzystając z algorytmu omówionego w tym rozdziale, generowane są poniższe tabele.

W poniższych tabelach indeks kolumny to i a indeks wiersza to j.

mi	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

korzeń	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

Z tych tabel można utworzyć optymalne drzewo.