બીએસટીમાં કે-થર સૌથી નાનું તત્વ શોધો (બીએસટીમાં આંકડા Orderર્ડર કરો)


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે ભેગા એમેઝોન Google
દ્વિસંગી શોધ વૃક્ષ દ્વિસંગી વૃક્ષ વૃક્ષ

સમસ્યા નિવેદન

“માં K-th નાના તત્વ શોધો બીએસટી (બીએસટીમાં ઓર્ડર સ્ટેટિસ્ટિક્સ) ”સમસ્યા જણાવે છે કે તમને બાઈનરી સર્ચ ટ્રી આપવામાં આવે છે અને તમારે બીએસટીમાં સૌથી ઓછી સંખ્યામાં K-th શોધવાની જરૂર છે. આનો અર્થ છે જો આપણે એક કરીએ ક્રમમાં દ્વિસંગી શોધ વૃક્ષનું આડેધડ અને પરિણામ વેક્ટર / એરેમાં સંગ્રહિત કરો. પછી જો આપણે 1-આધારિત અનુક્રમણિકાને ધ્યાનમાં લઈએ તો અનુક્રમણિકા (કે -0) પરનું તત્વ એ kth સૌથી નાનું હશે.

ઉદાહરણ

ઇનપુટ

 

બીએસટીમાં કે-થર સૌથી નાનું તત્વ શોધો (બીએસટીમાં આંકડા Orderર્ડર કરો)

કે = 4

6

સમજૂતી: જો આપણે આપેલ દ્વિસંગી વૃક્ષનું orderર્ડર ટ્રાવેલસલ કરીએ તો અમને {2, 4, 5, 6, 8, 9} મળે છે. આમાં, આપણે પછી ચોથા નાના તત્વને શોધવાની જરૂર છે જે તે 4 છે. આમ આઉટપુટ 6 છે.

અભિગમ

ઓગમેન્ટેડ ટ્રી ડેટા સ્ટ્રક્ચર

આ અભિગમમાં, અમે ધ્યાનમાં લઈએ છીએ કે દરેક નોડ તત્વને તેની ડાબી પેટા-ઝાડમાં સંગ્રહિત કરે છે. ઝાડ બનાવતી વખતે અમે દરેક નોડની ડાબી પેટાશ્રીમાં તત્વો જાળવીએ છીએ. આ તથ્યનો ઉપયોગ વૃક્ષમાંના કે-th નાનામાં નાના તત્વને શોધવા માટે થાય છે. તેથી જ્યારે આપણે kth એલિમેન્ટ શોધવાનો પ્રયત્ન કરીએ છીએ ત્યારે આપણે તપાસીએ છીએ કે જો ડાબી સબટ્રીમાં k કરતા વધારે તત્વો હોય. પછી આપણું કે-મી નાનું તત્વ ડાબી પેટા-ઝાડમાં રહેલું છે અન્યથા તે જમણા પેટા-ઝાડમાં આવેલું છે. અને તે જ રીતે આપણે બીએસટીમાં કે-મી નાનું સૌથી નાનું તત્વ શોધીએ છીએ.

કોડ

બીએસટીમાં K-th નાનું તત્વ શોધવા માટે સી ++ કોડ
#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
બીએસટીમાં K-th નાનું તત્વ શોધવા માટે જાવા કોડ
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 એ N ની બરાબર હોઇ શકે છે જો આપણી પાસે ઇનપુટ તરીકે સ્ક્વિડ વૃક્ષ હોય અને આપણે Nth નાનો તત્વ શોધવાની જરૂર હોય.

અવકાશ જટિલતા

ઓ (એચ), અહીં આપણે ડાબી સબટ્રીમાં ગાંઠોની સંખ્યા ગણવા માટે ડાબીસીએન્ટ દ્વારા જરૂરી જગ્યાને ધ્યાનમાં લેતા નથી. અમે ધ્યાનમાં લઈએ છીએ કે લેફ્ટ સીન્ટ એ ઝાડનો એક ભાગ છે અને તેથી ઓ (એચ) જગ્યા પુનરાવર્તન દ્વારા જરૂરી જગ્યા છે.

આંતરિક ક્રમિક

"બી.એસ.ટી. માં સૌથી નાના તત્વ શોધી કા elementો (બી.એસ.ટી. માં ઓર્ડર સ્ટેટિસ્ટિક્સ)" ને ઇનઓર્ડર ટ્રversવર્સલનો ઉપયોગ કરીને ઉકેલી શકાય છે કારણ કે બાઈનરી સર્ચ ટ્રીના ઇનોર્ડર ટ્રાવર્સલ વધતા ક્રમમાં ગાંઠોને વહન કરે છે. આમ આપણે કાઉન્ટ વેરીએબલ રાખી શકીએ છીએ. જ્યારે આ ગણતરી ચલ k ની બરાબર થાય છે, ત્યારે આપણે જાણીએ છીએ કે આપણે BST માં K-th નાના તત્વ પર છીએ.

કોડ

બીએસટીમાં K-th નાનું તત્વ શોધવા માટે સી ++ કોડ
#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
બીએસટીમાં K-th નાનું તત્વ શોધવા માટે જાવા કોડ
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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન), કારણ કે કે-થ્રી તત્વ સુધી પહોંચવા માટે પહેલા તમારે કે -1 તત્વોને પસાર કરવાની જરૂર છે. અને આમ પણ જો kth તત્વ મૂળ હતું, તો આપણે ડાબી સબટ્રીના બધા તત્વોમાંથી પસાર થવું પડશે.

અવકાશ જટિલતા

ઓ (એચ),  અહીં આ જગ્યાની જટિલતા પુનરાવર્તનને કારણે છે. તેમ છતાં આખા પ્રોગ્રામમાં રેખીય અવકાશ જટિલતા છે. ઓલ્ગોરિધમ પોતે ઓ (એચ) જગ્યામાં ચાલે છે.