දී ඇති අරාවට ද්විමය සෙවුම් ගසෙහි මට්ටමේ ඇණවුම් ගමන් කිරීම නිරූපණය කළ හැකිදැයි පරීක්ෂා කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇමේසන් Citrix IBM ආයතනය ඇත්ත වශයෙන්ම තොරතුරු එජ් OYO කාමර Teradata
ද්විමය සෙවුම් ගස ද්විමය ගස පෝලිමේ ගස රුක් සංචලනය

ගැටළු ප්රකාශය

“ලබා දී ඇති අරාවට ද්විමය සෙවුම් ගසෙහි මට්ටමේ ඇණවුම නිරූපණය කළ හැකිදැයි පරීක්ෂා කරන්න” යන ගැටළුවෙහි දැක්වෙන්නේ ඔබට මට්ටමේ ඇණවුමක් හරහා ගමන් කළ හැකි බවයි. ද්විමය සෙවුම් ගස. සහ භාවිතා කිරීම මට්ටමේ ඇණවුම හරහා ගමන් කිරීම ගසේ. මට්ටමේ ඇණවුම හරහා ගමන් කිරීම ද්විමය සෙවුම් ගසක් නියෝජනය කළ හැකිද නැද්ද යන්න අප කාර්යක්ෂමව සොයාගත යුතුද?

උදාහරණයක්

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

 

දී ඇති අරාවට ද්විමය සෙවුම් ගසෙහි මට්ටමේ ඇණවුම් ගමන් කිරීම නිරූපණය කළ හැකිදැයි පරීක්ෂා කරන්න

පැහැදිලි කිරීම

දී ඇති මට්ටමේ ඇණවුම හරහා ගමන් කිරීම රූපයේ දැක්වෙන ද්විමය ගස නියෝජනය කරයි. අපට පෙනෙන පරිදි ගස ද්විමය ගසක සියලු ගුණාංග තෘප්තිමත් කරන අතර එමඟින් ප්‍රතිදානය සත්‍ය වේ.

ලබා දී ඇති අරාව ද්විමය සෙවුම් ගසෙහි මට්ටමේ ඇණවුම් ගමන් කිරීම නිරූපණය කළ හැකිදැයි පරීක්ෂා කිරීමට ප්‍රවේශය

බොළඳ ප්‍රවේශය

ලබා දී ඇති මට්ටමේ අනුපිළිවෙල තෘප්තිමත් කරන සියලුම ද්විමය ගස් අප ගමන් කිරීමට උත්සාහ කළහොත් බොළඳ ප්‍රවේශයක් විය හැකිය. ගස ද්විමය සෙවුම් ගසක් නියෝජනය කරන්නේ දැයි පරීක්ෂා කරන්න. නමුත් මෙම මෙහෙයුම ඉතා මිල අධික වනු ඇත. පළමුවෙන්ම මෙන්, අපි බොහෝ ගස් ඉදිකරනු ඇත. එවිට ඇල්ගොරිතම මගින් සාදන ලද ගස BST දැයි පරීක්ෂා කිරීම අවශ්‍ය වේ. එබැවින් ගස ඉදිකිරීමට අවශ්‍ය නොවන තැනක් අප විසින් කළ යුතුය.

කාර්යක්ෂම ප්‍රවේශය

කාර්යක්ෂම ප්‍රවේශයක් මඟින් මට්ටම් අනුපිළිවෙලෙහි සිදුවන එක් එක් මූලද්‍රව්‍ය සඳහා මායිම් ගබඩා කරනු ඇත. මෙම සීමාවන් නිරූපණය කරන්නේ ඒවායේ උප කුලක මූලද්‍රව්‍යයන් පැවතිය හැකි සීමාවයි. අපි නෝඩයක් ගැන කතා කරන්නේ නම්, එය අවම සහ උපරිම වේ. වම් උප කුලයට අවම මායිමේ සිට වත්මන් නෝඩ් අගය -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

ලබා දී ඇති අරාව ද්විමය සෙවුම් ගසෙහි මට්ටමේ ඇණවුම් ගමන් කිරීම නිරූපණය කළ හැකිදැයි පරීක්ෂා කිරීමට ජාවා කේතය

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

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

අපි හුදෙක් මූලද්රව්ය හරහා ගමන් කර ඇති පරිදි. නරකම අවස්ථාවක, අපට සියලු මූලද්රව්ය හරහා ගමන් කළ යුතුය, ඇල්ගොරිතමයට රේඛීය කාල සංකීර්ණතාවයක් ඇත මත).

අභ්‍යවකාශ සංකීර්ණතාව

රේඛීය අවකාශ සංකීර්ණතාව සඳහා ඇල්ගොරිතම සෑදූ මූලද්‍රව්‍ය ගබඩා කිරීම සඳහා අපි පෝලිමක් භාවිතා කර ඇත්තෙමු මත).