दिलेला अ‍ॅरे बायनरी शोध वृक्षाच्या प्रीऑर्डर ट्रॅव्हर्सलचे प्रतिनिधित्व करू शकतो की नाही ते तपासा


अडचण पातळी सोपे
वारंवार विचारले अडोब ऍमेझॉन संलग्न
बायनरी शोध वृक्ष स्टॅक झाड

समस्या "दिलेली अ‍ॅरे बायनरी सर्च ट्रीच्या प्रीऑर्डर ट्रॅव्हर्सलचे प्रतिनिधित्व करू शकते की नाही ते तपासा" आपल्याला असे देण्यात आले आहे प्रीऑर्डर ट्रॅव्हर्सल क्रम. आता या अनुक्रमाचा विचार करा आणि शोधा की हा क्रम बायनरी शोध वृक्षांचे प्रतिनिधित्व करू शकतो की नाही? समाधानासाठी अपेक्षित वेळ जटिलता आहे ओ (1).

उदाहरण

दिलेला अ‍ॅरे बायनरी शोध वृक्षाच्या प्रीऑर्डर ट्रॅव्हर्सलचे प्रतिनिधित्व करू शकतो की नाही ते तपासा

5 3 4 7 6 9 8 11
Yes

प्रीऑर्डर सीक्वेन्स बीएसटीचे प्रतिनिधित्व करतो का ते तपासण्यासाठीचा दृष्टीकोन

समस्या आम्हाला दिलेली अ‍ॅरे प्रीऑर्डर ट्रॅव्हर्सलचे प्रतिनिधित्व करू शकते की नाही हे तपासायला सांगते बायनरी शोध वृक्ष. आम्हाला एक दिले जाते पूर्णांक अॅरे इनपुट म्हणून आता विचार करा की या अ‍ॅरेकडे एक आहे प्रीऑर्डर ट्रॅव्हर्सल बायनरी शोध वृक्षाचा क्रम. नंतर दिलेले प्रीऑर्डर ट्रॅव्हर्सल सीक्वेन्स बायनरी सर्च ट्रीचे प्रतिनिधित्व करू शकतात की नाही ते तपासा.

एक भोळसट दृष्टिकोन म्हणजे त्यातील उजवीकडे असलेल्या विद्यमान घटकापेक्षा सर्वात मोठा घटक शोधणे. आता उजवीकडे असलेले सर्व घटक निवडलेल्या वर्तमान घटकापेक्षा मोठे आहेत का ते तपासा. आणि मोठ्या घटकाच्या डावीकडील सर्व घटक आणि निवडलेला वर्तमान घटक त्यापेक्षा लहान असतो. नंतर चालू घटकापासून डाव्या सब सब्रेसाठी समान स्थिती फक्त मोठ्या घटकापेक्षा कमी घटकाकडे निरंतरपणे तपासा. आणि देखील वारंवार फक्त मोठ्या घटकापासून शेवटपर्यंत सबर्रे पहा. हा दृष्टिकोन कार्यक्षम नाही कारण यासाठी ओ (एन ^ 2) वेळ जटिलता आवश्यक आहे.

रेखीय वेळेत समस्या सोडविण्यासाठी. आम्ही शोधण्यासाठी लागेल स्टॅक वापरुन पुढील मोठे घटक. प्रथम नोड मूल्ये संचयित करणारे एक स्टॅक तयार करा. नंतर रूटला किमान पूर्णांक मूल्य म्हणून प्रारंभ करा. नंतर दिलेल्या इनपुट अ‍ॅरेसह प्रारंभ करा. जर आपण स्टॅकच्या तुलनेत मोठ्या असलेल्या एखाद्या घटकावर धाव घेतली तर. नंतर विद्यमान घटकापेक्षा स्टॅक किंवा स्टॅक रिक्त होत नाही तोपर्यंत स्टॅक टॉप होईपर्यंत घटक काढून टाकत रहा. जर आपण रूटपेक्षा लहान असलेल्या नोड मूल्यावर आला तर प्रीऑर्डर ट्रॅव्हर्सल योग्य नाही. शेवटी जेव्हा आपण या अटी पार करतो. आम्ही वर्तमान घटक स्टॅकमध्ये ढकलतो.

कोड

दिलेला अ‍ॅरे बीएसटीच्या प्रीऑर्डर ट्रव्हर्सलचे प्रतिनिधित्व करू शकतो की नाही हे तपासण्यासाठी सी ++ कोड

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

bool preorderBST(int input[], int n)
{
    stack<int> s;
    int root = INT_MIN;
    for(int i=0;i<n;i++)
    {
        // if current node is smaller than the root
        // the current node lies on the right of root
        // thus it is impossible for bst
        if (input[i] < root)
            return false;
        // keep removing elements smaller than the root
        // until you find an element which is greater than the root
        while(!s.empty() && s.top()<input[i])
            root = s.top(), s.pop();
        // if current element is smaller than the root
        // push it into stack
        s.push(input[i]);
    }
    // if we passed until the end of the array
    // that means that the given preorder sequence represents a valid BST
    return true;
}

int main()
{
    int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
    int n = (sizeof input)/(sizeof input[0]);

    cout<<((preorderBST(input, n)) ? "yes" : "no");
}
yes

दिलेला अ‍ॅरे बीएसटीच्या प्रीऑर्डर ट्रॅव्हर्सलचे प्रतिनिधित्व करू शकतो की नाही हे तपासण्यासाठी जावा कोड

import java.util.*;

class Main{
  static boolean preorderBST(int input[], int n)
  {
      Stack<Integer> s = new Stack<Integer>();
      int root = Integer.MIN_VALUE;
      for(int i=0;i<n;i++)
      {
          // if current node is smaller than the root
          // the current node lies on the right of root
          // thus it is impossible for bst
          if (input[i] < root)
              return false;
          // keep removing elements smaller than the root
          // until you find an element which is greater than the root
          while(!s.empty() && s.peek()<input[i]){
              root = s.peek();
              s.pop();
          }
          // if current element is smaller than the root
          // push it into stack
          s.push(input[i]);
      }
      // if we passed until the end of the array
      // that means that the given preorder sequence represents a valid BST
      return true;
  }

  public static void main(String[] args)
  {
      int input[] = {5, 3, 4, 7, 6, 9, 8, 11};
      int n = input.length;

      System.out.print((preorderBST(input, n)) ? "yes" : "no");
  }
}
yes

गुंतागुंत विश्लेषण

वेळ कॉम्प्लेक्सिटी

ओ (एन), आम्ही दिलेल्या इनपुट अ‍ॅरेमधील सर्व निर्देशांकाकडे दुर्लक्ष केले आहे. अशा प्रकारे वेळेची जटिलता रेषात्मक असते.

स्पेस कॉम्प्लेक्सिटी

ओ (एन), कारण आम्ही स्टॅक वापरला आहे. अशा प्रकारे सर्वात वाईट परिस्थितीत आपण सर्व नोड्स संचयित करू शकतो.