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

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

Twitter Facebook 링크드인 버퍼 레딧 텀블러

차례

문제 정책

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

예

입력

핀

k = 4

설명 : 주어진 이진 트리를 순서대로 순회하면 {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

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 번째로 작은 요소에 있다는 것을 알 수 있습니다.

암호