የተሰጠ ድርድር የሁለትዮሽ ፍለጋ ዛፍ ቅድመ-መሻገሪያን ሊወክል የሚችል መሆኑን ያረጋግጡ  


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe አማዞን LinkedIn
የሁለትዮሽ ፍለጋ ዛፍ ክምር ዛፍ

ችግሩ “የተሰጠው ድርድር የሁለትዮሽ ፍለጋ ዛፍ ቅድመ-መሻገርን ሊወክል ይችል እንደሆነ ይፈትሹ” ይላል መተላለፍን ቀድመው ቅደም ተከተል. አሁን ይህንን ቅደም ተከተል አስቡ እና ይህ ቅደም ተከተል የሁለትዮሽ ፍለጋ ዛፍን መወከል ይችል እንደሆነ ይወቁ ወይም አይፈልጉ? ለመፍትሔው የሚጠበቀው የጊዜ ውስብስብነት ነው ኦ (1).

ለምሳሌ  

የተሰጠ ድርድር የሁለትዮሽ ፍለጋ ዛፍ ቅድመ-መሻገሪያን ሊወክል የሚችል መሆኑን ያረጋግጡጭንቅላታም መያያዣ መርፌ

5 3 4 7 6 9 8 11
Yes

የቅድመ-ቅደም ተከተል ቅደም ተከተል BST ን የሚወክል ስለመሆኑ ለመቅረብ አቀራረብ  

ችግሩ አንድ የተሰጠ ድርድር የ “Preorder Traversal” ን ሊወክል ይችል እንደሆነ እንድንመረምር ይጠይቃል የሁለትዮሽ ፍለጋ ዛፍ. ተሰጠን ኢንቲጀር ደርድር እንደ ግብዓት. አሁን ይህ ድርድር ሀ መተላለፍን ቀድመው የሁለትዮሽ ፍለጋ ዛፍ ቅደም ተከተል። ከዚያ የተሰጠው ቅድመ-ቅደም ተከተል መተላለፍ ቅደም ተከተል የሁለትዮሽ ፍለጋ ዛፍ እንኳን ሊወክል ይችላል ወይም አይወክል ያረጋግጡ።

የዋህነት አቀራረብ በመጀመሪያ በቀኝ በኩል ካለው የአሁኑን ንጥረ ነገር የበለጠ የላቀውን ንጥረ ነገር መጀመሪያ መፈለግ ነው። አሁን በእሱ በስተቀኝ ያሉት ሁሉም ንጥረ ነገሮች ከተመረጠው የአሁኑ አካል የበለጠ መሆናቸውን ያረጋግጡ። እና በትልቁ አካል እና በተመረጠው የአሁኑ አካል ግራ ያሉት ሁሉም ንጥረ ነገሮች ከእሱ ያነሱ ናቸው። ከዚያ ለግራ ንዑስ ንዑስ ክፍል ከአሁኑ ኤለመንት እስከ ትክክለኛው ትልቁ ንጥረ ነገር በታች ወደሆነ አካል ተመሳሳይ ሁኔታን እንደገና ይፈትሹ። እናም በተከታታይ ከከፍተኛው እስከ መጨረሻው ንዑስ ስርአቱን ይፈትሹ ፡፡ ይህ አቀራረብ ውጤታማ አይደለም ምክንያቱም ይህ የ O (N ^ 2) የጊዜ ውስብስብነትን ይጠይቃል።

ተመልከት
ከፍተኛው የሁለትዮሽ ዛፍ

መስመራዊ በሆነ ጊዜ ችግሩን ለመፍታት ፡፡ እኛ ማግኘት አለብን ቀጣይ ትልቁ ንጥረ ነገር ቁልል በመጠቀም. ስለዚህ መጀመሪያ የመስቀለኛ እሴቶችን የሚያከማች ቁልል ይፍጠሩ ፡፡ ከዚያ ሥሩን እንደ አነስተኛ ኢንቲጀር እሴት ያስጀምሩ። ከዚያ በተሰጠው የግብዓት ድርድር ይጀምሩ። ከተደራራቢው አናት የሚበልጥ ንጥረ ነገር ላይ የምንሮጥ ከሆነ ፡፡ ከዚያም አሁን ካለው ንጥረ ነገር የሚበልጥ ከሆነ ወይም ቁልል ባዶ ሆኖ እስከሚገኝ ድረስ ቁልል እስከሚሞላ ድረስ አባላቱን ማስወገድዎን ይቀጥሉ። ከሥሩ ያነሰ የመስቀለኛ እሴት ካጋጠምዎት የቅድመ-መሻገሪያው ትክክለኛ አይደለም። በመጨረሻ እነዚህን ሁኔታዎች ስናልፍ ፡፡ የአሁኑን ንጥረ ነገር ወደ ቁልል ውስጥ እንገፋለን ፡፡

ኮድ  

አንድ የተሰጠው ድርድር የ BST ን መሻገሪያ ማወዳደር ይችል እንደሆነ ለመፈተሽ የ C ++ ኮድ

#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

አንድ የተሰጠው ድርድር የ BST ን መሻገሪያ ቀድሞ ማወቀር ይችል እንደሆነ ለመፈተሽ የጃቫ ኮድ

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

ውስብስብነት ትንተና  

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ በተጠቀሰው የግብዓት ድርድር ውስጥ ያሉትን ሁሉንም ኢንዴክሶች ስለ ተሻገርን ፡፡ ስለዚህ የጊዜ ውስብስብነት መስመራዊ ነው።

ተመልከት
በሁለትዮሽ ዛፍ ውስጥ ከፍተኛውን የደረጃ ድምርን ያግኙ

የቦታ ውስብስብነት

ኦ (ኤን) ፣ እኛ ቁልል ስለተጠቀምን ፡፡ ስለዚህ በጣም በከፋ ሁኔታ ውስጥ ሁሉንም አንጓዎች ማከማቸት እንችላለን ፡፡