在BST中查找第k個最小元素(BST中的訂單統計信息)


難度級別
經常問 ol石 亞馬遜 谷歌
二進制搜索樹 二叉樹

問題陳述

“找到第k個最小的元素 BST (“ BST中的訂單統計信息”)問題指出,您獲得了一個二進制搜索樹,需要在BST中找到第k個最小的數字。 這意味著如果我們做一個 為了 遍歷二叉搜索樹並將結果存儲在vector / an數組中。 如果考慮基於1的索引,則索引(k-0)處的元素將是第k個最小元素。

輸入

 

在BST中查找第k個最小元素(BST中的訂單統計信息)

k = 4

6

說明:如果對給定的二叉樹進行有序遍歷,則會得到{2,4,5,6,8,9}。 因此,在這裡,我們需要找到第4個最小的元素,即6。因此,輸出為6。

途徑

增強樹數據結構

在這種方法中,我們認為每個節點都將元素存儲在其左子樹中。 在構建樹時,我們將元素保留在每個節點的左子樹中。 此事實用於查找樹中的第k個最小元素。 因此,當我們嘗試找到第k個元素時,我們會檢查左子樹是否包含比k個更多的元素。 然後,我們的第k個最小元素位於左側子樹中,否則位於右側子樹中。 這就是我們在BST中找到第k個最小元素的方式。

推薦碼

C ++代碼在BST中找到第k個最小的元素
#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代碼在BST中找到第k個最小的元素
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

複雜度分析

時間複雜度

哦),在最壞的情況下,如果我們有一個傾斜的樹作為輸入並且我們需要找到第N個最小元素,則H可以等於N。

空間複雜度

哦), 這裡我們沒有考慮leftCnt用來計算左子樹中節點數的空間。 我們認為leftCnt是樹的一部分,因此O(H)空間是遞歸所需的空間。

有序遍歷

可以使用順序遍歷來解決“在BST中查找第k個最小元素(BST中的順序統計量)”,因為二進制搜索樹的順序遍歷以遞增順序遍歷節點。 因此,我們可以保留一個count變量。 當此計數變量等於k時,我們知道我們處於BST中的第k個最小元素。

推薦碼

C ++代碼在BST中找到第k個最小的元素
#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代碼在BST中找到第k個最小的元素
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)空間中運行。