கொடுக்கப்பட்ட வரிசை பைனரி தேடல் மரத்தின் முன்கூட்டிய பயணத்தை குறிக்க முடியுமா என்பதை சரிபார்க்கவும்


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அடோப் அமேசான் லின்க்டு இன்
பைனரி தேடல் மரம் ஸ்டேக் மரம்

“கொடுக்கப்பட்ட வரிசைக்கு பைனரி தேடல் மரத்தின் முன்கூட்டிய பயணத்தை குறிக்க முடியுமா என்று சரிபார்க்கவும்” சிக்கல் உங்களுக்கு வழங்கப்பட்டுள்ளது preorder traversal வரிசை. இப்போது இந்த வரிசையை கருத்தில் கொண்டு, இந்த வரிசை ஒரு பைனரி தேடல் மரத்தை குறிக்க முடியுமா அல்லது கண்டுபிடிக்க முடியுமா? தீர்வுக்கான எதிர்பார்க்கப்படும் நேர சிக்கலானது ஓ (1).

உதாரணமாக

கொடுக்கப்பட்ட வரிசை பைனரி தேடல் மரத்தின் முன்கூட்டிய பயணத்தை குறிக்க முடியுமா என்பதை சரிபார்க்கவும்

5 3 4 7 6 9 8 11
Yes

முன்பதிவு வரிசை பிஎஸ்டியைக் குறிக்கிறதா என்பதைச் சரிபார்க்க அணுகுமுறை

கொடுக்கப்பட்ட வரிசைக்கு முன்கூட்டியே ஆர்டர் செய்ததைக் குறிக்க முடியுமா என்று சிக்கல் கேட்கிறது பைனரி தேடல் மரம். எங்களுக்கு ஒரு வழங்கப்படுகிறது முழு வரிசை உள்ளீடாக. இப்போது இந்த வரிசைக்கு ஒரு உள்ளது என்று கருதுங்கள் preorder traversal பைனரி தேடல் மரத்திற்கான வரிசை. கொடுக்கப்பட்ட முன்கூட்டியே ஆர்டர் டிராவர்சல் வரிசை ஒரு பைனரி தேடல் மரத்தை கூட குறிக்க முடியுமா இல்லையா என்பதை சரிபார்க்கவும்.

ஒரு அப்பாவி அணுகுமுறை என்னவென்றால், அதன் வலதுபுறத்தில் உள்ள தற்போதைய உறுப்பை விட மிகப் பெரிய உறுப்பைக் கண்டுபிடிப்பது. இப்போது அதன் வலதுபுறத்தில் உள்ள அனைத்து உறுப்புகளும் தேர்ந்தெடுக்கப்பட்ட தற்போதைய உறுப்பை விட அதிகமாக இருக்கிறதா என்று சோதிக்கவும். மேலும் பெரிய உறுப்பு மற்றும் தேர்ந்தெடுக்கப்பட்ட தற்போதைய உறுப்பு ஆகியவற்றின் இடதுபுறத்தில் உள்ள அனைத்து உறுப்புகளும் அதை விட சிறியவை. தற்போதைய உறுப்பிலிருந்து இடது உறுப்புக்கு அதே நிலையை மீண்டும் மீண்டும் சரிபார்க்கவும். மேலும் மீண்டும் மீண்டும் சப்ரேயை இன்னும் பெரிய உறுப்பு முதல் இறுதி வரை சரிபார்க்கவும். இந்த அணுகுமுறை திறமையாக இல்லை, ஏனெனில் இதற்கு O (N ^ 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

சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ஓ (என்), கொடுக்கப்பட்ட உள்ளீட்டு வரிசையில் உள்ள அனைத்து குறியீடுகளையும் கடந்து சென்றோம். இதனால் நேர சிக்கலானது நேரியல்.

விண்வெளி சிக்கலானது

ஓ (என்), ஏனெனில் நாங்கள் ஒரு அடுக்கைப் பயன்படுத்தினோம். இதனால் மிக மோசமான நிலையில், எல்லா முனைகளையும் சேமித்து வைக்கலாம்.