იპოვნეთ კ-ის ყველაზე პატარა ელემენტი BST- ში (შეკვეთის სტატისტიკა BST- ში)  


Რთული ტური საშუალო
ხშირად ეკითხებიან თანამოსაყრელი Amazon Google
ორობითი ძებნა ხე ორობითი ხე ხე

პრობლემის განცხადება  

”იპოვნეთ k- ის ყველაზე პატარა ელემენტი BST (შეკვეთის სტატისტიკა BST- ში) ”პრობლემა აცხადებს, რომ გეძლევათ ორობითი ძიების ხე და თქვენ უნდა იპოვოთ k-th ყველაზე მცირე რიცხვი BST- ში. ეს ნიშნავს, თუ ჩვენ გავაკეთებთ წესით ორობითი ძიების ხის გადაკვეთა და შედეგის შენახვა ვექტორში / მასივში. მაშინ ინდექსის ელემენტი (k-1) იქნება უმცირესი, თუ გავითვალისწინებთ 0 – ზე დაფუძნებულ ინდექსს.

მაგალითი  

შეყვანის

 

იპოვნეთ კ-ის ყველაზე პატარა ელემენტი BST- ში (შეკვეთის სტატისტიკა BST- ში)

k = 4

6

განმარტება: თუ მოცემული ორობითი ხის შეკვეთით გატარებას მივიღებთ, მივიღებთ {2, 4, 5, 6, 8, 9}. ამში, ჩვენ უნდა მოვძებნოთ მე -4 ყველაზე პატარა ელემენტი, მაშინ ეს არის 6. ამრიგად, გამომავალია 6.

მიდგომა  

დამატებული ხის მონაცემთა სტრუქტურა

ამ მიდგომით, ჩვენ ვთვლით, რომ თითოეული კვანძი ინახავს ელემენტს თავის მარცხენა ქვე-ხეში. ხის აგების დროს ჩვენ ვიცავთ ელემენტებს თითოეული კვანძის მარცხენა ქვევრში. ეს ფაქტი გამოიყენება ხეში k- ყველაზე პატარა ელემენტის მოსაძებნად. როდესაც ვცდილობთ ვიპოვოთ kth ელემენტი, ვამოწმებთ რომ თუ მარცხენა ქვეძეს უფრო მეტი ელემენტი აქვს ვიდრე k. შემდეგ ჩვენი k- ყველაზე პატარა ელემენტი მდგომარეობს მარცხენა ქვე-ხეში, სხვაგან იგი მდებარეობს მარჯვენა ქვე-ხეში. და ასე ვხვდებით მე -XNUMX ყველაზე პატარა ელემენტს BST- ში.

იხილეთ ასევე
დაბალანსებული ორობითი ხე

კოდი

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
ჯავის კოდი 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), უარეს შემთხვევაში H შეიძლება იყოს N– ის ტოლი, თუ შეყვანის სახით გვაქვს დახრილი ხე და უნდა ვიპოვოთ მე -XNUMX ყველაზე პატარა ელემენტი.

იხილეთ ასევე
ორობითი ხის საზღვრის გადაკვეთა
სივრცის სირთულე

O (H), აქ ჩვენ არ განვიხილავთ მარცხენა Cnt- ის მიერ მოთხოვნილ ადგილს მარცხენა ქვეტყეში კვანძების რაოდენობის დასათვლელად. მიგვაჩნია, რომ leftCnt ხის ნაწილია და ამრიგად 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
ჯავის კოდი 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 ელემენტი იყო ფესვი, ჩვენ მოგვიწევს მარცხენა ქვედა ხის ყველა ელემენტის გავლა.

იხილეთ ასევე
N ზომის მოცემული მასივის შემოწმება შეიძლება წარმოადგენს N დონის BST– ს, თუ არა
სივრცის სირთულე

O (H),  აქ ეს სივრცული სირთულე უკავშირდება რეკურსიას. მიუხედავად იმისა, რომ მთელ პროგრამას აქვს ხაზოვანი სივრცის სირთულე. თავად ალგორითმი მუშაობს O (H) სივრცეში.