تحقق مما إذا كان بإمكان المصفوفة المحددة تمثيل اجتياز ترتيب المستوى لشجرة البحث الثنائية


مستوى الصعوبة سهل
كثيرا ما يطلب في أمازون سيتريكس IBM في الواقع حافة المعلومات غرف OYO مقاومه
شجرة البحث الثنائية شجرة ثنائية طابور شجرة اجتياز الشجرة

المشكلة بيان

تشير مشكلة "التحقق مما إذا كان المصفوفة المعينة يمكن أن تمثل اجتياز ترتيب المستوى لشجرة البحث الثنائي" إلى أنه قد تم منحك اجتياز ترتيب مستوى شجرة البحث الثنائية. وباستخدام ملف اجتياز ترتيب المستوى من الشجرة. نحن بحاجة إلى العثور بكفاءة على ما إذا كان اجتياز ترتيب المستوى يمكن أن يمثل شجرة بحث ثنائية أم لا؟

مثال

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

كود Java للتحقق مما إذا كانت المصفوفة المحددة يمكن أن تمثل اجتياز ترتيب المستوى لشجرة البحث الثنائية

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

تحليل التعقيد

تعقيد الوقت

كما اجتزنا العناصر ببساطة. وفي أسوأ الحالات ، نحتاج إلى اجتياز جميع العناصر ، فالخوارزمية لها تعقيد زمني خطي على).

تعقيد الفضاء

لقد استخدمنا قائمة انتظار لتخزين العناصر التي جعلت الخوارزمية لها تعقيد مساحة خطي على).