Найдите k-й наименьший элемент в BST (Статистика заказов в BST)


Сложный уровень средний
Часто спрашивают в Акколит Амазонка Google
Двоичное дерево поиска Двоичное дерево дерево

Постановка задачи

«Найдите k-й наименьший элемент в BST (Статистика заказов в BST) ”проблема заключается в том, что вам дано двоичное дерево поиска и вам нужно найти k-е наименьшее число в BST. Это означает, что если мы в целях обход двоичного дерева поиска и сохранение результата в векторе / массиве. Тогда элемент с индексом (k-1) будет k-м наименьшим, если мы рассмотрим индексирование на основе 0.

Пример

вход

 

Найдите k-й наименьший элемент в BST (Статистика заказов в BST)

k = 4

6

Объяснение: Если мы выполним обход данного двоичного дерева по порядку, мы получим {2, 4, 5, 6, 8, 9}. Итак, здесь нам нужно найти 4-й наименьший элемент, то есть 6. Таким образом, на выходе будет 6.

Подход

Расширенная древовидная структура данных

В этом подходе мы считаем, что каждый узел хранит элемент в своем левом поддереве. При построении дерева мы сохраняем элементы в левом поддереве каждого узла. Этот факт используется для нахождения k-го наименьшего элемента в дереве. Поэтому, когда мы пытаемся найти k-й элемент, мы проверяем, имеет ли левое поддерево больше элементов, чем k. Тогда наш k-й наименьший элемент лежит в левом поддереве, иначе он лежит в правом поддереве. Так мы находим k-й наименьший элемент в BST.

Код:

Код C ++ для поиска k-го наименьшего элемента в BST
#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
Код Java для поиска k-го наименьшего элемента в BST
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) - это пространство, необходимое для рекурсии.

Inorder Traversal

«Найти k-й наименьший элемент в BST (статистика порядка в BST)» может быть решен с использованием обхода в порядке, поскольку обход дерева двоичного поиска проходит по узлам в возрастающем порядке. Таким образом, мы можем сохранить счетную переменную. Когда эта переменная count становится равной k, мы знаем, что находимся на k-м наименьшем элементе в BST.

Код:

Код C ++ для поиска k-го наименьшего элемента в BST
#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
Код Java для поиска k-го наименьшего элемента в BST
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).