일정한 추가 공간을 사용하는 BST에서 K'th 가장 큰 요소-TutorialCup

차례

문제 정책

“상수 추가 공간을 사용하는 BST에서 K '번째로 큰 요소 "는 이진 검색 트리가 주어졌고 그 안에서 k 번째로 큰 요소를 찾아야한다고 말합니다. 따라서 이진 검색 트리의 요소를 내림차순으로 배열하면 시퀀스에서 k 번째 숫자를 반환해야합니다.

예

핀

k = 4

설명 : 요소가 내림차순으로 배열 된 경우 순서는 [6, 5, 4, 3, 2, 1]입니다. 이제 네 번째로 큰 요소는 네 번째 인덱스의 요소 인 3입니다.

일정한 추가 공간을 사용하여 BST에서 K '번째로 큰 요소를 찾는 방법

순진한 접근

먼저 저장하여이 문제를 해결할 수 있습니다. 순서 순회 그런 다음 시퀀스에서 n-k + 1 요소를 찾으면 문제에 대한 답을 얻을 수 있습니다. 그러나이 접근 방식은 O (N) 공간 복잡성을 갖습니다. 또한 역 순회를 수행하고 노드 수를 계산하는보다 효율적인 솔루션에 대해서도 논의했습니다. 노드를 세는 동안 노드 수가 k와 같은지 확인했습니다. 노드 수가 k와 같으면 노드를 반환합니다. 그렇지 않으면 결국 k 번째로 큰 노드를 찾을 수 없다는 메시지를 반환합니다.

효율적인 접근

. 이전 접근법, 우리는 재귀를 위해 O (H) 공간이 필요한 역 순회를 사용했습니다. 우리는 inorder traversal에서했던 것과 같은 일을 할 수 있습니다. 우리가 inorder traversal을 뒤집었을 때. O (1) 공간에서 inorder traversal을 수행하기 위해 Morris traversal을 사용할 것입니다. 하지만 단순히 이렇게하는 대신 Morris Traversal을 사용하여 역 순회 순회를 수행합니다.

Morris Traversal은 이진 스레드 트리에서 사용되며, 이진 스레드 트리는 추가 스레드가있는 이진 트리 일뿐입니다. 이렇게하면 트리에서 순회를 쉽게 수행 할 수 있습니다. Reverse Morris Traversal은 Morris Traversal 일 뿐이지 만 반대 방식입니다. 일반적인 모리스 순회에서는 먼저 왼쪽 하위 트리로 이동 한 다음 오른쪽 하위 트리로 이동했을 것입니다. 그러나 여기서 먼저 오른쪽 하위 트리로 이동 한 다음 왼쪽 하위 트리로 이동합니다. 이 방법은 내림차순으로 순회를 수행 할 수 있습니다. 그런 다음 처음부터 k 번째 요소를 반환합니다. 즉, 개수를 유지하고 개수가 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* findKthLargest(node* root, int k)
{
    node *cur = root; node* kLargest = NULL;
    int cnt = 0;

    while(cur != NULL){
        // if right subtree is NULL, then move to left subtree
        if(cur->right == NULL){
            // if current node is kth largest
            if(cnt == k-1)
                kLargest = cur;
            cnt++;
            // move to the left subtree
            cur = cur->left;
        }
        else{
            // to find successor of current node
            node* successor = cur->right;

            while(successor->left != NULL && successor->left != cur)
                successor = successor->left;

            if(successor->left == NULL){
                // set current node as left child of successor as it doesn't have left child
                successor->left = cur;
                    cur = cur->right;
            }
            else{
                // remove threads to restore the original tree
                successor->left = NULL;
                if(cnt == k-1)
                    kLargest = cur;
                cnt++;
                cur = cur->left;
            }
        }
    }
    return kLargest;
}
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에서 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)
  {
      node cur = root; node kLargest = null;
      int cnt = 0;
  
      while(cur != null){
          // if right subtree is NULL, then move to left subtree
          if(cur.right == null){
              // if current node is kth largest
              if(cnt == k-1)
                  kLargest = cur;
              cnt++;
              // move to the left subtree
              cur = cur.left;
          }
          else{
              // to find successor of current node
              node successor = cur.right;
  
              while(successor.left != null && successor.left != cur)
                  successor = successor.left;
  
              if(successor.left == null){
                  // set current node as left child of successor as it doesn't have left child
                  successor.left = cur;
                      cur = cur.right;
              }
              else{
                  // remove threads to restore the original tree
                  successor.left = null;
                  if(cnt == k-1)
                      kLargest = cur;
                  cnt++;
                  cur = cur.left;
              }
          }
      }
      return kLargest;
  }
  
  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

복잡성 분석

시간 복잡성

의 위에), 우리는 한때 트리의 모든 요소를 순회했기 때문입니다. 시간 복잡도는 선형, 즉 O (N)입니다.

공간 복잡성

O (1), 순회를 재귀 적으로 수행하는 대신 morris 순회를 사용했기 때문입니다.

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