इनपुट और आउटपुट इनपुट: नोड के रूप में कुंजी मान और आवृत्ति। 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) इनपुट: BST में डालने के लिए कुंजियाँ, प्रत्येक कुंजी के लिए आवृत्ति, कुंजियों की संख्या। आउटपुट: इष्टतम BST बनाने की न्यूनतम लागत। शुरुआत n x n आकार की cost मैट्रिक्स परिभाषित करें i रेंज 0 से n-1 में, करें cost[i, i] := freq[i] पूर्ण length रेंज 2 से n में, करें i रेंज 0 से (n-length+1) में, करें j := i + length - 1 cost[i, j] := ∞ r रेंज i से j में, करें यदि r > i, तो c := cost[i, r-1] अन्यथा c := 0 यदि r < j, तो c := c + cost[r+1, j] c := c + i से j तक आवृत्ति का योग यदि c < cost[i, j], तो cost[i, j] := c पूर्ण पूर्ण पूर्ण वापस cost[0, n-1] अंत उदाहरण (C++ कोड) #include using namespace std; int sum(int freq[], int low, int high) { 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++) cost[i][i] = freq[i]; for (int length = 2; length <= n; length++) { for (int i = 0; i <= n-length+1; i++) { int j = i + length - 1; cost[i][j] = INT_MAX; for (int r = i; r <= j; r++) { 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); }