डेटा स्ट्रक्चर में इष्टतम बाइनरी सर्च ट्री

पूर्णांक का एक सेट सॉर्टेड क्रम में दिया गया है और दूसरा सरणी freq आवृत्ति गणना के लिए है। हमारा कार्य उन डेटा के साथ एक बाइनरी सर्च ट्री बनाना है ताकि सभी खोजों के लिए न्यूनतम लागत प्राप्त हो सके।

सब-प्रॉब्लम्स के समाधान को हल करने और स्टोर करने के लिए एक सहायक सरणी cost[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) इनपुट: BST में इन्सर्ट करने के लिए कीज़, प्रत्येक कीज़ के लिए आवृत्ति, कीज़ की संख्या। आउटपुट: इष्टतम BST बनाने के लिए न्यूनतम लागत। Begin    आकार 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 + i से 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){ //low से 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++){ //0th पंक्ति से n-length+1 पंक्ति तक i के रूप में          int j = i+length-1;          cost[i][j] = INT_MAX; //प्रारंभ में अनंत स्टोर करें          for (int r=i; r<=j; r++){             //लागत ढूंढें जब 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); }

आउटपुट

Cost of Optimal BST is: 142