Берілген жиым екілік іздеу ағашының алдын-ала өтуін білдіре алатынын тексеріңіз


Күрделілік дәрежесі оңай
Жиі кіреді Adobe Amazon LinkedIn
Екілік іздеу ағашы үйме ағаш

«Берілген массивтің екілік іздеу ағашының алдын-ала өтуін білдіре алатынын тексеру» мәселесі сізге алдын-ала өту жүйелі. Енді осы реттілікті қарастырып, осы тізбектің екілік іздеу ағашын көрсете алатынын немесе көрсете алмайтынын біліңіз Шешімнің күтілетін уақыт күрделілігі O (1).

мысал

Берілген жиым екілік іздеу ағашының алдын-ала өтуін білдіре алатынын тексеріңіз

5 3 4 7 6 9 8 11
Yes

Алдын-ала тапсырыс беру кезегі BST-ті көрсететіндігін тексеру әдісі

Мәселе бізден берілген массивтің алдын-ала өту траекториясын көрсете алатынын тексеруді сұрайды екілік іздеу ағашы. Бізге ан бүтін сан массив кіріс ретінде. Енді бұл массивтің а бар екенін ескеріңіз алдын-ала өту екілік іздеу ағашының реттілігі. Осыдан кейін берілген алдын-ала өтпелі тізбектің екілік іздеу ағашын көрсете алатынын немесе көрсете алмайтындығын тексеріңіз.

Аңғалдық тәсілі - алдымен оның оң жағындағы ағымдағы элементтен гөрі үлкен элементті табу. Енді оның оң жағындағы барлық элементтер таңдалған ток элементінен үлкен екенін тексеріңіз. Үлкен элементтің және таңдалған ток элементінің сол жағындағы барлық элементтер одан кіші. Содан кейін ағымдағы элементтен үлкен элементтен кіші элементке сол жақ ішкі массивтің бірдей шартын рекурсивті түрде тексеріңіз. Сонымен қатар рекурсивті ішкі массивтің үлкен элементтен соңына дейін болуын тексеріңіз. Бұл тәсіл тиімді емес, өйткені бұл 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 алдын-ала өтпелі жолын көрсете алатынын тексеретін Java коды

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

Күрделілікті талдау

Уақыттың күрделілігі

O (N), өйткені біз берілген кіріс массивіндегі барлық индекстерден өттік. Осылайша уақыттың күрделілігі сызықтық болып табылады.

Ғарыштың күрделілігі

O (N), өйткені біз стек қолдандық. Осылайша, ең нашар жағдайда біз барлық түйіндерді сақтай аламыз.