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

सी++ में आरएमक्यू का उपयोग करके बाइनरी ट्री में एलसीए खोजें

अवधारणा

लेख एक पेड़ में दो नोड्स के एलसीए को आरएमक्यू समस्या में कम करके खोजने की समस्या को हल करने के लिए एक विधि बताता है।

उदाहरण

निम्नतम सामान्य पूर्वज (LCA) जड़ वाले पेड़ में दो नोड्स a और b में से T को रूट से सबसे दूर स्थित नोड के रूप में परिभाषित किया गया है, जिसमें a और b दोनों वंशज हैं।

उदाहरण के लिए, नीचे दिए गए आरेख के अनुसार, नोड डी और नोड I का एलसीए नोड बी है।

सी++ में आरएमक्यू का उपयोग करके बाइनरी ट्री में एलसीए खोजें

एलसीए समस्या को हल करने के लिए हम कई दृष्टिकोण लागू कर सकते हैं। ये दृष्टिकोण अपने समय और स्थान की जटिलताओं के संबंध में भिन्न हैं।

न्यूनतम क्वेरी श्रेणी (RMQ) दो निर्दिष्ट सूचकांकों के बीच न्यूनतम मान वाले तत्व की स्थिति का पता लगाने के लिए सरणियों पर लागू किया जाता है। हम आरएमक्यू को हल करने के लिए विभिन्न तरीकों को लागू कर सकते हैं। इस लेख के अनुसार, सेगमेंट ट्री आधारित दृष्टिकोण को समझाया गया है। सेगमेंट ट्री के संबंध में, प्रीप्रोसेसिंग समय ओ (एन) है और रेंज न्यूनतम क्वेरी के लिए समय ओ (लॉगन) है। यहां, सेगमेंट ट्री को स्टोर करने के लिए O(n) अतिरिक्त स्थान की आवश्यकता है।

LCA को RMQ में घटाना

हम एक यूलर टूर (पेंसिल उठाए बिना विज़िट करें) द्वारा जड़ से शुरू होने वाले पेड़ पर जाने के लिए इस विचार की व्याख्या करते हैं, जो एक डीएफएस (गहराई पहली खोज) - प्रीऑर्डर ट्रैवर्सल विशेषताओं के साथ टाइप ट्रैवर्सल है।

सी++ में आरएमक्यू का उपयोग करके बाइनरी ट्री में एलसीए खोजें

अवलोकन - उपरोक्त आरेख के अनुसार, नोड्स D और I का LCA नोड B है, जो T के DFS के दौरान D और I की यात्राओं के बीच आने वाले सभी लोगों के बीच रूट के निकटतम नोड को इंगित करता है। इसलिए हम यह अवलोकन कह सकते हैं घटाने की कुंजी है। फिर से हम कह सकते हैं कि हमारा नोड न्यूनतम स्तर पर नोड है और टी के यूलर टूर में ए और बी की लगातार घटनाओं (कोई भी) के बीच होने वाले सभी नोड्स के बीच उस स्तर पर एकमात्र नोड है।

कार्यान्वयन के लिए हमें तीन सरणियों की आवश्यकता है -

  • T

    . के यूलर टूर के क्रम में विज़िट किए गए नोड्स
  • टी के यूलर दौरे में प्रत्येक नोड स्तर का दौरा किया

  • टी के यूलर टूर में नोड का पहला घटना सूचकांक (चूंकि कोई भी घटना अच्छी होगी, आइए पहले वाले को ट्रैक करें)

सी++ में आरएमक्यू का उपयोग करके बाइनरी ट्री में एलसीए खोजें

विधि

  • पेड़ पर एक यूलर यात्रा करें, और यूलर, स्तर और प्रथम आवृत्ति सरणियों को भरें।

  • पहली घटना सरणी को लागू करते हुए, दो नोड्स से संबंधित सूचकांक प्राप्त करें जो कि न्यूनतम मान के लिए आरएमक्यू एल्गोरिदम को खिलाए गए स्तर सरणी में सीमा के कोने होंगे।

  • उस समय जब एल्गोरिथम श्रेणी में न्यूनतम स्तर का सूचकांक लौटाता है, हम इसे यूलर टूर ऐरे का उपयोग करके एलसीए निर्धारित करने के लिए लागू करते हैं।

उदाहरण

