БСТде эң кичинекей элементти табыңыз (БСТтеги статистика)


Кыйынчылык деңгээли орто
Көп суралган Accolite Amazon Гугл
Binary Search Tree Binary Tree дарак

Маселени билдирүү

“К-деги эң кичинекей элементти табыңыз BST (Order Statistika in BST) ”көйгөйүндө экилик издөө дарагы берилгендиги жана сиз BSTдеги k-чи кичинекей санды табууңуз керек экени айтылат. Эгерде биз ан тартипте экилик издөө дарагынын өтүшү жана натыйжаны вектордо / массивде сактоо. Эгерде индекстеги элемент (k-1), эгерде 0 негизделген индекстөөнү алсак, k кичине болот.

мисал

кирүү

 

БСТде эң кичинекей элементти табыңыз (БСТтеги статистика)

k = 4

6

Түшүндүрмө: Берилген экилик дарактын тартиби боюнча өтсөк, биз {2, 4, 5, 6, 8, 9} алабыз. Ошентип, биз 4-орунду ээлеген 6-кичинекей элементти табышыбыз керек. Ошентип, жыйынтык 6га жетет.

жакындоо

Кошумча дарактардын маалымат түзүмү

Мындай ыкма менен, ар бир түйүн элементти сол сол дарагында сактайт деп эсептейбиз. Бак-даракты курууда биз ар бир түйүндүн сол теректериндеги элементтерди сактап калабыз. Бул факт дарактын k-чи элементин табуу үчүн колдонулат. Ошентип, kth элементин табууга аракет кылганда, эгерде сол субтрактын 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

Комплекстик анализ

Убакыт татаалдыгы

O (H), эгерде биз кыйшайган даракты алып, N-кичинекей элементти табышыбыз керек болсо, эң начар учурда H Nге барабар болот.

Космостун татаалдыгы

O (H), бул жерде биз сол subtreeдеги түйүндөрдүн санын эсептөө үчүн leftCnt талап кылган орунду эсептебейбиз. Биз leftCnt дарактын бир бөлүгү деп эсептейбиз, ошондуктан O (H) мейкиндиги рекурсия талап кылган орун болуп саналат.

Inorder Traversal

“BSTдеги k-чи кичинекей элементти табуу (БСТтеги Статистиканын статистикасы)” инордералдык өтмөктүн жардамы менен чечүүгө болот, анткени экилик издөө дарагынын инератордук өтүшү түйүндөрдү көбөйүп бараткан тартипте өтөт. Ошентип, биз санап турган өзгөрмө сактай алабыз. Бул эсептөө өзгөрмөсү kге барабар болгондо, биз BSTдеги эң кичинекей элементте экенибизди билебиз.

коду

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

Комплекстик анализ

Убакыт татаалдыгы

O (N), анткени k-элементине жетүү үчүн k-1 элементтерин кыдырып өтүшүбүз керек. Ошентип kth элементи тамыр болсо дагы, биз сол субтрактын бардык элементтерин аралап өтүшүбүз керек.

Космостун татаалдыгы

O (H),  бул жерде космостогу татаалдык рекурсияга байланыштуу. Программанын бардыгы сызыктуу космостук татаалдыкка ээ болсо дагы. Алгоритм өзү O (H) мейкиндигинде иштейт.