DAA - Optimum Maliyetli İkili Arama Ağaçları

İkili Arama Ağacı (BST), anahtar değerlerin dahili düğümlerde depolandığı bir ağaçtır. Dış düğümler boş düğümlerdir. Anahtarlar sözlükbilimsel olarak sıralanmıştır, yani her dahili düğüm için sol alt ağaçtaki tüm anahtarlar düğümdeki anahtarlardan daha azdır ve sağ alt ağaçtaki tüm anahtarlar daha büyüktür.

Anahtarların her birini arama sıklığını bildiğimizde, ağaçtaki her düğüme erişmenin beklenen maliyetini hesaplamak oldukça kolaydır. Optimum ikili arama ağacı, her bir düğümü bulmak için minimum beklenen maliyete sahip bir BST'dir.

BST'deki bir elemanın arama süresi O(n)Dengeli BST arama süresinde ise O(log n). Yine arama süresi Optimal Maliyet İkili Arama Ağacında iyileştirilebilir, en sık kullanılan veriler köke ve kök öğeye daha yakın yerleştirilirken, en az kullanılan veriler yaprakların yanına ve yapraklara yerleştirilir.

Burada Optimal İkili Arama Ağacı Algoritması sunulmuştur. İlk olarak, sağlanan bir setten bir BST oluşturuyoruzn farklı anahtarların sayısı < k₁, k₂, k₃, ... k_n >. Burada, bir anahtara erişme olasılığını varsayıyoruzK_i dır-dir p_i. Bazı sahte anahtarlar (d₀, d₁, d₂, ... d_nAnahtar setinde bulunmayan değerler için bazı aramalar yapılabileceğinden) eklenir. K. Her kukla anahtar için varsayıyoruzd_i erişim olasılığı 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

Analiz

Algoritma gerektirir O (n³) üç iç içe geçtiğinden beri zaman fordöngüler kullanılır. Bu döngülerin her biri en fazlan değerler.

Misal

Aşağıdaki ağaç düşünüldüğünde maliyet 2,80'dir, ancak bu optimal bir sonuç değildir.

Düğüm	Derinlik	Olasılık	Katkı
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

Bu bölümde tartışılan algoritmayı kullanarak en uygun çözümü elde etmek için aşağıdaki tablolar oluşturulur.

Aşağıdaki tablolarda sütun dizini i ve satır dizini 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

kök	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

Bu tablolardan optimum ağaç oluşturulabilir.