데이터 구조에서 최적의 이진 탐색 트리

정수 세트가 정렬된 순서로 제공되고 다른 배열 freq는 빈도 수로 지정됩니다. 우리의 임무는 모든 검색에 대한 최소 비용을 찾기 위해 해당 데이터로 이진 검색 트리를 만드는 것입니다.

보조 배열 비용[n, n]은 하위 문제의 솔루션을 해결하고 저장하기 위해 생성됩니다. 비용 매트릭스는 상향식 방식으로 문제를 해결하기 위한 데이터를 보유합니다.

입력 − 노드와 빈도로 키 값입니다.

Keys = {10, 12, 20}
Frequency = {34, 8, 50}

출력 − 최소 비용은 142입니다.

주어진 값에서 가능한 BST입니다.

사례 1의 경우 비용은 (34*1) + (8*2) + (50*3) =200입니다.

사례 2의 경우 비용은 (8*1) + (34*2) + (50*2) =176입니다.

마찬가지로 사례 5의 경우 비용은 (50*1) + (34 * 2) + (8 * 3) =142(최소)

알고리즘

optCostBst(keys, freq, n)
Input: Keys to insert in BST, frequency for each keys, number of keys.
Output: Minimum cost to make optimal BST.
Begin
   define cost matrix of size n x n
   for i in range 0 to n-1, do
      cost[i, i] := freq[i]
   done
   for length in range 2 to n, do
      for i in range 0 to (n-length+1), do
         j := i + length – 1
         cost[i, j] := ∞
         for r in range i to j, done
            if r > i, then
               c := cost[i, r-1]
            else
               c := 0
            if r < j, then
               c := c + cost[r+1, j]
            c := c + sum of frequency from i to j
            if c < cost[i, j], then
               cost[i, j] := c
         done
      done
   done
   return cost[0, n-1]
End

예시

#include <iostream>
using namespace std;
int sum(int freq[], int low, int high){ //sum of frequency from low to high range
   int sum = 0;
   for (int k = low; k <=high; k++)
      sum += freq[k];
   return sum;
}
int minCostBST(int keys[], int freq[], int n){
   int cost[n][n];
   for (int i = 0; i < n; i++) //when only one key, move along diagonal elements
      cost[i][i] = freq[i];
   for (int length=2; length<=n; length++){
      for (int i=0; i<=n-length+1; i++){ //from 0th row to n-length+1 row as i
         int j = i+length-1;
         cost[i][j] = INT_MAX; //initially store to infinity
         for (int r=i; r<=j; r++){
            //find cost when r is root of subtree
            int c = ((r > i)?cost[i][r-1]:0)+((r < j)?cost[r+1][j]:0)+sum(freq, i, j);
            if (c < cost[i][j])
               cost[i][j] = c;
         }
      }
   }
   return cost[0][n-1];
}
int main(){
   int keys[] = {10, 12, 20};
   int freq[] = {34, 8, 50};
   int n = 3;
   cout << "Cost of Optimal BST is: "<< minCostBST(keys, freq, n);
}

출력

Cost of Optimal BST is: 142