BST에서 k 번째로 작은 요소 찾기 (BST의 주문 통계)

난이도 중급
자주 묻는 질문 수행자 아마존 구글
이진 검색 트리 이진 트리 나무조회수 58

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

"에서 k 번째로 작은 요소를 찾으십시오. BST (BST의 주문 통계)”문제는 이진 검색 트리가 주어졌고 BST에서 k 번째로 작은 숫자를 찾아야한다고 말합니다. 이것은 우리가 순서대로 이진 검색 트리를 탐색하고 결과를 벡터 / an 배열에 저장합니다. 그러면 인덱스 (k-1)에있는 요소는 0 기반 인덱싱을 고려하면 k 번째로 작은 요소가됩니다.

입력

 

BST에서 k 번째로 작은 요소 찾기 (BST의 주문 통계)

k = 4

6

설명 : 주어진 이진 트리를 순서대로 순회하면 {2, 4, 5, 6, 8, 9}를 얻습니다. 따라서 여기에서 4 번째로 작은 요소 인 6을 찾아야합니다. 따라서 출력은 6입니다.

접근

증강 트리 데이터 구조

이 접근 방식에서는 각 노드가 왼쪽 하위 트리에 요소를 저장한다고 생각합니다. 트리를 구축하는 동안 각 노드의 왼쪽 하위 트리에있는 요소를 유지합니다. 이 사실은 트리에서 k 번째로 작은 요소를 찾는 데 사용됩니다. 따라서 k 번째 요소를 찾으려고 할 때 왼쪽 하위 트리에 k보다 많은 요소가 있는지 확인합니다. 그러면 k 번째로 작은 요소가 왼쪽 하위 트리에 있고 그렇지 않으면 오른쪽 하위 트리에 있습니다. 이것이 BST에서 k 번째로 작은 원소를 찾는 방법입니다.

암호

BST에서 k 번째로 작은 요소를 찾는 C ++ 코드
#include <bits/stdc++.h>
using namespace std;

struct node{
    int data;
    int leftCnt;
    node *left;
    node *right;
} ;

node* create(int data){
    node * tmp = new node();
    tmp->data = data;
    tmp->leftCnt = 0;
    tmp->left = tmp->right = NULL;
    return tmp;
}

node* insert(node* root, int x)
{
    if (root == NULL)
        return create(x);
    // we do the same as done to insert an element in the BST
    // but if we insert an element in the left sub-tree
    // we increment the count of nodes in left sub-tree as well
    if(x<root->data){
        root->left = insert(root->left, x);
        root->leftCnt++;
    }
    else if(x>root->data)
        root->right = insert(root->right, x);
    return root;
}


node* findKthSmallest(node *root, int k)
{
    if (!root)
        return NULL;

    int cnt = root->leftCnt+1;

    // current node is the k-th smallest element
    if(cnt == k)
        return root;
    else if(k > cnt)
        return findKthSmallest(root->right, k-cnt);
    else
        return findKthSmallest(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 = findKthSmallest(root, k);
    if(res == NULL)
        cout<<"No kth smallest found";
    else
        cout<<"Kth smallest element is "<<res->data;
}
6
5 4 2 8 6 9
4
6
BST에서 k 번째로 작은 요소를 찾는 Java 코드
import java.util.*;
import java.lang.*;
import java.io.*;

class node{
  int data;
  int leftCnt;
  node left;
  node right;
}

class Tree{
  static node root;
  
  static node create(int data){
      node tmp = new node();
      tmp.data = data;
      tmp.leftCnt = 0;
      tmp.left = null;
      tmp.right = null;
      return tmp;
  }
  
  static node insert(node root, int x)
  {
      if (root == null)
          return create(x);
      // we do the same as done to insert an element in the BST
      // but if we insert an element in the left sub-tree
      // we increment the count of nodes in left sub-tree as well
      if(x<root.data){
          root.left = insert(root.left, x);
          root.leftCnt++;
      }
      else if(x>root.data)
          root.right = insert(root.right, x);
      return root;
  }
  
  
  static node findKthSmallest(node root, int k)
  {
      if (root == null)
          return null;
  
      int cnt = root.leftCnt+1;
  
      // current node is the k-th smallest element
      if(cnt == k)
          return root;
      else if(k > cnt)
          return findKthSmallest(root.right, k-cnt);
      else
          return findKthSmallest(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();
      node res = findKthSmallest(root, k);
      if(res == null)
          System.out.println("No kth smallest found");
      else
          System.out.println("Kth smallest element is "+res.data);
  }
}
6
5 4 2 8 6 9
4
Kth smallest element is 6

복잡성 분석

시간 복잡성

오), 최악의 경우 H는 입력으로 기울어 진 트리가 있고 N 번째로 작은 요소를 찾아야하는 경우 N과 같을 수 있습니다.

공간 복잡성

오), 여기에서는 leftCnt가 왼쪽 하위 트리의 노드 수를 계산하는 데 필요한 공간을 고려하지 않습니다. leftCnt가 트리의 일부이므로 O (H) 공간이 재귀에 필요한 공간이라고 생각합니다.

중위 순회

"BST에서 k 번째로 작은 요소 찾기 (BST의 주문 통계)"는 이진 검색 트리의 순차 순회가 오름차순으로 노드를 순회하기 때문에 순회 순회를 사용하여 해결할 수 있습니다. 따라서 카운트 변수를 유지할 수 있습니다. 이 카운트 변수가 k와 같으면 BST에서 k 번째로 작은 요소에 있다는 것을 알 수 있습니다.

암호

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* findKthSmallest(node* root, int& k)
{
    // base case
    if(!root)
        return NULL;
    node *left = findKthSmallest(root->left, k);
    if(left)
        return left;
    // if current element is kth smallest
    if(k==1)
        return root;
    // if the kth smallest is not found in the left subtree
    // search in right subtree
    k--;
    return findKthSmallest(root->right, 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 = findKthSmallest(root, k);
    if(res == NULL)
        cout<<"No kth smallest found";
    else
        cout<<"Kth smallest element is "<<res->data;
}
6
5 4 2 8 6 9
4
Kth smallest element is 6
BST에서 k 번째로 작은 요소를 찾는 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 findKthSmallest(node root, int k)
  {
      // base case
      if(root == null)
          return null;
      node left = findKthSmallest(root.left, k);
      if(left != null)
          return left;
      count++;
      // if current element is kth smallest
      if(k==count)
          return root;
      // if the kth smallest is not found in the left subtree
      // search in right subtree
      return findKthSmallest(root.right, 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 = findKthSmallest(root, k);
      if(res == null)
          System.out.println("No kth smallest found");
      else
          System.out.println("Kth smallest element is "+res.data);
  }
}
6
5 4 2 8 6 9
4
Kth smallest element is 6

복잡성 분석

시간 복잡성

의 위에), k 번째 요소에 도달하려면 먼저 k-1 요소를 횡단해야합니다. 따라서 k 번째 요소가 루트 인 경우에도 왼쪽 하위 트리의 모든 요소를 ​​통과해야합니다.

공간 복잡성

오),  여기서이 공간 복잡성은 재귀 때문입니다. 전체 프로그램에는 선형 공간 복잡성이 있지만. 알고리즘 자체는 O (H) 공간에서 실행됩니다.

균열 시스템 설계 인터뷰
Translate »