BST හි සෑම අභ්‍යන්තර නෝඩයකම හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කරන්න


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇමේසන් මොනෝටයිප් විසඳුම් පේපෑල් Synopsys
ද්විමය සෙවුම් ගස ද්විමය ගස ගස

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

“බීඑස්ටී හි සෑම අභ්‍යන්තර නෝඩයකටම හරියටම එක් දරුවෙක් සිටීදැයි පරීක්ෂා කරන්න” ගැටලුවේ සඳහන් වන්නේ ඔබට ද්විමය සෙවුම් ගසක පෙර ඇණවුමක් ලබා දී ඇති බවයි. තවද කොළ නොවන සියලුම නෝඩ් වල ඇත්තේ තනි දරුවෙකු පමණක් දැයි ඔබ සොයා ගත යුතුය. දී ඇති ආදානයේ ඇති සියලුම නෝඩ් වල සුවිශේෂී අගයන් ඇති බව මෙහිදී අපි සලකා බලමු.

උදාහරණයක්

BST හි සෑම අභ්‍යන්තර නෝඩයකම හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කරන්න

 

Preorder Traversal: 6 15 7 9 11
Yes

පැහැදිලි කිරීම: ඉහත රූපයේ අපට දැකිය හැකි පරිදි, ලබා දී ඇති පූර්ව ඇණවුම් සංචලනය සහිත ගස සෑම අභ්‍යන්තර නෝඩයක් සඳහාම තනි දරුවෙකු ඇත. මේ අනුව ප්‍රතිදානය ඔව්.

BST හි සෑම අභ්‍යන්තර නෝඩයකම හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කිරීමට ප්‍රවේශය

පූර්ව ඇණවුම් ගමන් එහි අර්ථය වන්නේ මූලයට මනාප ලබා දී එහි වම් සහ දකුණු උප කුලයට පෙර මුද්‍රණය කිරීමයි. මේ අනුව මූලයෙන් පසු මූලද්‍රව්‍ය මූලයට වඩා කුඩා හෝ වැඩි වේ. එබැවින්, ලබා දී ඇති අනුක්‍රමයක් a හි පූර්ව ඇණවුමක් දැයි පරීක්ෂා කිරීමට අපට අවශ්‍ය නම් ද්විමය සෙවුම් ගස. දී ඇති අනුක්‍රමය සමඟ ද්විමය සෙවුම් ගසක් සෑදිය හැකිදැයි පරීක්ෂා කිරීමට අපට කූඩු ලූප දෙකක් භාවිතා කළ හැකිය.

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

අප දැනටමත් සාකච්ඡා කර ඇති පරිදි, එම පූර්ව ඇණවුම් ගමන් මාර්ගයෙහි මුල සහ වම් සහ දකුණු උප කුලකය මුද්‍රණය කිරීමෙන් පසුව මූල අඩංගු වේ. දැන් මෙම මෙහෙයුම සිදු කර ඇත පුනරාවර්තන ලෙස ගසෙහි ඇති සියලුම නෝඩ් ආවරණය වන තුරු. එබැවින්, ලබා දී ඇති අනුක්‍රමය බීඑස්ටී එකක් නියෝජනය කරන්නේ දැයි අපට පරීක්ෂා කළ හැකිය, අපි කූඩුවක ලූප දෙකක් ධාවනය කරන්නෙමු. තවද එහි ඇති මූලද්‍රව්‍යයන්ට එහි වම් සහ දකුණු උප කුලකය නිරූපණය කළ හැකිදැයි කැදැලි ලූපය පරීක්ෂා කරයි. ඒ සඳහා, යම් දර්ශකයක් තෙක් සියලු මූලද්‍රව්‍ය තෝරාගත් මූලද්‍රව්‍යයට වඩා අඩු දැයි අපි පරීක්ෂා කරමු. ඉන්පසු ඇති මූලද්‍රව්‍ය තෝරාගත් මූලද්‍රව්‍යයට වඩා වැඩිය. දැන්, අපගේ භාවිතයට අනුව මෙම ප්‍රවේශය වෙනස් කළ හැකිය.