/* This C++ Program is implemented to find LCA of u and v by reducing the problem to RMQ */
#include<bits/stdc++.h>
#define V 9 // indicates number of nodes in input tree
int euler1[2*V - 1]; // indicates for Euler tour sequence
int level1[2*V - 1]; // indicates level of nodes in tour sequence
int firstOccurrence1[V+1]; // indicates first occurrences of nodes in tour
int ind; // indicates variable to fill-in euler and level arrays
//This is a Binary Tree node
struct Node1{
   int key;
   struct Node1 *left, *right;
};
// Utility function creates a new binary tree node with given key
Node1 * newNode1(int k){
   Node1 *temp = new Node1;
   temp->key = k;
   temp->left = temp->right = NULL;
   return temp;
}
// indicates log base 2 of x
int Log2(int x){
   int ans = 0 ;
   while (x>>=1) ans++;
      return ans ;
}
/* A recursive function is used to get the minimum value in a given range of array indexes. The following are parameters for this function.
st --> indicates pointer to segment tree
index --> indicates index of current node in the segment tree.
Initially 0 is passed as root is always at index 0
ss & se --> indicate starting and ending indexes of the segment
represented by current node, i.e., st[index]
qs & qe --> indicate starting and ending indexes of query range
*/
int RMQUtil(int index1, int ss1, int se1, int qs1, int qe1, int *st1){
      // It has been seen that if segment of this node is a part of given range, then return the min of the segment
      if (qs1 <= ss1 && qe1 >= se1)
         return st1[index1];
         //It has been seen that if segment of this node is outside the given range
      else if (se1 < qs1 || ss1 > qe1)
         return -1;
      // It has been seen that if a part of this segment overlaps with the given range
      int mid = (ss1 + se1)/2;
      int q1 = RMQUtil(2*index1+1, ss1, mid, qs1, qe1, st1);
      int q2 = RMQUtil(2*index1+2, mid+1, se1, qs1, qe1, st1);
      if (q1==-1) return q2;
      else if (q2==-1) return q1;
      return (level1[q1] < level1[q2]) ? q1 : q2;
   }
   // Return minimum of elements in range from index qs (query start) to
   // qe (query end). It mainly uses RMQUtil()
   int RMQ(int *st1, int n, int qs1, int qe1){
      // Check for erroneous input values
      if (qs1 < 0 || qe1 > n-1 || qs1 > qe1){
         printf("Invalid Input");
         return -1;
      }
      return RMQUtil(0, 0, n-1, qs1, qe1, st1);
   }
   // Now a recursive function that constructs Segment Tree for
   array[ss1..se1]. // si1 is index of current node in segment tree st
   void constructSTUtil(int si1, int ss1, int se1, int arr1[], int *st1){
      // When there will be only one element in array, store it in current node of
      // segment tree and return
      if (ss1 == se1)st1[si1] = ss1;
      else{
         // It has been seen that if there are more than one
         elements, then recur for left and right subtrees and store the
         minimum of two values in this node
         int mid1 = (ss1 + se1)/2;
         constructSTUtil(si1*2+1, ss1, mid1, arr1, st1);
         constructSTUtil(si1*2+2, mid1+1, se1, arr1, st1);
         if (arr1[st1[2*si1+1]] < arr1[st1[2*si1+2]])
            st1[si1] = st1[2*si1+1];
         else
            st1[si1] = st1[2*si1+2];
      }
   }
   /* Now this function is used to construct segment tree from given
   array. This function allocates memory for segment tree and calls
      constructSTUtil() to fill the allocated memory */
      int *constructST(int arr1[], int n){
         // Allocating memory for segment tree
         //Indicates height of segment tree
         int x = Log2(n)+1;
         // Indicates maximum size of segment tree
         int max_size = 2*(1<<x) - 1; // 2*pow(2,x) -1
         int *st1 = new int[max_size];
         // Indicates filling the allocated memory st1
         constructSTUtil(0, 0, n-1, arr1, st1);
         // Returning the constructed segment tree
         return st1;
      }
   // Indicates recursive version of the Euler tour of T
   void eulerTour(Node1 *root, int l){
      /* if the passed node exists */
      if (root){
         euler1[ind] = root->key; // inserting in euler array
         level1[ind] = l; // inserting l in level array
         ind++; // indicates increment index
         /* It has been seen that if unvisited, mark first occurrence*/
         if (firstOccurrence1[root->key] == -1)
         firstOccurrence1[root->key] = ind-1;
         /* touring left subtree if exists, and remark euler
         and level arrays for parent on return */
         if (root->left){
            eulerTour(root->left, l+1);
            euler1[ind]=root->key;
            level1[ind] = l;
            ind++;
         }
         /* touring right subtree if exists, and remark euler
         and level arrays for parent on return */
         if (root->right) {
            eulerTour(root->right, l+1);
            euler1[ind]=root->key;
            level1[ind] = l;
            ind++;
         }
      }
   }
   // Returning LCA of nodes n1, n2 (assuming they are
   // present in the tree)
   int findLCA(Node1 *root, int u1, int v1){
      /* Marking all nodes unvisited. Note that the size of
      firstOccurrence is 1 as node values which vary from
      1 to 9 are used as indexes */
      memset(firstOccurrence1, -1, sizeof(int)*(V+1));
      /* To start filling euler and level arrays from index 0 */
      ind = 0;
      /* Starting Euler tour with root node on level 0 */
      eulerTour(root, 0);
      /* constructing segment tree on level array */
      int *st1 = constructST(level1, 2*V-1);
      /*It has been seen that if v before u in Euler tour. For RMQ to
      work, first parameter 'u1' must be smaller than second 'v1' */
      if (firstOccurrence1[u1]>firstOccurrence1[v1])
      std::swap(u1, v1);
      // Indicates starting and ending indexes of query range
      int qs1 = firstOccurrence1[u1];
      int qe1 = firstOccurrence1[v1];
      // Indicates query for index of LCA in tour
      int index1 = RMQ(st1, 2*V-1, qs1, qe1);
      /* returning LCA node */
      return euler1[index1];
   }
   // Driver program to test above functions
   int main(){
      // Let us create the Binary Tree as shown in the diagram.
      Node1 * root = newNode1(1);
      root->left = newNode1(2);
      root->right = newNode1(3);
      root->left->left = newNode1(4);
      root->left->right = newNode1(5);
      root->right->left = newNode1(6);
      root->right->right = newNode1(7);
      root->left->right->left = newNode1(8);
      root->left->right->right = newNode1(9);
      int u1 = 4, v1 = 9;
      printf("The LCA of node %d and node %d is node %d.\n",
      u1, v1, findLCA(root, u1, v1));
      return 0;
}

