BST 수정이 허용되지 않는 경우 BST에서 K '번째로 큰 요소

난이도 중급
자주 묻는 질문 아마존 시스코 구글 UHG 옵텀
이진 검색 트리 이진 트리 나무조회수 24

문제 정책

"BST 수정이 허용되지 않는 경우 BST에서 K 번째로 큰 요소"는 이진 검색 트리가 제공되고 k 번째로 큰 요소를 찾아야 함을 나타냅니다. 이것은 이진 검색 트리의 모든 요소가 내림차순으로 배열 될 때를 의미합니다. 그런 다음 시퀀스에서 k 번째 요소를 반환해야합니다.

입력

BST 수정이 허용되지 않는 경우 BST에서 K '번째로 큰 요소

k = 4

3

설명 : 나무의 이미지는 위에 표시됩니다. 그리고 우리는 4 번째로 큰 요소를 찾아야합니다. 따라서 오름차순으로 정렬하면 {1, 2, 3, 4, 5, 6}이됩니다. 따라서 네 번째로 큰 요소는 세 번째로 작은 요소입니다. 따라서 4을 출력으로 반환합니다.

BST 수정이 허용되지 않는 경우 BST에서 K '번째로 큰 요소를 찾는 방법

우리는 이미 비슷한 질문을했습니다. k 번째로 작은 요소 BST에서. 문제는 그것에 대한 수정일뿐입니다. 이전 게시물에서 해당 질문에 대한 솔루션에 대해 논의했습니다. 첫 번째 방법은 트리 데이터 구조를 수정하는 것이 었습니다. 다른 하나는 이진 검색 트리에 대해 순서대로 순회를 실행하고 노드를 계속 계산하는 것입니다. 이전 질문은 k 번째 작은 값을 반환하는 것이 었습니다. 우리는 단순히 노드 수를 세고 그 수가 k와 같으면 해당 노드의 값을 반환했습니다.

순진한 접근

여기 상황이 조금 다릅니다. k 번째로 큰 요소를 찾아야합니다. 먼저 트리에서 총 노드 수를 찾은 다음 총 노드 수에서 k-1을 뺍니다. 이제 n-k + 1 가장 작은 노드를 찾습니다. 여기서 n은 이진 검색 트리의 총 노드 수입니다. 하지만이 방법은 두 번 또는 두 번 순회 나무 위에.

효율적인 접근

내림차순으로 노드를 찾을 수 있다면 효율적으로 문제를 해결할 수 있습니다. 이렇게하면 트리에서 총 노드 수를 찾을 필요가 없습니다. 효율적인 접근 방식은 트리를 역 순회하는 것입니다. 이진 검색 트리의 역 순회는 트리를 내림차순으로 순회합니다. 따라서 역순으로 수행하는 동안 노드 수를 계속 계산합니다. 카운트가 k가되면 해당 노드의 값을 반환합니다.

암호

BST 수정이 허용되지 않는 경우 BST에서 K 번째로 큰 요소를 찾는 C ++ 코드

#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 수정이 허용되지 않을 때 BST에서 K'th 가장 큰 요소를 찾는 Java 코드

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, BST에는 N 개의 노드 만 있기 때문에. 우리는 O (N)의 선형 시간 복잡도를 달성했습니다.

공간 복잡성

O (1), 우리는 일정한 여분의 공간만을 사용했습니다. 따라서이 알고리즘 만 일정한 공간 복잡성을 갖지만 프로그램 전체는 선형 공간 복잡성을가집니다. N 개의 이진 트리 노드를 저장하고 있기 때문입니다.

Translate »