જ્યારે બીએસટીમાં ફેરફાર કરવાની મંજૂરી નથી ત્યારે બીએસટીમાં સૌથી મોટો એલિમેન્ટ છે


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

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

"જ્યારે બીએસટીમાં ફેરફાર કરવાની મંજૂરી નથી ત્યારે બીએસટીમાં સૌથી મોટો એલિમેન્ટ" તમને જણાવે છે કે તમને બાઈનરી સર્ચ ટ્રી આપવામાં આવે છે અને તમારે kth સૌથી મોટું તત્ત્વ શોધવાની જરૂર છે. આનો અર્થ એ છે કે જ્યારે બાઈનરી સર્ચ ટ્રીના બધા તત્વો ઉતરતા ક્રમમાં ગોઠવાય છે. પછી આપણે ક્રમમાંથી kth એલિમેન્ટ પાછા આપવાની જરૂર છે.

ઉદાહરણ

ઇનપુટ

જ્યારે બીએસટીમાં ફેરફાર કરવાની મંજૂરી નથી ત્યારે બીએસટીમાં સૌથી મોટો એલિમેન્ટ છે

કે = 4

3

સમજૂતી: ઉપર વૃક્ષની છબી બતાવવામાં આવી છે. અને આપણે 4 મો સૌથી મોટો તત્વ શોધવાની જરૂર છે. તેથી જો આપણે તેમને ચડતા ક્રમમાં ગોઠવીએ, તો તે {1, 2, 3, 4, 5, 6} છે. તેથી ચોથું સૌથી મોટું તત્વ 4 જી સૌથી નાનું તત્વ છે. આમ આપણે આઉટપુટ તરીકે 3 પરત કરીએ છીએ.

જ્યારે બીએસટીમાં ફેરફાર કરવાની મંજૂરી ન હોય ત્યારે બીએસટીમાં કthથ લ Larસ્ટ એલિમેન્ટ શોધવાનો અભિગમ

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

નિષ્કપટ અભિગમ

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

કાર્યક્ષમ અભિગમ

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

કોડ

જ્યારે બીએસટીમાં ફેરફાર કરવાની મંજૂરી નથી ત્યારે બીએસટીમાં કેથથ સૌથી મોટા ઘટક શોધવા માટે સી ++ કોડ

#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

જ્યારે બીએસટીમાં ફેરફાર કરવાની મંજૂરી ન હોય ત્યારે બીએસટીમાં કેથ સૌથી મોટા ઘટક શોધવા માટે જાવા કોડ

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

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

સમય જટિલતા

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

અવકાશ જટિલતા

ઓ (1), અમે ફક્ત સતત વધારાની જગ્યાનો ઉપયોગ કર્યો છે. આમ ફક્ત આ અલ્ગોરિધમમાં સતત જગ્યા જટિલતા હોય છે પરંતુ સમગ્ર પ્રોગ્રામમાં રેખીય જગ્યા જટિલતા હોય છે. કારણ કે અમે એન બાઈનરી ટ્રી ગાંઠો સ્ટોર કરીએ છીએ.