आउटपुट

The LCA of node 4 and node 9 is node 2.

  1. C++ में एक बाइनरी ट्री में रूट से दिए गए नोड की दूरी ज्ञात करें

    मान लें कि हमारे पास कुछ नोड्स के साथ एक बाइनरी ट्री है। हमें रूट और दूसरे नोड u के बीच की दूरी का पता लगाना है। मान लीजिए पेड़ नीचे जैसा है: अब बीच की दूरी (रूट, 6) =2, पथ की लंबाई 2, के बीच की दूरी (रूट, 8) =3 आदि। इस समस्या को हल करने के लिए, हम बाएँ और दाएँ सबट्री में नोड को खोजने के लिए एक

  1. C++ में बाइनरी ट्री के लंबवत क्रम ट्रैवर्सल में kth नोड खोजें

    मान लीजिए कि हमारे पास एक बाइनरी ट्री और एक मान K है। कार्य Kth नोड को वर्टिकल ऑर्डर ट्रैवर्सल में प्रिंट करना है। यदि ऐसा कोई नोड मौजूद नहीं है, तो -1 लौटाएं। तो अगर पेड़ नीचे जैसा है - लंबवत क्रम ट्रैवर्सल इस प्रकार है - 4 2 1 5 6 3 8 7 9 तो अगर K =3 है, तो परिणाम 1 होगा। दृष्टिकोण सरल है। हम

  1. C++ में बाइनरी ट्री में अधिकतम लम्बवत योग ज्ञात कीजिए

    मान लीजिए कि हमारे पास एक बाइनरी ट्री है। कार्य ऊर्ध्वाधर क्रम ट्रैवर्सल में सभी नोड्स के अधिकतम योग को प्रिंट करना है। तो अगर पेड़ नीचे जैसा है - लंबवत क्रम ट्रैवर्सल इस प्रकार है - 4 2 1 + 5 + 6 = 12 3 + 8 = 11 7 9 यहां अधिकतम 12 है। दृष्टिकोण सरल है। हम वर्टिकल ऑर्डर ट्रैवर्सल करेंगे, फिर योग