BST တွင် k-th အသေးဆုံး element ကိုရှာပါ။  


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

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

"k-th အသေးဆုံး element ကိုရှာပါ BST (Order Statistics in BST)” ပြproblemနာကသင်ကို binary search tree ပေးပြီး BST တွင် k-th အငယ်ဆုံးနံပါတ်ကိုရှာရန်လိုအပ်သည်ဟုဖော်ပြသည်။ ဆိုလိုတာကတော့ငါတို့လုပ်မယ် စနစ်တကျဖြစ်သည် binary search tree ၏လမ်းကြောင်းကိုဖြတ်ပြီးရလဒ်ကို vector / array တစ်ခုသိမ်းထားပါ။ ထိုအခါ 1 (based-indexing) ကိုစဉ်းစားပါက index (k-0) သည်အ kth အငယ်ဆုံးဖြစ်သည်။

နမူနာ  

input

 

BST တွင် k-th အသေးဆုံး element ကိုရှာပါ။

= = ၂

6

ရှင်းလင်းချက် - ကျွန်ုပ်တို့ပေးထားသော binary tree ကိုအစဉ်လိုက်ဖြတ်ကူးလျှင် {2, 4, 5, 6, 8, 9} ။ ဒီတော့ဒီမှာကျွန်တော်တို့ဟာ 4th အသေးငယ်ဆုံး element ကိုရှာဖို့လိုတယ်။ ဒါက 6 ဖြစ်တယ်။ ဒီတော့ output က 6 ။

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

Augmented သစ်ပင် Data ဖွဲ့စည်းပုံ

ဤချဉ်းကပ်မှုတွင် node တစ်ခုစီသည်၎င်းကိုဘယ်ဖက်ခွဲသစ်ပင်တွင်သိမ်းဆည်းထားသည်ဟုကျွန်ုပ်တို့စဉ်းစားသည်။ သစ်ပင်ကိုတည်ဆောက်စဉ်ကျွန်ုပ်တို့သည် node တစ်ခုစီ၏ဘယ်ဘက် subtree တွင် element များကိုထိန်းသိမ်းသည်။ ဤအချက်ကိုသစ်ပင်ထဲတွင် k-th အသေးဆုံး element ကိုရှာဖွေရန်အသုံးပြုသည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် kth element ကိုရှာသောအခါဘယ်ဘက် subtree တွင် k ထက် element များပိုများလာသည်ကိုစစ်ဆေးသည်။ ထိုအခါကျွန်ုပ်တို့၏ k-th အသေးဆုံးသည်ဘယ်ဘက်အပင်တွင်တည်ရှိပြီးအခြားတစ်ဖက်သည်လက်ျာ sub-tree တွင်တည်ရှိသည်။ ထိုနည်းအားဖြင့် BST တွင် k-th အငယ်ဆုံးသော element ကိုကျွန်ုပ်တို့တွေ့ရှိနိုင်သည်။

လည်းကြည့်ရှုပါ
မျှမျှတတ Binary Tree

ကုဒ်

B ++ တွင် k-th အသေးဆုံး element ကိုရှာရန် C ++ code
#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    int leftCnt;
    node *left;
    node *right;
} ;

node* create(int data){
    node * tmp = new node();
    tmp->data = data;
    tmp->leftCnt = 0;
    tmp->left = tmp->right = NULL;
    return tmp;
}

node* insert(node* root, int x)
{
    if (root == NULL)
        return create(x);
    // we do the same as done to insert an element in the BST
    // but if we insert an element in the left sub-tree
    // we increment the count of nodes in left sub-tree as well
    if(x<root->data){
        root->left = insert(root->left, x);
        root->leftCnt++;
    }
    else if(x>root->data)
        root->right = insert(root->right, x);
    return root;
}


node* findKthSmallest(node *root, int k)
{
    if (!root)
        return NULL;

    int cnt = root->leftCnt+1;

    // current node is the k-th smallest element
    if(cnt == k)
        return root;
    else if(k > cnt)
        return findKthSmallest(root->right, k-cnt);
    else
        return findKthSmallest(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 = findKthSmallest(root, k);
    if(res == NULL)
        cout<<"No kth smallest found";
    else
        cout<<"Kth smallest element is "<<res->data;
}
6
5 4 2 8 6 9
4
6
BST တွင် k-th အသေးဆုံး element ကိုရှာရန် Java code
import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int leftCnt;
  node left;
  node right;
}

class Tree{
  static node root;
  
  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.leftCnt = 0;
      tmp.left = null;
      tmp.right = null;
      return tmp;
  }
  
  static node insert(node root, int x)
  {
      if (root == null)
          return create(x);
      // we do the same as done to insert an element in the BST
      // but if we insert an element in the left sub-tree
      // we increment the count of nodes in left sub-tree as well
      if(x<root.data){
          root.left = insert(root.left, x);
          root.leftCnt++;
      }
      else if(x>root.data)
          root.right = insert(root.right, x);
      return root;
  }
  
  
  static node findKthSmallest(node root, int k)
  {
      if (root == null)
          return null;
  
      int cnt = root.leftCnt+1;
  
      // current node is the k-th smallest element
      if(cnt == k)
          return root;
      else if(k > cnt)
          return findKthSmallest(root.right, k-cnt);
      else
          return findKthSmallest(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();
      node res = findKthSmallest(root, k);
      if(res == null)
          System.out.println("No kth smallest found");
      else
          System.out.println("Kth smallest element is "+res.data);
  }
}
6
5 4 2 8 6 9
4
Kth smallest element is 6

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

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

