Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में मर्ज सॉर्ट ट्री


हमें एक पूर्णांक सरणी, सेगमेंट प्रारंभ और अंत पॉइंटर्स का एक सेट और एक कुंजी मान दिया गया है और यहां समस्या कथन दी गई रेंज में उन सभी मानों को ढूंढना है जो दिए गए कुंजी मान से छोटे या बराबर हैं।

उदाहरण से समझते हैं

इनपुट - arr[] = {7, 8 , 1, 4 , 6 , 8 , 10 }

सेगमेंट 1: start = 2, end = 4, k = 2

सेगमेंट 2: start = 1, end = 6, k = 3

आउटपुट - दी गई रेंज में कुंजी मान से छोटे या बराबर संख्याओं की गिनती 2 6 है

व्याख्या - [8, 1, 4] 2 से 4 तक की रेंज को दर्शाता है और 2 रेंज में दूसरी सबसे छोटी संख्या है [7, 8 , 1, 4 , 6 , 8 ] 1 से 6 तक की रेंज को दर्शाता है और 6 दी गई रेंज में तीसरी सबसे छोटी संख्या है

इनपुट - arr[] = {2, 7 , 9, 4 , 6 , 5 , 1 }

सेगमेंट 1: start = 3, end = 6, k = 4

सेगमेंट 2: start = 2, end = 5, k = 3

आउटपुट - दी गई रेंज में कुंजी मान से छोटे या बराबर संख्याओं की गिनती: 9 7

व्याख्या - [9, 4 , 6 , 5] 3 से 6 तक की रेंज को दर्शाता है और 9 दी गई रेंज में चौथी सबसे छोटी संख्या है [7 , 9, 4 , 6 ] 2 से 4 तक की रेंज को दर्शाता है और 7 दिए गए सेगमेंट रेंज में तीसरी सबसे छोटी संख्या है

नीचे दिए गए प्रोग्राम में उपयोग किया गया दृष्टिकोण इस प्रकार है:

  • एक पूर्णांक प्रकार की सरणी घोषित करें। सरणी का आकार गणना करें। पूर्णांक प्रकार का जोड़ा बनाने वाले वेक्टर प्रकार के चर घोषित करें। सरणी से वेक्टर में डेटा पुश करने के लिए FOR लूप शुरू करें।

  • दिए गए वेक्टर को सॉर्ट करें। MAX आकार के साथ पूर्णांक प्रकार के वेक्टर सरणी बनाएं।

  • generateTree(1, 0, size - 1, vec, tree) फ़ंक्शन को कॉल करें और getSmallestIndex को queryWrapper(2, 5, 2, size, vec, tree) पर सेट करें।

  • input[getSmallestIndex] प्रिंट करें।

  • getSmallestIndex को queryWrapper(1, 6, 4, size, vec, tree) फ़ंक्शन को कॉल करके सेट करें।

  • फ़ंक्शन void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]) के अंदर

    • जांचें IF leftIndex, rightIndex के बराबर है तो tree[treeIndex].push_back(a[leftIndex].second) सेट करें और लौटें

    • midValue को (leftIndex + rightIndex) / 2 पर सेट करें और generateTree(2 * treeIndex, leftIndex, midValue, a, tree), generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree) और merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin() कॉल करें। tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex])) सेट करें

  • फ़ंक्शन int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector tree[]) के अंदर

    • जांचें IF startIndex, endIndex के बराबर है तो tree[treeIndex][0] लौटाएं

    • mid को (startIndex + endIndex) / 2 पर सेट करें, last_in_query_range को (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin()) पर सेट करें

    • first_in_query_range को (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin()) पर सेट करें और M को last_in_query_range - first_in_query_range पर सेट करें

    • जांचें IF M, key से बड़ा या बराबर है तो calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree) लौटाएं

    • अन्यथा, calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree) लौटाएं।

  • फ़ंक्शन int queryWrapper(int queryStart, int queryEnd, int key, int n, vector<pair<int, int> > &a, vector<int> tree[]) के अंदर

    • calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree) फ़ंक्शन को कॉल करके लौटाएं

उदाहरण

