بررسی کنید که آیا آرایه داده شده می تواند نمایانگر سطح مرتبه از درخت جستجوی دودویی باشد


سطح دشواری ساده
اغلب در آمازون خودتان هستید؟ آی بی ام در واقع Edge Edge اتاق های OYO داده Teradata
درخت جستجوی دودویی درخت باینری صف درخت عبور از درخت

بیان مسأله

مسئله "بررسی کنید که آیا آرایه داده شده می تواند نمایانگر سطح مرتبه از درخت جستجوی دودویی باشد" بیان می کند که به شما یک ترتیب سطح مرتب داده می شود درخت جستجوی دودویی. و با استفاده از پیمایش سفارش سطح از درخت ما باید به طور کارآمد دریابیم که آیا پیمایش مرتبه سطح می تواند یک درخت جستجوی دودویی باشد یا خیر؟

مثال

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

 

بررسی کنید که آیا آرایه داده شده می تواند نمایانگر سطح مرتبه از درخت جستجوی دودویی باشد

توضیح

جدول عبور از سطح داده شده درخت باینری را نشان می دهد که در تصویر نشان داده شده است. و همانطور که می بینیم درخت تمام خصوصیات یک درخت باینری را برآورده می کند و بنابراین خروجی درست است.

رویکرد بررسی اینکه آیا آرایه داده شده می تواند نمایانگر سطح مرتبه درخت جستجوی دودویی باشد

رویکرد ساده لوحانه

یک رویکرد ساده لوحانه می تواند این باشد که اگر بخواهیم همه درختان دودویی را که از سطح نظم مطلوبی برخوردار هستند ، ایجاد کنیم. و سپس بررسی کنید که آیا درخت یک درخت جستجوی دودویی است. اما این عملیات بسیار پرهزینه خواهد بود. اول از همه ، ما درختان زیادی را خواهیم ساخت. سپس الگوریتم نیاز به بررسی اینکه درخت شکل گرفته BST است یا خیر. بنابراین ، در جایی که نیازی به ساخت درخت نداریم ، باید کاری انجام دهیم.

رویکرد کارآمد

یک رویکرد کارآمد مرزهای مربوط به هر یک از عناصر رخ داده در مسیر مرتب سازی را ذخیره می کند. این مرزها نشان دهنده مرزی است که عناصر زیر درخت آنها می توانند در آن نهفته باشند. اگر درباره گره صحبت کنیم ، حداقل و حداکثر خواهد داشت. subtree سمت چپ می تواند عناصر مختلفی از حداقل محدود به مقدار گره فعلی -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

تحلیل پیچیدگی

پیچیدگی زمان

همانطور که ما به سادگی عناصر را مرور کرده ایم. و در بدترین حالت ، ما باید تمام عناصر را رد کنیم ، الگوریتم دارای پیچیدگی زمانی خطی است بر).

پیچیدگی فضا

ما از یک صف برای ذخیره عناصری استفاده کرده ایم که باعث شده الگوریتم دارای پیچیدگی فضای خطی باشد بر).