چیک کریں کہ آیا دی گئی سرنی بائنری سرچ ٹری کے لیول آرڈر ٹراورسل کی نمائندگی کرسکتی ہے


مشکل سطح آرام سے
اکثر پوچھا جاتا ہے ایمیزون Citrix کی IBM بے شک انفارمیشن ایج OYO کمرے ٹیراداٹا
ثنائی تلاش درخت ثنائی درخت قطار درخت درخت ٹراورسال

مسئلہ یہ بیان

مسئلہ "چیک کریں کہ آیا دی گئی سرنی بائنری سرچ ٹری کے لیول آرڈر ٹراورسل کی نمائندگی کرسکتی ہے"۔ یہ بتاتا ہے کہ آپ کو لیول آرڈر ٹراورسال دیا گیا ہے بائنری تلاش درخت. اور استعمال کرتے ہوئے سطح کا آرڈر پار کرنا درخت کا ہمیں مؤثر طریقے سے تلاش کرنے کی ضرورت ہے کہ اگر سطح کا آرڈر ٹراورسال بائنری سرچ ٹریٹ کی نمائندگی کرسکتا ہے یا نہیں؟

مثال کے طور پر

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

 

چیک کریں کہ آیا دی گئی سرنی بائنری سرچ ٹری کے لیول آرڈر ٹراورسل کی نمائندگی کرسکتی ہے

وضاحت

دیئے گئے سطح کا آرڈر ٹروراسل بائنری ٹری کی نمائندگی کرتا ہے جو تصویر میں دکھایا گیا ہے۔ اور جیسا کہ ہم دیکھ سکتے ہیں کہ درخت بائنری درخت کی تمام خصوصیات کو پورا کرتا ہے اور اس طرح پیداوار صحیح ہے۔

جانچنے کے لach نقطہ نظر یہ ہے کہ آیا دیئے جانے والا صف بائنری سرچ ٹری کے لیول آرڈر ٹراورسل کی نمائندگی کرسکتا ہے

بولی اپروچ

ایک بولی نقطہ نظر ہوسکتا ہے اگر ہم بائنری کے تمام درختوں کو بنانے کی کوشش کریں جو دیئے گئے سطح کے آرڈر کو پورا کریں۔ اور پھر چیک کریں کہ آیا درخت بائنری تلاش کے درخت کی نمائندگی کرتا ہے۔ لیکن یہ آپریشن بہت مہنگا ہوگا۔ سب سے پہلے کی طرح ، ہم بہت سے درخت تعمیر کرینگے۔ پھر الگورتھم کی جانچ پڑتال کی ضرورت ہوتی ہے کہ آیا درخت تشکیل دی گئی بی ایس ٹی ہے۔ لہذا ، ہمیں کچھ کرنے کی ضرورت ہے جہاں ہمیں درخت تعمیر کرنے کی ضرورت نہیں ہے۔

موثر انداز

ایک موثر نقطہ نظر ، سطح کے آرڈر میں ہونے والے ہر ایک عنصر کی حدود کو محفوظ کرے گا۔ یہ حدود اس حد کی نمائندگی کرتی ہیں جس میں ان کے ذیلی مقام عناصر جھوٹ بول سکتے ہیں۔ اگر ہم نوڈ کے بارے میں بات کریں تو ، اس میں کم از کم اور زیادہ سے زیادہ ہوگا۔ بائیں سب ٹری میں موجودہ نوڈ ویلیو 1 سے کم سے کم حد تک عنصر ہوسکتے ہیں۔ جب کہ دائیں سب ٹری میں موجود عناصر موجودہ نوڈ ویلیو +1 سے لے کر زیادہ سے زیادہ حد تک ہوسکتے ہیں۔

لہذا ، ہم ایک قطار استعمال کریں گے جہاں ہم عناصر کو ان حدود کے ساتھ داخل کرتے رہیں گے اور اگر ہم تمام نوڈس کو عبور کرنے میں کامیاب ہوجائیں گے۔ ہم کہتے ہیں کہ دیئے گئے سطح کا آرڈر ٹروراسل ایک 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

جاوا کوڈ چیک کرنے کے ل the کہ آیا دیئے گئے صف میں بائنری سرچ ٹری کے لیول آرڈر ٹراورسل کی نمائندگی ہوسکتی ہے

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).