정수 집합이 정렬된 순서로 제공되고 다른 배열 freq가 빈도 수로 지정됩니다. 우리의 임무는 모든 검색에 대한 최소 비용을 찾기 위해 해당 데이터로 이진 검색 트리를 만드는 것입니다.
보조 배열 비용[n, n]은 하위 문제의 솔루션을 해결하고 저장하기 위해 생성됩니다. 비용 매트릭스는 상향식 방식으로 문제를 해결하기 위한 데이터를 보유합니다.
입력 및 출력
Input: The key values as node and the frequency. Keys = {10, 12, 20} Frequency = {34, 8, 50} Output: The minimum cost is 142. These are possible BST from the given values. For case 1, the cost is: (34*1) + (8*2) + (50*3) = 200 For case 2, the cost is: (8*1) + (34*2) + (50*2) = 176. Similarly for case 5, the cost is: (50*1) + (34 * 2) + (8 * 3) = 142 (Minimum)
알고리즘
optCostBst(keys, freq, n)
입력: BST에 삽입할 키, 각 키의 빈도, 키 수.
출력: 최적의 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