K'th Խոշորագույն տարրը BST- ում, երբ BST- ում փոփոխություն չի թույլատրվում


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Amazon Cisco Google UHG Optum
Երկուական որոնման ծառ Երկուական ծառ ծառ

Խնդիրի հայտարարություն

«K'th Խոշորագույն տարրը BST- ում, երբ փոփոխություն չի թույլատրվում BST- ում» նշում է, որ ձեզ տրվում է երկուական որոնման ծառ և դուք պետք է գտնեք kth ամենամեծ տարրը: Սա նշանակում է, որ երբ երկուական որոնման ծառի բոլոր տարրերը դասավորված են նվազման կարգով: Դրանից հետո մենք պետք է վերադարձնենք kth տարրը հաջորդականությունից:

Օրինակ

Մուտքային

K'th Խոշորագույն տարրը BST- ում, երբ BST- ում փոփոխություն չի թույլատրվում

k = 4

3

Բացատրություն. Theառի պատկերը ցույց է տրված վերևում: Եվ մենք պետք է գտնենք ամենամեծ 4-րդ տարրը: Այսպիսով, եթե դրանք դասավորենք աճման կարգով, դրանք {1, 2, 3, 4, 5, 6} են: Այսպիսով, 4-րդ ամենամեծ տարրը 3-րդ ամենափոքր տարրն է: Այսպիսով, մենք վերադարձնում ենք 3-ը որպես արդյունք:

BST- ում K'th Largest Element- ին գտնելու մոտեցում, երբ BST- ի փոփոխումը թույլատրված չէ

Մենք արդեն արել ենք նմանատիպ հարց, որտեղ գտել ենք այն k- րդ ամենափոքր տարրը BST- ում: Խնդիրն ընդամենը դրա փոփոխությունն է: Նախորդ հաղորդագրության մեջ մենք քննարկեցինք այդ հարցի լուծումները: Առաջին մոտեցումը ծառի տվյալների կառուցվածքի փոփոխումն էր: Մինչ մյուսը պետք է կատարեր կարգի անցում երկուական որոնման ծառի համար և շարունակեր հաշվել հանգույցները: Քանի որ նախորդ հարցն էր վերադարձնել ամենափոքրը: Մենք պարզապես հաշվեցինք հանգույցների քանակը, և երբ հաշվարկը հավասարվեց k- ին, մենք վերադարձրեցինք այդ հանգույցի արժեքը:

Միամիտ մոտեցում

Այստեղ իրավիճակը մի փոքր այլ է: Մենք պետք է գտնենք kth ամենամեծ տարրը, մենք նախ կարող ենք գտնել ծառի հանգույցների ընդհանուր քանակը, իսկ այնուհետև հանգույցների ընդհանուր քանակից հանել k-1: Այժմ մենք գտնում ենք n-k + 1 ամենափոքր հանգույցը, որտեղ n- ը երկուական որոնման ծառի հանգույցների ընդհանուր թիվն է: Բայց այս մոտեցման համար անհրաժեշտ կլինի երկու կամ երկու փոխանցում անցումներ ծառի վրայով:

Արդյունավետ մոտեցում

Մենք կարող ենք արդյունավետորեն լուծել խնդիրը, եթե կարողանանք հանգույցները նվազման կարգով գտնել: Այդ կերպ մեզ պետք չի լինի գտնել ծառի հանգույցների ընդհանուր քանակը: Արդյունավետ մոտեցում կլինի ծառի հակադարձ անշարժ շրջանցումը: Երկուական որոնման ծառի հակառակ շրջադարձի անցումը ծառը հատում է նվազման կարգով: Հակառակ կարգը կատարելիս մենք կշարունակենք հաշվել հանգույցները: և երբ հաշվարկը հավասար է k- ին, մենք այդ հանգույցի վրա վերադարձնում ենք արժեքը:

Կոդ

C ++ կոդ ՝ BST- ում K'th Largest Element- ը գտնելու համար, երբ BST- ի փոփոխումը թույլատրված չէ

#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

Java- ի կոդ `BST- ում K'th Largest Element- ը գտնելու համար, երբ BST- ի փոփոխումը թույլատրված չէ

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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ մենք պարզապես անցել ենք BST- ը, և քանի որ BST– ն ուներ միայն N հանգույց: Մենք հասել ենք O (N) - ի գծային ժամանակի բարդությանը:

Տիեզերական բարդություն

O (1), մենք օգտագործել ենք միայն անընդհատ լրացուցիչ տարածք: Այսպիսով, միայն այս ալգորիթմն ունի անընդհատ տիեզերական բարդություն, բայց ծրագիրն, ընդհանուր առմամբ, ունի գծային տիեզերական բարդություն: Քանի որ մենք պահպանում ենք N երկուական ծառի հանգույցներ: