BST ကိုပြောင်းလဲခြင်းကိုခွင့်မပြုသည့်အချိန်တွင် K'th အကြီးမားဆုံး Element ကို


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် အမေဇုံ Cisco သည် Google UHG Optum
Binary Search Tree ဒွိသစ်ပင် သစ်ပင်

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

“ BST တွင် K'th အကြီးမားဆုံး Element ကိုခွင့်ပြုမထားသောအခါ” သည် binary search tree ပေးပြီး kth အကြီးဆုံး element ကိုရှာရန်လိုအပ်သည်။ ဆိုလိုသည်မှာ binary search tree ၏ element များအားလုံးကို sort လုပ်ရန်စီစဉ်ပေးသောအခါဖြစ်သည်။ ပြီးရင် kth element ကို sequence ကနေပြန်ရမယ်။

နမူနာ

input

BST ကိုပြောင်းလဲခြင်းကိုခွင့်မပြုသည့်အချိန်တွင် K'th အကြီးမားဆုံး Element ကို

= = ၄

3

ရှင်းလင်းချက် - သစ်ပင်၏ရုပ်ပုံကိုအပေါ်တွင်ပြထားသည်။ 4th အကြီးဆုံး element ကိုရှာဖို့လိုတယ်။ ဒီတော့သူတို့ကိုကန ဦး အစီအစဉ်အတိုင်းစီစဉ်မယ်ဆိုရင်သူတို့က {1, 2, 3, 4, 5, 6} ။ ဒီတော့ 4th အကြီးဆုံး element က 3rd smallest element ဖြစ်တယ်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် output ကိုအဖြစ် 3 ပြန်သွားပါ။

BST ကိုပြုပြင်မွမ်းမံရန်ခွင့်မပြုသည့်အချိန်တွင် K'th အကြီးဆုံး Element ကို BST တွင်ရှာရန်ချဉ်းကပ်မှု

ကျွန်ုပ်တို့လည်းအလားတူမေးခွန်းတစ်ခုကိုပြုလုပ်ခဲ့ပြီးဖြစ်သည် k-th အသေးဆုံးဒြပ်စင် အဆိုပါ BST ၌တည်၏။ အဆိုပါပြproblemနာကိုကျော်ရုံပြုပြင်မွမ်းမံသည်။ ပြီးခဲ့သည့်ပို့စ်တွင်ကျွန်ုပ်တို့သည်ထိုမေးခွန်းအတွက်ဖြေရှင်းနည်းများကိုဆွေးနွေးခဲ့ကြသည်။ ပထမ ဦး ဆုံးချဉ်းကပ်သစ်ပင်ဒေတာဖွဲ့စည်းပုံကိုပြုပြင်မွမ်းမံရန်ဖြစ်ခဲ့သည်။ အခြားတစ်ခုမှာ binary search tree အတွက်အစဉ်လိုက်ဖြတ်သန်းသွားသောလမ်းကြောင်းနှင့် node များကိုရေတွက်ရန်ဖြစ်သည်။ ယခင်မေးခွန်း kth အသေးဆုံးပြန်သွားဖို့ဖြစ်ခဲ့သည်ကတည်းက။ node အရေအတွက်ကိုရေတွက်ရုံနဲ့ count တန်ဖိုး k ဖြစ်တာနဲ့အဲ့ဒီ node ပေါ်က value ကို return ပြန်လိုက်တယ်။

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

ဒီမှာအခြေအနေကနည်းနည်းကွဲပြားတယ်။ kth အကြီးဆုံးဒြပ်စင်ကိုရှာရန်လိုသည်။ ပထမဆုံးသစ်ပင်ရှိ node စုစုပေါင်းကိုရှာပြီး k-1 ကိုစုစုပေါင်း node များမှနုတ်နိုင်သည်။ ယခုမှာ n-k + 1 အငယ်ဆုံး node ကိုတွေ့ပြီ။ b သည် binary search tree ရှိ node စုစုပေါင်းဖြစ်သည်။ သို့သော်ဤချဉ်းကပ်မှုသည်နှစ်ဆင့်သို့မဟုတ်နှစ်ဆင့်လိုအပ်သည် ဖြတ်သန်း သစ်ပင်ပေါ်မှာ။

ထိရောက်သောချဉ်းကပ်မှု

