ตรวจสอบว่าอาร์เรย์ที่ระบุสามารถแสดงถึงการส่งผ่านของลำดับระดับของ Binary Search Tree หรือไม่  


ระดับความยาก สะดวกสบาย
ถามบ่อยใน อเมซอน ซิทริกซ์ ไอบีเอ็ม จริง ขอบข้อมูล ห้องโอโย Teradata
ต้นไม้ค้นหาแบบไบนารี ต้นไม้ไบนารี คิว ต้นไม้ ทรีทราเวอร์ซัล

คำชี้แจงปัญหา  

ปัญหา“ ตรวจสอบว่าอาร์เรย์ที่ระบุสามารถแสดงถึงการส่งผ่านของลำดับระดับของโครงสร้างการค้นหาแบบไบนารีได้หรือไม่” ระบุว่าคุณได้รับการส่งผ่านลำดับระดับ ต้นไม้ค้นหาไบนารี. และการใช้ การส่งผ่านคำสั่งระดับ ของต้นไม้ เราจำเป็นต้องค้นหาอย่างมีประสิทธิภาพว่าการส่งผ่านคำสั่งระดับสามารถแสดงถึงโครงสร้างการค้นหาแบบไบนารีได้หรือไม่?

ตัวอย่าง  

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

 

ตรวจสอบว่าอาร์เรย์ที่ระบุสามารถแสดงถึงการส่งผ่านของลำดับระดับของ Binary Search Tree หรือไม่หมุด

คำอธิบาย

การส่งผ่านลำดับระดับที่กำหนดแสดงถึงต้นไม้ไบนารีซึ่งแสดงในภาพ และในขณะที่เราเห็นว่าต้นไม้ตรงตามคุณสมบัติทั้งหมดของต้นไม้ไบนารีดังนั้นผลลัพธ์จึงเป็นจริง

วิธีการตรวจสอบว่าอาร์เรย์ที่กำหนดสามารถแสดงถึงการส่งผ่านของลำดับระดับของโครงสร้างการค้นหาแบบไบนารีได้หรือไม่  

แนวทางที่ไร้เดียงสา

วิธีการที่ไร้เดียงสาอาจเป็นได้ถ้าเราพยายามสร้างต้นไม้ไบนารีทั้งหมดที่ตอบสนองการข้ามผ่านคำสั่งระดับที่กำหนด จากนั้นตรวจสอบว่าต้นไม้นั้นแสดงถึงต้นไม้ค้นหาแบบไบนารีหรือไม่ แต่การดำเนินการนี้จะมีค่าใช้จ่ายสูงมาก ก่อนอื่นเราจะสร้างต้นไม้จำนวนมาก จากนั้นอัลกอริทึมต้องตรวจสอบว่าต้นไม้ที่สร้างขึ้นเป็น BST หรือไม่ ดังนั้นเราต้องทำอะไรบางอย่างโดยที่เราไม่จำเป็นต้องสร้างต้นไม้

ดูสิ่งนี้ด้วย
ลบโหนด Nth จากส่วนท้ายของรายการที่เชื่อมโยงที่กำหนด

แนวทางที่มีประสิทธิภาพ

แนวทางที่มีประสิทธิภาพจะจัดเก็บขอบเขตสำหรับแต่ละองค์ประกอบที่เกิดขึ้นในการข้ามผ่านคำสั่งระดับ ขอบเขตเหล่านี้แสดงถึงขอบเขตที่องค์ประกอบของแผนผังย่อยสามารถอยู่ได้ ถ้าเราพูดถึงโหนดก็จะมีค่าต่ำสุดและสูงสุด แผนผังย่อยด้านซ้ายสามารถมีองค์ประกอบได้ตั้งแต่ขั้นต่ำที่ถูกผูกไว้จนถึงค่าโหนดปัจจุบัน -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 เพื่อตรวจสอบว่าอาร์เรย์ที่กำหนดสามารถแสดงถึงการส่งผ่านของลำดับระดับของ Binary Search Tree ได้หรือไม่

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

การวิเคราะห์ความซับซ้อน  

ความซับซ้อนของเวลา

ในขณะที่เราข้ามผ่านองค์ประกอบต่างๆ และในกรณีที่เลวร้ายที่สุดเราจำเป็นต้องสำรวจองค์ประกอบทั้งหมดอัลกอริทึมมีความซับซ้อนของเวลาเชิงเส้น บน).

ดูสิ่งนี้ด้วย
ค้นหา Subtrees ที่ซ้ำกัน

ความซับซ้อนของอวกาศ

เราได้ใช้คิวในการจัดเก็บองค์ประกอบซึ่งทำให้อัลกอริทึมมีความซับซ้อนของพื้นที่เชิงเส้น บน).