DAA-최적 비용 이진 검색 트리

이진 검색 트리 (BST)는 키 값이 내부 노드에 저장되는 트리입니다. 외부 노드는 널 노드입니다. 키는 사전 순으로 정렬됩니다. 즉, 각 내부 노드에 대해 왼쪽 하위 트리의 모든 키가 노드의 키보다 적고 오른쪽 하위 트리의 모든 키가 더 큽니다.

각 키를 검색하는 빈도를 알면 트리의 각 노드에 액세스하는 데 예상되는 비용을 계산하기가 매우 쉽습니다. 최적의 이진 검색 트리는 BST로, 각 노드를 찾는 데 예상되는 최소 비용이 있습니다.

BST에서 요소의 검색 시간은 다음과 같습니다. O(n)반면 Balanced-BST 검색 시간은 O(log n). 검색 시간은 최적 비용 이진 검색 트리에서 개선 될 수 있습니다. 가장 자주 사용되는 데이터는 루트에 배치하고 루트 요소에 더 가깝게 배치하고 가장 자주 사용하지 않는 데이터는 잎과 잎에 배치합니다.

여기에서는 최적 이진 검색 트리 알고리즘이 제시됩니다. 먼저, 제공된 세트에서 BST를 구축합니다.n 고유 키 수 < k1, k2, k3, ... kn >. 여기서 우리는 키에 액세스 할 확률이Ki 이다 pi. 일부 더미 키 (d0, d1, d2, ... dn) 키 세트에없는 값에 대해 일부 검색이 수행 될 수 있으므로 추가됩니다. K. 우리는 각 더미 키에 대해di 접근 가능성은 qi.

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

분석

알고리즘에는 O (n3) 시간, 세 중첩 이후 for루프가 사용됩니다. 이러한 각 루프는 최대n 가치.

다음 트리를 고려할 때 비용은 2.80이지만 최적의 결과는 아닙니다.

마디 깊이 개연성 기부
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 0.05 0.20
d 3 0.05 0.20
d 4 0.05 0.20
d 5 0.10 0.40
Total 2.80

최적의 솔루션을 얻기 위해이 장에서 설명하는 알고리즘을 사용하여 다음 표가 생성됩니다.

다음 표에서 열 인덱스는 i 행 인덱스는 j.

이자형 1 2 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
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 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
0.55 0.35 0.15 0.05
2 0.45 0.25 0.05
1 0.30 0.10
0 0.05

뿌리 1 2 4 5
5 2 4 5 5 5
4 2 2 4 4
2 2
2 1 2
1 1

이 테이블에서 최적의 트리를 형성 할 수 있습니다.