ကျွန်ုပ်တို့သည် node များကိုအစဉ်လိုက်အတိုင်းရှာပါကပြproblemနာကိုထိရောက်စွာဖြေရှင်းနိုင်သည်။ ထိုနည်းအားဖြင့်သစ်ပင်ထဲတွင်စုစုပေါင်း node များရှာရန်မလိုအပ်ပါ။ ထိရောက်သောချဉ်းကပ်မှုတစ်ခုသည်အပင်၏ပြောင်းပြန် - ဖြတ်ကူးခြင်းကိုပြုရန်ဖြစ်သည်။ binary search tree ၏ inorder inverse traversal သည်အပင်ကိုအစဉ်လိုက်ဖြတ်သန်းသွားသည်။ ဒါကြောင့်ပြောင်းပြန် in-order လုပ်နေစဉ်, ငါတို့ node များရေတွက်ဆက်လက်ပါလိမ့်မယ်။ count က k နဲ့ညီတယ်ဆိုရင်အဲ့ node ပေါ်က value ကို return ပြန်မယ်။

ကုဒ်

B ++ ကိုပြောင်းလဲခြင်းကိုခွင့်မပြုသောအခါ K'th အကြီးဆုံး Element ကို BST တွင်ရှာရန် C ++ ကုဒ်

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;
    node *left;
    node *right;
} ;
node* create(int data){
    node * tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
    return tmp;
}
// normally insert the node in BST
node* insert(node* root, int x)
{
    if (root == NULL)
        return create(x);
    if(x<root->data)
        root->left = insert(root->left, x);
    else if(x>root->data)
        root->right = insert(root->right, x);
    return root;
}
node* findKthLargest(node* root, int& k)
{
    // base case
    if(!root)
        return NULL;
    node *right = findKthLargest(root->right, k);
    if(right)
        return right;
    // if current element is kth largest
    if(k==1)
        return root;
    // if the kth largest is not found in the left subtree
    // search in left subtree
    k--;
    return findKthLargest(root->left, k);
}
int main()
{
    node *root = NULL;
    int n;cin>>n;
    for(int i=0;i<n;i++){
        int element;cin>>element;
        root = insert(root, element);
    }
    int k;cin>>k;
    node* res = findKthLargest(root, k);
    if(res == NULL)
        cout<<"No kth largest found";
    else
        cout<<"Kth largest element is "<<res->data;
}
6
3 2 1 5 4 6
4
Kth largest element is 3

BST ကိုပြုပြင်ခြင်းအားခွင့်မပြုသောအခါ K'th အကြီးမားဆုံး Element ကို BST တွင်ရှာရန် Java ကုဒ်

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static int count;
  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.left = null;
      tmp.right = null;
      return tmp;
  }
 
  static node insert(node root, int x)
  {
      if (root == null)
          return create(x);
      if(x<root.data)
          root.left = insert(root.left, x);
      else if(x>root.data)
          root.right = insert(root.right, x);
      return root;
  }
 
  static node findKthLargest(node root, int k)
  {
      // base case
      if(root == null)
          return null;
      node right = findKthLargest(root.right, k);
      if(right != null)
          return right;
      count++;
      // if current element is kth largest
      if(k==count)
          return root;
      // if the kth largest is not found in the left subtree
      // search in left subtree
      return findKthLargest(root.left, k);
  }
  
  public static void main(String[] args)
  {
    Scanner sc = new Scanner(System.in);
      int n = sc.nextInt();
      for(int i=0;i<n;i++){
          int element = sc.nextInt();
          root = insert(root, element);
      }
      int k = sc.nextInt();
      count = 0;
      node res = findKthLargest(root, k);
      if(res == null)
          System.out.println("No kth largest found");
      else
          System.out.println("Kth largest element is "+res.data);
  }
}
6
3 2 1 5 4 6
4
Kth largest element is 3

ရှုပ်ထွေးဆန်းစစ်ခြင်း

အချိန်ရှုပ်ထွေး

အို (N)၊ ဘာဖြစ်လို့လဲဆိုတော့ငါတို့ကရိုးရိုးလေးဖြတ်သွားတာပါ BSTနှင့် BST ကတည်းကသာ N ကို node များရှိခဲ့ပါတယ်။ ကျွန်ုပ်တို့သည်အို (N) ၏ linear အချိန်ရှုပ်ထွေးမှုကိုရရှိခဲ့ပါပြီ။

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

အို (၁)၊ ကျနော်တို့သာစဉ်ဆက်မပြတ်အပိုအာကာသကိုအသုံးပြုခဲ့ကြသည်။ ထို့ကြောင့်၎င်း algorithm တစ်ခုတည်းတွင်အမြဲတမ်းရှုပ်ထွေးမှုရှုပ်ထွေးမှုရှိသော်လည်း program တစ်ခုလုံးတွင် linear space ရှုပ်ထွေးမှုရှိသည်။ ဘာလို့လဲဆိုတော့ငါတို့က N binary tree node တွေကိုသိုလှောင်ထားလို့ပဲ