BST හි එක් එක් අභ්‍යන්තර නෝඩයට හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කිරීම සඳහා අපි ඇල්ගොරිතම වෙනස් කරන්නේ කෙසේදැයි බලමු. බීඑස්ටී හි අභ්‍යන්තර දරුවාට හරියටම එක් දරුවෙකු සිටී නම්. මෙයින් අදහස් කරන්නේ සෑම අභ්‍යන්තර නෝඩයකම වම් උප කුලක හෝ දකුණු උප කුලක තිබිය හැකි බවයි. එය එකවර උප කුලක දෙකම අඩංගු නොවේ. මේ අනුව, අපගේ ඇල්ගොරිතම සාරාංශ කිරීමට. අපි කූඩුවල ලූප දෙකක් භාවිතා කරමු, එහිදී පිටත ලූපය මූලද්‍රව්‍යයක් තෝරා ගනී. එවිට කැදැලි ලූපය උප කුලකයේ ඕනෑම කෙනෙකුට අයත් දැයි පරීක්ෂා කිරීමට භාවිතා කරයි. මීට පෙර, මූලයට වඩා මූලද්‍රව්‍යයන් අඩු වූ මූලද්‍රව්‍යවලට වඩා විශාල වූ නිශ්චිත දර්ශකයක් අප සතුව තිබුණි. දැන් අපට එවැනි දර්ශකයක් හමු නොවේ. නමුත් මෙම ක්‍රමය O (N ^ 2) හි බහුපද-කාල සංකීර්ණතාවයක් ඇති බැවින් එය කාර්යක්ෂම නොවේ.

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

මේ දක්වා, අපි එක් කරුණක් පැහැදිලි කර ඇත්තේ මෙම ගැටළුව අනුව ඕනෑම නෝඩයක සියලුම දරුවන් වත්මන් නෝඩයට වඩා අඩු හෝ වැඩි වනු ඇති බවයි. එබැවින්, බීඑස්ටී හි සෑම අභ්‍යන්තර නෝඩයකටම හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කර බැලීමට වත්මන් නෝඩයේ ඊළඟ පූර්ව ඇණවුම් අනුප්‍රාප්තිකයා අපට හමු වේ. වත්මන් නෝඩයේ අවසාන පූර්ව ඇණවුම් අනුප්‍රාප්තිකයා අපට හමු වේ. අනුප්‍රාප්තිකයන් දෙදෙනාම වත්මන් නෝඩයට වඩා අඩු නම් හෝ වත්මන් නෝඩයට වඩා වැඩි නම්. වත්මන් නෝඩයේ වම් සහ දකුණු උප කුලක දෙකම ඇති බව අපි දනිමු. මන්දයත් එක් මූලද්‍රව්‍යයක් වත්මන් නෝඩයට වඩා කුඩා වන බැවිනි. තවත් නෝඩයක් වත්මන් නෝඩයට වඩා විශාලය. මේ අනුව අපි අපේ අවශ්‍යතාවය අනුව ව්‍යාජ හෝ -1 ආපසු ලබා දෙමු.

කේතය

බීඑස්ටී හි සෑම අභ්‍යන්තර නෝඩයකටම හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කිරීමට සී ++ කේතය

#include<bits/stdc++.h>
using namespace std;

bool checkIfALlInternalNodesHaveSingleChild(vector<int> preorder, int i){
    int n = preorder.size();
    if(i==n-1)return true;
    int next = preorder[i+1] - preorder[i];
    int lst = preorder[n-1] - preorder[i];
    int prod = next*lst;
    if(prod<0)
    return false;
    return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
}

int main()
{
    int n;cin>>n;
    vector<int> preorder(n);
    for(int i=0;i<n;i++)cin>>preorder[i];
    cout<<(checkIfALlInternalNodesHaveSingleChild(preorder, 0) ? "Yes" : "No");
}
5
6 15 7 9 11
Yes

BST හි සෑම අභ්‍යන්තර නෝඩයකම හරියටම එක් දරුවෙකු සිටීදැයි පරීක්ෂා කිරීමට ජාවා කේතය

import java.util.*;
import java.lang.*;
import java.io.*;
class Main
{
  static boolean checkIfALlInternalNodesHaveSingleChild(int preorder[], int i){
      int n = preorder.length;
      if(i==n-1)return true;
      int next = preorder[i+1] - preorder[i];
      int lst = preorder[n-1] - preorder[i];
      int prod = next*lst;
      if(prod<0)
      return false;
      return checkIfALlInternalNodesHaveSingleChild(preorder, i+1);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      int preorder[] = new int[n];
      for(int i=0;i<n;i++)preorder[i] = sc.nextInt();
      boolean answer = checkIfALlInternalNodesHaveSingleChild(preorder, 0);
      System.out.print(answer == true ? "Yes" : "No");
  }
}
5
6 15 7 9 11
Yes

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

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

ඕ (එන්), අපි දැන් පෙර ඇණවුම් අරාව හරහා ගමන් කර ඇති නිසා. පෙර ඇණවුම් අරාවෙහි N මූලද්‍රව්‍ය ඇති බැවින් රේඛීය කාල සංකීර්ණතාවයක් ඇත.

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

O (N), පුනරාවර්තන තොගයට අවශ්‍ය අවකාශය වන අතර, පෙර ඇණවුම් අනුක්‍රමය ගබඩා කිරීම සඳහා අපි N ප්‍රමාණයේ ආදාන පෙළක් ද භාවිතා කළෙමු.