#include <bits/stdc++.h> using namespace std; const int MAX = 1000; void generateTree(int treeIndex, int leftIndex, int rightIndex, vector<pair<int, int> > &a, vector<int> tree[]){     if (leftIndex == rightIndex){       tree[treeIndex].push_back(a[leftIndex].second);       return;     }     int midValue = (leftIndex + rightIndex) / 2;     generateTree(2 * treeIndex, leftIndex, midValue, a, tree);     generateTree(2 * treeIndex + 1, midValue + 1, rightIndex, a, tree);     merge(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), tree[2 * treeIndex + 1].begin(),     tree[2 * treeIndex + 1].end(), back_inserter(tree[treeIndex])); } int calculateKSmallest(int startIndex, int endIndex, int queryStart, int queryEnd, int treeIndex, int key, vector<int> tree[]){       if (startIndex == endIndex){           return tree[treeIndex][0];       }       int mid = (startIndex + endIndex) / 2;       int last_in_query_range = (upper_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryEnd) - tree[2 * treeIndex].begin());       int first_in_query_range = (lower_bound(tree[2 * treeIndex].begin(), tree[2 * treeIndex].end(), queryStart) - tree[2 * treeIndex].begin());       int M = last_in_query_range - first_in_query_range;       if (M >= key){           return calculateKSmallest(startIndex, mid, queryStart, queryEnd, 2 * treeIndex, key, tree);       }       else {           return calculateKSmallest(mid + 1, endIndex, queryStart, queryEnd, 2 * treeIndex + 1, key - M, tree);       } } int queryWrapper(int queryStart, int queryEnd, int key, int n,     vector<pair<int, int> > &a, vector<int> tree[]){       return calculateKSmallest(0, n - 1, queryStart - 1, queryEnd - 1, 1, key, tree); } int main(){     int input[] = { 7, 8 , 1, 4 , 6 , 8 , 10 };     int size = sizeof(input)/sizeof(input[0]);     vector<pair<int, int> > vec;     for (int i = 0; i < size; i++) {       vec.push_back(make_pair(input[i], i));     }     sort(vec.begin(), vec.end());     vector<int> tree[MAX];     generateTree(1, 0, size - 1, vec, tree);     cout<<"दी गई रेंज में कुंजी मान से छोटे या बराबर संख्याओं की गिनती:"<<endl;     int getSmallestIndex = queryWrapper(2, 4, 2, size, vec, tree);     cout << input[getSmallestIndex] << endl;     getSmallestIndex = queryWrapper(1, 6, 3, size, vec, tree);     cout << input[getSmallestIndex] << endl;     return 0; }

आउटपुट

यदि हम उपरोक्त कोड चलाते हैं तो यह निम्नलिखित आउटपुट उत्पन्न करेगा

दी गई रेंज में कुंजी मान से छोटे या बराबर संख्याओं की गिनती: 4 6

  1. C++ में BK ट्री परिचय C++ में BK ट्री परिचय

    BK ट्री या बर्कहार्ड ट्री (Burkhard tree) एक प्रकार की डेटा संरचना है जिसका उपयोग आमतौर पर लेवेंश्टाइन दूरी (Levenshtein distance) के आधार पर स्पेल चेक करने के लिए किया जाता है। इसका उपयोग स्ट्रिंग मिलान के लिए ऑटोकरेक्ट फीचर बनाने के लिए भी किया जाता है। मान लें कि हमारे पास एक डिक्शनरी में कुछ शब

  1. C++ में ट्री नोड्स डिलीट करें C++ में ट्री नोड्स डिलीट करें

    मान लीजिए हमारे पास एक ट्री है, यह ट्री नोड 0 पर रूटेड है, यह निम्नानुसार दिया गया है -नोड्स की संख्या nodes हैi-वें नोड का मान value[i] हैi-वें नोड का पैरेंट parent[i] हैहमें हर उस सबट्री को हटाना है जिसके नोड्स के मानों का योग 0 है, ऐसा करने के बाद ट्री में शेष नोड्स की संख्या लौटाएं। यदि ट्री इस

  1. C++ में ट्री डायमीटर C++ में ट्री डायमीटर

    मान लीजिए हमारे पास एक अनडायरेक्टेड ट्री है; हमें इसका डायमीटर ढूंढना है - उस ट्री में सबसे लंबे पथ में एज की संख्या उस ट्री का डायमीटर है। यहां ट्री को एज लिस्ट के रूप में दिया गया है जहां edges[i] = [u, v] नोड्स u और v के बीच एक बायडायरेक्शनल एज है। प्रत्येक नोड के लेबल सेट {0, 1, ..., edges.lengt