BST-də dəyişiklik edilməsinə icazə verilmədiyi zaman BST-də ən böyük element

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Cisco google UHG Optum
İkili Axtarış Ağacı İkili ağac AğacBaxılıb 25

Problem bəyanat

"BST-də dəyişiklik edilməsinə icazə verilmədiyi zaman BST-də ən böyük element" sizə ikili axtarış ağacı verildiyini və kth ən böyük elementi tapmaq lazım olduğunu bildirir. Bu, ikili axtarış ağacının bütün elementlərinin azalan sıraya yerləşdiyi zaman deməkdir. Sonra kth elementini ardıcıllıqdan qaytarmalıyıq.

misal

Input

BST-də dəyişiklik edilməsinə icazə verilmədiyi zaman BST-də ən böyük elementPin

k = 4

3

İzahat: Ağacın şəkli yuxarıda göstərilmişdir. Və ən böyük 4-cü elementi tapmaq lazımdır. Beləliklə, onları artan qaydada düzəltsək, onlar {1, 2, 3, 4, 5, 6}. Deməli, 4-cü ən böyük element 3-cü kiçik elementdir. Beləliklə, 3-ü nəticə olaraq qaytarırıq.

BST-də dəyişiklik edilməsinə icazə verilmədikdə BST-də K'th Ən Böyük Elementi tapmaq üçün yanaşma

Bənzər bir sualı artıq harada tapdıq k-ci ən kiçik element BST-də. Problem yalnız bunun üzərində bir dəyişiklikdir. Əvvəlki yazıda, bu sualın həllərini müzakirə etdik. İlk yanaşma ağac məlumat quruluşunu dəyişdirmək idi. Digəri isə ikili axtarış ağacı üçün nizamlı bir keçid aparmaq və qovşaqları saymağa davam etmək idi. Əvvəlki sual k-ı ən kiçik qaytarmaq idi. Sadəcə qovşaq sayını saydıq və say k-yə bərabər olduqda həmin qovşaqdakı dəyəri qaytardıq.

Sadəlövh yanaşma

Burada vəziyyət bir az fərqlidir. K ən böyük elementi tapmalıyıq, əvvəlcə ağacdakı qovşaqların ümumi sayını tapa bilərik və sonra ümumi qovşaq sayından k-1 çıxardırıq. İndi n-k + 1 ən kiçik qovşaq tapırıq, burada n ikili axtarış ağacındakı qovşaqların ümumi sayıdır. Ancaq bu yanaşma iki və ya iki keçid tələb edəcəkdir keçidlər ağacın üstündə.

Səmərəli yanaşma

Düyünləri azalan qaydada tapa bilsək, problemi səmərəli şəkildə həll edə bilərik. Bu şəkildə ağacdakı ümumi qovşaq sayını tapmaq lazım olmayacaq. Səmərəli bir yanaşma, ağacın tərs istiqamətdən keçməsini etmək olacaq. İkili axtarış ağacının tərs tərs keçidi, azalan qaydada ağacdan keçir. Buna görə tərs qaydada edərkən qovşaqları saymağa davam edəcəyik. və say k-ya bərabər olduqda, həmin qovşaqdakı dəyəri qaytarırıq.

Kodu

BST-də dəyişiklik edilməsinə icazə verilmədikdə BST-də K'th Ən Böyük Elementi tapmaq üçün C ++ kodu

#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

BST-də dəyişiklik edilməsinə icazə verilmədikdə BST-də K'th Ən Böyük Elementi tapmaq üçün Java kodu

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

Mürəkkəblik təhlili

Zamanın mürəkkəbliyi

O (N), çünki sadəcə yolu keçdik BSTvə BST-dən bəri yalnız N düyünü var idi. O (N) xətti bir zaman mürəkkəbliyinə nail olduq.

Kosmik Mürəkkəblik

O (1), yalnız daimi əlavə yerdən istifadə etdik. Beləliklə, yalnız bu alqoritm daimi kosmik mürəkkəbliyə malikdir, lakin proqram bütövlükdə xətti kosmik mürəkkəbliyə malikdir. Çünki N ikili ağac düyünlərini saxlayırıq.

Translate »