შეამოწმეთ, მოცემული მასივი წარმოადგენს თუ არა ორობითი ძიების ხის დონის ორდერის გადაკვეთას


Რთული ტური Easy
ხშირად ეკითხებიან Amazon Citrix IBM ნამდვილად ინფო ზღვარი OYO ოთახები Teradata
ორობითი ძებნა ხე ორობითი ხე Queue ხე ხის გადაკვეთა

პრობლემის განცხადება

პრობლემა "შეამოწმეთ, მოცემული მასივი წარმოადგენს თუ არა ორობითი საძიებო ხის დონის შეკვეთის გადაკვეთას" აცხადებს, რომ თქვენ მოცემულია დონის შეკვეთის გადაკვეთა ორობითი ძებნის ხე. და გამოყენებით დონის შეკვეთის გადაკვეთა ხის. ჩვენ ეფექტურად უნდა დავადგინოთ, დონის წესრიგის გადაკვეთა წარმოადგენს თუ არა ორობითი ძიების ხეს?

მაგალითი

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

 

შეამოწმეთ, მოცემული მასივი წარმოადგენს თუ არა ორობითი ძიების ხის დონის ორდერის გადაკვეთას

განმარტება

მოცემული დონის ორდერის გადაკვეთა წარმოადგენს ორობითი ხეს, რომელიც ნაჩვენებია სურათზე. როგორც ვხედავთ, ხე აკმაყოფილებს ორობითი ხის ყველა თვისებას და, შესაბამისად, გამომავალი არის ჭეშმარიტი.

მიდგომა იმის შემოწმებისთვის, მოცემული მასივი წარმოადგენს თუ არა ორობითი ძიების ხის დონის ორდერის გადაკვეთას

გულუბრყვილო მიდგომა

გულუბრყვილო მიდგომა შეიძლება იყოს, თუ ჩვენ ვცდილობთ გავაკეთოთ ყველა ორობითი ხე, რომელიც აკმაყოფილებს მოცემული დონის წესრიგის გადაკვეთას. შემდეგ შეამოწმეთ, წარმოადგენს თუ არა ხე ორობითი ძიების ხეს. მაგრამ ეს ოპერაცია ძალიან ძვირი ჯდება. უპირველეს ყოვლისა, ჩვენ ვაშენებთ ბევრ ხეს. შემდეგ ალგორითმი მოითხოვს შემოწმებას, ჩამოყალიბებული ხე არის BST. ასე რომ, ჩვენ ისეთი რამ უნდა გავაკეთოთ, სადაც არ დაგვჭირდება ხის აგება.

ეფექტური მიდგომა

ეფექტური მიდგომა შეინახავს საზღვრებს დონის წესრიგის გადაკვეთისას წარმოქმნილი თითოეული ელემენტისთვის. ეს საზღვრები წარმოადგენს საზღვარს, რომელშიც მათი ქვეტყის ელემენტები შეიძლება იყოს მოთავსებული. თუ კვანძზე ვისაუბრებთ, მას მინიმალური და მაქსიმალური ექნება. მარცხენა ქვეძეს შეიძლება ჰქონდეს ელემენტები დაწყებული მინიმალურიდან მიმდინარე კვანძის მნიშვნელობამდე - 1. მართალია, მარჯვენა ქვეჯგუფის ელემენტები შეიძლება იყოს მიმდინარე კვანძის მნიშვნელობიდან + 1 მაქსიმალური შეკრულიდან.

ასე რომ, ჩვენ გამოვიყენებთ რიგს, სადაც გავაგრძელებთ ამ საზღვრების ელემენტების ჩასმას და თუ ყველა კვანძის გავლა შეგვიძლია. ჩვენ ვამბობთ, რომ მოცემული დონის წესრიგის გადაკვეთა შეიძლება წარმოადგენს BST- ს, არა. ალგორითმი ძალიან ჰგავს იმის შემოწმებას, არის თუ არა ორობითი ხე 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

სირთულის ანალიზი

დროის სირთულე

როგორც ჩვენ უბრალოდ გადავკვეთეთ ელემენტებს. და უარეს შემთხვევაში, ჩვენ უნდა გადავკვეთოთ ყველა ელემენტი, ალგორითმს აქვს წრფივი დროის სირთულე O (N)

სივრცის სირთულე

ჩვენ გამოვიყენეთ რიგი ელემენტების შესანახად, რამაც ალგორითმს წრფივი სივრცის სირთულე შესძინა O (N).