जेव्हा बीएसटीमध्ये बदल करण्यास अनुमती नसते तेव्हा बीएसटीमधील सर्वात मोठा घटक  


अडचण पातळी मध्यम
वारंवार विचारले ऍमेझॉन सिस्को Google यूएचजी ऑप्टम
बायनरी शोध वृक्ष बायनरी ट्री झाड

समस्या विधान  

“जेव्हा बीएसटीमध्ये बदल करण्याची परवानगी नसते तेव्हा बीएसटीमधील केथचा सर्वात मोठा घटक” असे सांगते की आपणास बायनरी शोध वृक्ष देण्यात आला आहे आणि आपल्याला सर्वात मोठा घटक शोधण्याची आवश्यकता आहे. याचा अर्थ असा की जेव्हा बायनरी शोध वृक्षाचे सर्व घटक उतरत्या क्रमाने व्यवस्थित केले जातात. नंतर आपल्याला अनुक्रमातून kth घटक परत करणे आवश्यक आहे.

उदाहरण  

इनपुट

जेव्हा बीएसटीमध्ये बदल करण्यास अनुमती नसते तेव्हा बीएसटीमधील सर्वात मोठा घटकपिन

के = 4

3

स्पष्टीकरणः झाडाची प्रतिमा वर दर्शविली आहे. आणि आपल्याला 4 था सर्वात मोठा घटक शोधण्याची आवश्यकता आहे. म्हणून जर आम्ही त्यांना चढत्या क्रमाने व्यवस्थित केले तर ते {1, 2, 3, 4, 5, 6} आहेत. तर 4 था सर्वात मोठा घटक 3 रा सर्वात लहान घटक आहे. हे आऊटपुट म्हणून 3 परत करेल.

जेव्हा बीएसटीमध्ये बदल करण्याची परवानगी नसते तेव्हा बीएसटीमध्ये के ला सर्वात मोठा घटक शोधण्याचा दृष्टीकोन  

आम्ही आधीपासून असा प्रश्न केला आहे, जिथे आम्हाला तो सापडला के-व्या सर्वात लहान घटक बीएसटी मध्ये समस्या त्या प्रती फक्त एक बदल आहे. मागील पोस्टमध्ये आम्ही त्या प्रश्नावरील उपायांवर चर्चा केली. प्रथम दृष्टिकोन वृक्ष डेटा संरचना सुधारित करण्याचा होता. दुसरे बायनरी शोध वृक्षासाठी ऑर्डर ट्रॅव्हर्सल चालवत असताना आणि नोड्स मोजतच राहिले. मागील प्रश्न सर्वात छोटा परत परत करण्याचा होता. आम्ही फक्त नोड्सची संख्या मोजली आणि एकदा गणना के बरोबर असल्यास आम्ही त्या नोडवरील मूल्य परत केले.

हे सुद्धा पहा
पालिंड्रोम क्रमांक

भोळे दृष्टिकोन

इथे परिस्थिती थोडी वेगळी आहे. आम्हाला kth सर्वात मोठा घटक शोधण्याची आवश्यकता आहे, आम्ही प्रथम झाडामध्ये एकूण नोड शोधू आणि नंतर नोड्सच्या एकूण संख्येमधून के -1 वजा करू. आता आम्हाला एन-के + 1 सर्वात छोटा नोड सापडला आहे, जिथे बायनरी शोध वृक्षात एकूण नोड्स आहेत. परंतु या दृष्टिकोनात दोन किंवा दोन पास आवश्यक आहेत ट्रॅव्हर्सल्स झाडावर

कार्यक्षम दृष्टीकोन

आम्हाला खाली उतरत्या क्रमाने नोड्स सापडल्यास आम्ही ही समस्या कार्यक्षमतेने सोडवू शकतो. अशा प्रकारे आम्हाला झाडामध्ये एकूण नोड्स शोधण्याची आवश्यकता नाही. झाडाची रिव्हर्स-इनऑर्डर ट्रॅव्हर्सल करणे हा एक कार्यक्षम दृष्टीकोन असेल. बायनरी शोध वृक्षाची रिव्हर्स इनऑर्डर ट्रॅव्हर्सल झाडास उतरत्या क्रमाने फिरवते. रिव्हर्स ऑर्डर करत असताना आम्ही नोडची मोजणी करत राहू. आणि जेव्हा गणना के समान होईल, आम्ही त्या नोडची व्हॅल्यू परत करू.

कोड  

जेव्हा बीएसटीमध्ये बदल करण्याची परवानगी नसते तेव्हा बीएसटीमध्ये के ला सर्वात मोठा घटक शोधण्यासाठी सी ++ कोड

#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

गुंतागुंत विश्लेषण  

वेळ कॉम्प्लेक्सिटी

ओ (एन), कारण आपण सहजपणे त्या मार्गावरुन गेलो आहोत BST, आणि बीएसटीकडे फक्त एन नोड्स असल्याने. आम्ही ओ (एन) ची रेषीय वेळची जटिलता प्राप्त केली आहे.

हे सुद्धा पहा
दिलेल्या श्रेणीतील मूल्यांसह अ‍ॅरे घटकांच्या संख्येसाठी क्वेरी

स्पेस कॉम्प्लेक्सिटी

ओ (1), आम्ही फक्त सतत अतिरिक्त जागा वापरली आहे. अशा प्रकारे केवळ या अल्गोरिदममध्ये निरंतर जागेची गुंतागुंत असते परंतु संपूर्ण कार्यक्रमात रेषात्मक अवघडपणा असते. कारण आम्ही एन बायनरी ट्री नोड्स साठवत आहोत.