जांचें कि क्या दिए गए सरणी बाइनरी सर्च ट्री के लेवल ऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकते हैं


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना Citrix आईबीएम वास्तव में जानकारी एज ओयो कमरे Teradata
बाइनरी सर्च ट्री बाइनरी ट्री पंक्ति पेड़ वृक्ष का त्राटक

समस्या का विवरण

समस्या "जाँच करें कि क्या दी गई सरणी बाइनरी सर्च ट्री के लेवल ऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकती है" बताती है कि आपको एक लेवल ऑर्डर ट्रैसल ऑफ दिया गया है बाइनरी सर्च ट्री। और का उपयोग कर स्तर का आदेश पेड़ का। हमें कुशलतापूर्वक यह पता लगाने की आवश्यकता है कि क्या स्तर क्रम ट्रावेल एक बाइनरी सर्च ट्री का प्रतिनिधित्व कर सकता है या नहीं?

उदाहरण

Level Order Traversal - {5 2 7 1 6 9 }
True

 

जांचें कि क्या दिए गए सरणी बाइनरी सर्च ट्री के लेवल ऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकते हैं

व्याख्या

दिए गए स्तर के ऑर्डर ट्रैवर्सल बाइनरी ट्री का प्रतिनिधित्व करते हैं जो छवि में दिखाया गया है। और जैसा कि हम देख सकते हैं कि पेड़ एक द्विआधारी पेड़ के सभी गुणों को संतुष्ट करता है और इस प्रकार उत्पादन सच है।

यह देखने के लिए कि क्या दी गई सरणी बाइनरी सर्च ट्री के लेवल ऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकती है

Naive दृष्टिकोण

यदि हम सभी बाइनरी पेड़ों को बनाने की कोशिश करते हैं, तो एक भोली दृष्टिकोण हो सकता है जो दिए गए स्तर के आदेश को पूरा करते हैं। और फिर जांचें कि क्या पेड़ एक द्विआधारी खोज पेड़ का प्रतिनिधित्व करता है। लेकिन यह ऑपरेशन बहुत महंगा होगा। सबसे पहले, हम कई पेड़ों का निर्माण करेंगे। फिर एल्गोरिथ्म को जांचना आवश्यक है कि क्या पेड़ का गठन BST है। इसलिए, हमें कुछ ऐसा करने की ज़रूरत है जहाँ हमें पेड़ बनाने की ज़रूरत न हो।

कुशल दृष्टिकोण

एक कुशल दृष्टिकोण स्तर के क्रम में होने वाले तत्वों में से प्रत्येक के लिए सीमाओं को संग्रहीत करेगा। ये सीमाएं उस सीमा का प्रतिनिधित्व करती हैं जिसमें उनके उप-तत्व तत्व झूठ बोल सकते हैं। यदि हम एक नोड के बारे में बात करते हैं, तो यह एक न्यूनतम और अधिकतम होगा। बाएं सबट्री में न्यूनतम नोड से लेकर वर्तमान नोड मान -1 तक के तत्व हो सकते हैं। जबकि सही सबट्री में तत्व वर्तमान नोड मान + 1 से अधिकतम सीमा तक हो सकते हैं।

इसलिए, हम एक कतार का उपयोग करेंगे जहां हम इन सीमाओं के साथ तत्वों को सम्मिलित करते रहेंगे और यदि हम सभी नोड्स के माध्यम से पार करने में सक्षम हैं। हम कहते हैं कि दिए गए स्तर के आदेश ट्रैवर्सल एक बीएसटी का प्रतिनिधित्व कर सकते हैं और नहीं। एल्गोरिथ्म बहुत हद तक जाँच के समान है कि क्या एक बाइनरी पेड़ एक BST है या नहीं?

कोड

C ++ कोड यह जांचने के लिए कि दिया गया सरणी बाइनरी सर्च ट्री के लेवल ऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकता है या नहीं

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    int mn;
    int mx;
};

node create(int data, int mn, int mx){
    node tmp;
    tmp.data = data;
    tmp.mn = mn;
    tmp.mx = mx;
    return tmp;
}

bool checkLevelOrderTraversalRepresentBinarySearchTree(vector<int> traversal){
    queue<node> q;
    int i = 0, n = traversal.size();
    q.push(create(traversal[i++], INT_MIN, INT_MAX));

    while(!q.empty()){
        node now = q.front();
        q.pop();
        if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
            q.push(create(traversal[i++], now.mn, now.data));
        if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
            q.push(create(traversal[i++], now.data, now.mx));
    }
    return (i == n);
}

int main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        vector<int> traversal(n);
        for(int i=0;i<n;i++)
            cin>>traversal[i];
        cout<<(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no")<<endl;
    }
}
1
6
5 2 7 1 6 9
true

जावा कोड यह जांचने के लिए कि क्या दिए गए सरणी बाइनरी सर्च ट्री के लेवल ऑर्डर ट्रैवर्सल का प्रतिनिधित्व कर सकते हैं

import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int mn;
  int mx;
}

class Main{
  
  static node create(int data, int mn, int mx){
      node tmp = new node();
      tmp.data = data;
      tmp.mn = mn;
      tmp.mx = mx;
      return tmp;
  }
  
  static boolean checkLevelOrderTraversalRepresentBinarySearchTree(int traversal[]){
      Queue<node> q = new LinkedList<node>();
      int i = 0; int n = traversal.length;
      q.add(create(traversal[i++], Integer.MIN_VALUE, Integer.MAX_VALUE));
  
      while(q.size() > 0){
          node now = q.peek();
          q.remove();
          if(i<n && now.mn<traversal[i] && traversal[i]<now.data)
              q.add(create(traversal[i++], now.mn, now.data));
          if(i<n && now.data<traversal[i] && traversal[i]<now.mx)
              q.add(create(traversal[i++], now.data, now.mx));
      }
      return (i == n);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int t = sc.nextInt();
      while(t-- > 0){
          int n = sc.nextInt();
          int[] traversal = new int[n];
          for(int i=0;i<n;i++)
              traversal[i] = sc.nextInt();
          System.out.println(checkLevelOrderTraversalRepresentBinarySearchTree(traversal) ? "true" : "no");
      }
  }
}
1
6
5 2 7 1 6 9
true

जटिलता विश्लेषण

समय जटिलता

जैसा कि हमने तत्वों के बारे में आसानी से पता लगाया है। और सबसे खराब स्थिति में, हमें सभी तत्वों को पार करने की आवश्यकता है, एल्गोरिथ्म में रैखिक समय की जटिलता है पर)।

अंतरिक्ष जटिलता

हमने उन तत्वों को संग्रहीत करने के लिए एक कतार का उपयोग किया है जो एल्गोरिथ्म को रैखिक स्थान की जटिलता के लिए बनाते हैं पर).