အို (H)အဆိုးဆုံးအနေဖြင့် အကယ်၍ ကျွန်ုပ်တို့သည် input ကိုအညွန့်အပင်တစ်ပင်ရှိပါက Nth အသေးဆုံး element ကိုရှာရန်လိုအပ်ပါက N သည်ညီမျှနိုင်သည်။

လည်းကြည့်ရှုပါ
binary သစ်ပင်၏နယ်နိမိတ်ဖြတ်သန်း
အာကာသရှုပ်ထွေးမှု

အို (H)၊ ဘယ်ဘက် subtree ရှိ node အရေအတွက်ကိုရေတွက်ရန် leftCnt မှလိုအပ်သောအာကာသကိုဤနေရာတွင်ကျွန်ုပ်တို့မထည့်သွင်းပါ။ leftCnt သည်သစ်ပင်၏အစိတ်အပိုင်းတစ်ခုဖြစ်သည်၊ ထို့ကြောင့်အို (H) အာကာသသည်ပြန်လည်ပြုပြင်ရန်လိုအပ်သောနေရာဖြစ်သည်။

Inorder ဖြတ်သန်း

“ BST တွင်ရှာပါ k-th အသေးဆုံးဒြပ်စင် (BST ရှိအမိန့်စာရင်း)” သည် Binary Search Tree ၏ inorder ဖြတ်သန်းမှုသည် node များတိုးပွားလာသဖြင့် inorder traversal ကို အသုံးပြု၍ ဖြေရှင်းနိုင်သည်။ ထို့ကြောင့်ကျွန်ုပ်တို့သည် count variable ကိုသိမ်းနိုင်သည်။ ဒီ count variable က k နဲ့ညီရင် BST မှာ k-th အငယ်ဆုံးသော element ကိုငါတို့သိတယ်။

ကုဒ်

B ++ တွင် k-th အသေးဆုံး element ကိုရှာရန် C ++ code
#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* findKthSmallest(node* root, int& k)
{
    // base case
    if(!root)
        return NULL;
    node *left = findKthSmallest(root->left, k);
    if(left)
        return left;
    // if current element is kth smallest
    if(k==1)
        return root;
    // if the kth smallest is not found in the left subtree
    // search in right subtree
    k--;
    return findKthSmallest(root->right, 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 = findKthSmallest(root, k);
    if(res == NULL)
        cout<<"No kth smallest found";
    else
        cout<<"Kth smallest element is "<<res->data;
}
6
5 4 2 8 6 9
4
Kth smallest element is 6
Java Code သည် BST တွင် k-th အသေးဆုံး element ကိုရှာရန်
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 findKthSmallest(node root, int k)
  {
      // base case
      if(root == null)
          return null;
      node left = findKthSmallest(root.left, k);
      if(left != null)
          return left;
      count++;
      // if current element is kth smallest
      if(k==count)
          return root;
      // if the kth smallest is not found in the left subtree
      // search in right subtree
      return findKthSmallest(root.right, 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 = findKthSmallest(root, k);
      if(res == null)
          System.out.println("No kth smallest found");
      else
          System.out.println("Kth smallest element is "+res.data);
  }
}
6
5 4 2 8 6 9
4
Kth smallest element is 6

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

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

အို (N)ဘာဖြစ်လို့လဲဆိုတော့ k-th element ကိုရောက်ဖို့ဆိုရင်ငါတို့ပထမ ဦး ဆုံး k-1 element တွေကိုဖြတ်ဖို့လိုတယ်။ ထို့ကြောင့် kth element သည်အမြစ်ဖြစ်ပါကဘယ်ဘက် subtree ၏အစိတ်အပိုင်းအားလုံးကိုဖြတ်သန်းရလိမ့်မည်။

လည်းကြည့်ရှုပါ
ပေးထားသောအရွယ်အစားခင်းကျင်းမှု n ကို BST ၏ကိုယ်စားပြုမှု (သို့) မကိုယ်စားပြုသည်ကိုစစ်ဆေးပါ
အာကာသရှုပ်ထွေးမှု

အို (H)၊  ဒီနေရာမှာဒီရှုပ်ထွေးမှုကပြန်ဖြစ်လို့ရတယ်။ အစီအစဉ်တစ်ခုလုံးသည် linear ရှုပ်ထွေးမှုရှိသော်လည်း အဆိုပါ algorithm ကိုသူ့ဟာသူအို (H) အာကာသအတွင်းပြေး။