Գտեք BST- ի k- րդ ամենափոքր տարրը (Պատվերի վիճակագրություն BST- ում)


Դժվարության մակարդակ Միջին
Հաճախակի հարցնում են Ակոլիտ Amazon Google
Երկուական որոնման ծառ Երկուական ծառ ծառ

Խնդիրի հայտարարություն

«Գտեք k- րդ ամենափոքր տարրը ներսում BST- ը (Պատվերի վիճակագրություն BST- ում) »խնդիրը նշում է, որ ձեզ տրվում է երկուական որոնման ծառ և անհրաժեշտ է գտնել BST- ի k- րդ ամենափոքր թիվը: Սա նշանակում է, եթե մենք անենք որպեսզի Երկուական որոնման ծառի անցում և արդյունքը պահեք վեկտորում / զանգվածում: Այդ դեպքում ինդեքսում գտնվող տարրը (k-1) կլինի ամենափոքրը, եթե հաշվի առնենք 0-ի վրա հիմնված ինդեքսավորումը:

Օրինակ

Մուտքային

 

Գտեք BST- ի k- րդ ամենափոքր տարրը (Պատվերի վիճակագրություն BST- ում)

կ = 4

6

Բացատրություն. Եթե մենք կատարում ենք տրված երկուական ծառի կարգի անցում, ապա մենք ստանում ենք {2, 4, 5, 6, 8, 9}: Այսպիսով, դրանում մենք պետք է գտնենք 4-րդ փոքրագույն տարրը, ապա դա 6-ն է: Այսպիսով, ելքը 6 է:

Մոտեցում

Լրացված ծառի տվյալների կառուցվածքը

Այս մոտեցման մեջ մենք համարում ենք, որ յուրաքանչյուր հանգույց տարրը պահպանում է իր ձախ ենթածառում: Buildingառը կառուցելիս մենք պահպանում ենք տարրերը յուրաքանչյուր հանգույցի ձախ ենթաթմբում: Այս փաստը օգտագործվում է ծառի մեջ 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

Բարդության վերլուծություն

Timeամանակի բարդություն

Ո (Հ), վատագույն դեպքում H- ը կարող է հավասար լինել N- ին, եթե որպես ներդրում ունենանք շեղված ծառ և պետք է գտնենք N- րդ փոքր տարրը:

Տիեզերական բարդություն

O (H), այստեղ մենք չենք համարում ձախ տարածքի պահանջվող տարածությունը ձախ ենթածառի հանգույցների քանակը հաշվելու համար: Մենք համարում ենք, որ ձախ Cnt- ը ծառի մի մասն է, և, այդպիսով, O (H) տարածությունը հետադարձի պահանջվող տարածությունն է:

Անսահման անցում

«Գտեք BST- ի k- րդ ամենափոքր տարրը (BST- ի կարգի վիճակագրություն)» կարելի է լուծել անշարժ շրջադարձի միջոցով, քանի որ Երկուական որոնման ծառի անխափան անցումը անցնում է հանգույցներն աճող կարգով: Այսպիսով, մենք կարող ենք պահել հաշվիչի փոփոխական: Երբ այս հաշվարկի փոփոխականը հավասար է 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

Բարդության վերլուծություն

Timeամանակի բարդություն

ՎՐԱ), քանի որ k- րդ տարրին հասնելու համար նախ պետք է անցնել k-1 տարրերը: Եվ այսպես, նույնիսկ եթե kth տարրը արմատ լիներ, մենք ստիպված կլինեինք անցնել ձախ ենթածառի բոլոր տարրերի միջով:

Տիեզերական բարդություն

O (H),  այստեղ այս տիեզերական բարդությունը պայմանավորված է ռեկուրսիայով: Նույնիսկ եթե ամբողջ ծրագիրն ունի գծային տիեզերական բարդություն: Ալգորիթմն ինքնին գործում է O (H) տարածության մեջ: