Проверите да ли дати низ може представљати прелазак редоследа нивоа бинарног стабла претраживања  


Ниво тешкоће Лако
Често питани у амазонка Цитрик ИБМ- Заиста Инфо Едге ОИО собе терадата
Бинарно стабло претраживања Бинарно дрво Ред Дрво Прелазак дрвета

Изјава о проблему  

Проблем „Проверите да ли дати низ може представљати прелазак редоследа нивоа бинарног стабла претраживања“ наводи да вам је дато обилажење редоследа нивоа бинарно стабло претраге. И користећи прелазак редоследа нивоа од дрвета. Морамо ефикасно да утврдимо може ли прелазак редоследа нивоа представљати бинарно стабло претраживања или не?

Пример  

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

 

Проверите да ли дати низ може представљати прелазак редоследа нивоа бинарног стабла претраживањаПин

Објашњење

Дати прелазак редоследа нивоа представља бинарно стабло које је приказано на слици. И као што можемо видети да стабло задовољава сва својства бинарног стабла и стога је резултат тачан.

Приступ провери да ли дати низ може представљати прелазак редоследа нивоа бинарног стабла претраживања  

Наивни приступ

Наиван приступ би могао бити ако покушамо да направимо заокрет свих бинарних стабала која задовољавају дати ниво. А затим проверите да ли дрво представља бинарно стабло претраживања. Али ова операција ће бити веома скупа. Као и пре свега, изградићемо мноштво дрвећа. Тада алгоритам захтева проверу да ли је формирано стабло БСТ. Дакле, морамо учинити нешто тамо где не треба да конструишемо дрво.

Види такође
Избришите Н-ти чвор са краја дате повезане листе

Ефикасан приступ

Ефикасан приступ ће сачувати границе за сваки од елемената који се јављају у преласку по нивоу. Ове границе представљају границу у којој могу лежати њихови елементи подстабла. Ако говоримо о чвору, он ће имати минимум и максимум. Лево подстабло може имати елементе у распону од минимално везаног до тренутне вредности чвора-1. Док се елементи у десном подстаблу могу кретати од тренутне вредности чвора + 1 до максимално везане.

Дакле, користићемо ред где ћемо наставити са уметањем елемената са овим границама и ако будемо могли да прелазимо кроз све чворове. Кажемо да дат прелазак редоследа нивоа може представљати БСТ, у супротном не. Алгоритам је врло сличан алгоритму провере да ли је бинарно стабло БСТ или није?

код  

Ц ++ код за проверу да ли дати низ може представљати прелазак редоследа нивоа бинарног стабла претраживања

#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

Анализа сложености  

Сложеност времена

Као што смо једноставно прешли преко елемената. А у најгорем случају, морамо прећи преко свих елемената, алгоритам има линеарну временску сложеност НА).

Види такође
Пронађите дупликате подстабла

Сложеност простора

Користили смо ред за складиштење елемената који су алгоритам направили да има линеарну сложеност простора НА).