BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး တိတိရှိမရှိစစ်ဆေးပါ


ခက်ခဲအဆင့် လွယ်ကူသော
မကြာခဏမေးတယ် Accenture အမေဇုံ Monotype Solutions PayPal က မြတ်နိုး
Binary Search Tree ဒွိသစ်ပင် သစ်ပင်

ပြProbleနာဖော်ပြချက်

“ BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး စီတိတိကျကျရှိမရှိစစ်ဆေးပါ” သည်ပြproblemနာကသင့်အား binary search tree ၏ကြိုတင်မှာယူမှုကိုပေးသည်ဟုဖော်ပြသည်။ အရွက်မဟုတ်သော node အားလုံးသည်ကလေးတစ် ဦး တည်းသာပါဝင်သည်ကိုသင်ရှာဖွေရန်လိုအပ်သည်။ ဤနေရာတွင်ပေးထားသော input ရှိ node အားလုံးသည်ကွဲပြားသောတန်ဖိုးများရှိသည်ကိုလည်းကျွန်ုပ်တို့စဉ်းစားသည်။

နမူနာ

BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး တိတိရှိမရှိစစ်ဆေးပါ

 

Preorder Traversal: 6 15 7 9 11
Yes

ရှင်းလင်းချက်: အပေါ်ကပုံမှာမြင်ရတဲ့အတိုင်းပေးထားတဲ့ preorder ဖြတ်သန်းမှုရှိတဲ့သစ်ပင်ဟာ node တစ်ခုစီအတွက်တစ်ခုတည်းသောကလေးရှိတယ်။ ထို့ကြောင့် output ကိုဟုတ်ကဲ့ဖြစ်ပါတယ်။

BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး စီရှိမရှိစစ်ဆေးရန်နည်းလမ်း

ကြိုတင်မှာယူမှုဖြတ်သန်း ဆိုလိုသည်မှာ root သည် preference ကိုပေးပြီး၎င်း၏ဘယ်ဘက်နှင့်ညာ subtree မတိုင်မီပုံနှိပ်ထားသည်။ ထို့ကြောင့် root ပြီးနောက် element များသည် root ထက်သေးငယ်သည်ဖြစ်စေကြီးမားသည်။ ဒါကြောင့်ကျွန်တော်တို့ဟာပေးထားတဲ့ sequence ကိုတစ် ဦး ၏ preorder ဟုတ်မဟုတ်ကိုစစ်ဆေးဖို့လိုအပ်မယ်ဆိုရင် Binary Search Tree။ nested loops နှစ်ခုကိုသုံးပြီး binary search tree ကိုပေးထားတဲ့ sequence နဲ့အတူဖန်တီးနိုင်မလားဆိုတာစစ်ဆေးနိုင်ပါတယ်။

နုံချဉ်းကပ်နည်း

ကျွန်ုပ်တို့ဆွေးနွေးခဲ့ပြီးသည့်အတိုင်း၊ ထိုကြိုတင်မှာယူမှုလမ်းကြောင်းသည်အပေါ်ဘက်ရှိနှင့်ဘယ်ဘက်နှင့်ညာဘက် subtree ပုံနှိပ်ပြီးနောက်အမြစ်ပါရှိသည်။ အခုဒီစစ်ဆင်ရေးပြီးပြီ ပြန်လည် သစ်ပင်၌ရှိသမျှသော node များဖုံးလွှမ်းလျက်ရှိသည်အထိ။ ဒါကြောင့်ပေးထားတဲ့ sequence က BST ဟုတ်မဟုတ်ကိုစစ်ဆေးပြီး၊ root loop ကိုရွေးဖို့ပြင်ပ loop ကိုသုံးတဲ့ nested loops နှစ်ခုကို run ပါတယ်။ ပြီးတော့ nested loop က element ရဲ့ဘယ်ဘက်နဲ့ညာ subtree ကိုကိုယ်စားပြုနိုင်မလားဆိုတာစစ်ဆေးပါတယ်။ ထိုအရာအတွက်ကျွန်ုပ်တို့သည်အချို့သောအညွှန်းများမတိုင်မီအထိ element အားလုံးသည်ရွေးချယ်ထားသော element များထက်နည်းသည်ကိုစစ်ဆေးသည်။ ထိုနောက်မှဒြပ်စင်ရွေးချယ်သောဒြပ်စင်ထက်သာ။ ကြီးမြတ်ဖြစ်ကြသည်။ ယခုကျွန်ုပ်တို့အသုံးပြုမှုကိစ္စအရဤချဉ်းကပ်မှုကိုပြုပြင်နိုင်သည်။

BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး တိတိကျကျရှိမရှိစစ်ဆေးရန် algorithm ကိုမည်သို့ပြုပြင်ရမည်ကိုကြည့်ကြပါစို့။ အဆိုပါ BST ရဲ့ပြည်တွင်းရေးကလေးသည်အတိအကျကလေးတစ် ဦး ရှိပါက။ ဆိုလိုသည်မှာ internal node တစ်ခုစီသည် subtree ဘယ်ဘက်သို့မဟုတ်ညာ subtree တစ်ခုခုရှိနိုင်သည်။ ၎င်းသည် subtrees နှစ်ခုလုံးကိုတစ်ချိန်တည်းမဆံ့နိုင်ပါ။ ထို့ကြောင့်ကျွန်ုပ်တို့၏ algorithm ကိုအနှစ်ချုပ်ရန်။ ကျနော်တို့ကွင်းပြင်တစ်ခု element တစ်ခုရွေးဘယ်မှာအသိုက်နှစ်ခုနှစ်ခုကိုအသုံးပြုသည်။ ထိုအခါ nested loop သည်၎င်းမှလာသည့် element များသည် subtrees ထဲမှမည်သူတစ် ဦး တစ်ယောက်နှင့်သက်ဆိုင်သည်ကိုစစ်ဆေးရန်အသုံးပြုသည်။ ယခင်ကကျွန်ုပ်တို့တွင် element အချို့သည် root ထက် ပို၍ သေးငယ်သည်၊ ၎င်းထက် element များကသာလွန်သည်။ အခုတော့အဲဒီလိုအညွှန်းကိုရှာမရဘူး။ ၎င်းသည် polynomial အချိန်ရှုပ်ထွေးမှုဖြစ်သောကြောင့် (ဤနည်းသည်) မလုံလောက်ပါ။

ထိရောက်သောချဉ်းကပ်နည်း

ယခုအချိန်အထိမည်သည့် node များ၏သားသမီးအားလုံးသည်ပြproblemနာအရလက်ရှိ node ထက်နည်းမည်သို့မဟုတ်ပိုကြီးလိမ့်မည်ဟုကျွန်ုပ်တို့တစ်ချက်ရှင်းရှင်းလင်းလင်းဖော်ပြခဲ့သည်။ ထို့ကြောင့် BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး တိတိရှိမရှိစစ်ဆေးရန်လက်ရှိ node ၏နောက်ဆက်တွဲဆက်ခံသူကိုရှာသည်။ ထို့နောက်ကျွန်ုပ်တို့သည်လက်ရှိ node ၏နောက်ဆုံးကြိုတင်ဆက်ခံသူကိုရှာသည်။ ဆက်ခံသူနှစ် ဦး စလုံးသည်လက်ရှိ node ထက်နည်းနေလျှင်သို့မဟုတ်လက်ရှိ node ထက်ကြီးလျှင်။ နောက်တစ်ခုဆက်လုပ်မယ်။ လက်ရှိ node မှာဘယ်ဖက်နဲ့ညာဖက် subtree နှစ်မျိုးစလုံးရှိတယ်ဆိုတာသိတယ်။ ဘာလို့လဲဆိုတော့ element တစ်ခုက current node ထက်သေးတယ်။ နောက် node သည်လက်ရှိ node ထက်ပိုကြီးသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည်ကျွန်ုပ်တို့၏လိုအပ်ချက်အတိုင်း false သို့မဟုတ် -1 သို့ပြန်သွားသည်။

ကုဒ်

BST တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး တိတိရှိမရှိစစ်ဆေးရန် C ++ ကုဒ်

#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 တစ်ခု၏အတွင်းပိုင်း node တစ်ခုစီတွင်ကလေးတစ် ဦး တိတိရှိမရှိစစ်ဆေးရန် Java ကုဒ်

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)၊ ကျနော်တို့ကကြိုတင်မှာယူမှုခင်းကျင်းကိုဖြတ်သန်းသွားသောကြောင့်။ preorder array မှာ N element တွေရှိတယ်။

အာကာသရှုပ်ထွေးမှု

O (N), recursive stack အတွက်လိုအပ်သောနေရာ, ငါတို့သည်လည်း preorder sequence ကိုသိမ်းဆည်းရန်အရွယ်အစား N ကိုတစ် ဦး input ကိုခင်းကျင်းကိုအသုံးပြုခဲ့သည်။