BST өзгертуге жол берілмеген кезде BST-тегі ең үлкен элемент


Күрделілік дәрежесі орта
Жиі кіреді Amazon Cisco Google UHG Optum
Екілік іздеу ағашы Екілік ағаш ағаш

Проблемалық мәлімдеме

«BST-ге өзгеріске жол берілмеген кезде BST-тегі ең үлкен элемент» сізге екілік іздеу ағашы берілгенін және k-ші ең үлкен элементті табу керек екенін айтады. Бұл дегеніміз, екілік іздеу ағашының барлық элементтері кему ретімен орналасқан кезде. Сонда біз k-ші элементті тізбектен қайтаруымыз керек.

мысал

енгізу

BST өзгертуге жол берілмеген кезде BST-тегі ең үлкен элемент

k = 4

3

Түсіндіру: ағаш кескіні жоғарыда көрсетілген. Біз 4-ші элементті табуымыз керек. Сондықтан оларды өсу ретімен орналастырсақ, олар {1, 2, 3, 4, 5, 6}. Сонымен 4-ші үлкен элемент 3-ші кіші элемент болып табылады. Осылайша, біз 3-ті шығыс ретінде қайтарамыз.

BST-ге өзгертуге жол берілмеген кезде BST-де K'th ірі элементін табу тәсілі

Біз осыған ұқсас сұрақ қойдық, қайдан таптық k-ші элемент БСТ-да. Мәселе - бұл тек модификацияда. Алдыңғы жазбада біз осы сұрақтың шешімдерін талқыладық. Бірінші тәсіл ағаш деректерінің құрылымын өзгерту болды. Ал екіншісі екілік іздеу ағашына ретпен жүруді жүргізіп, түйіндерді санауды жалғастыру керек болды. Алдыңғы сұрақ k-ны ең кішісін қайтару болғандықтан болды. Біз жай ғана түйіндер санын санадық және санау k-ге тең болғаннан кейін сол түйіннің мәнін шығардық.

Аңғал көзқарас

Мұнда жағдай сәл басқаша. Біз k-ші үлкен элементті табуымыз керек, алдымен ағаштағы түйіндердің жалпы санын тауып, содан кейін k-1-ді тораптардың жалпы санынан алып тастай аламыз. Енді n-k + 1 ең кіші түйінді табамыз, мұндағы n - екілік іздеу ағашындағы түйіндердің жалпы саны. Бірақ бұл тәсіл екі немесе екі өтуді қажет етеді жүрістер ағаштың үстінде.

Тиімді тәсіл

Егер түйіндерді кему ретімен таба алсақ, мәселені тиімді шеше аламыз. Осылайша ағаштағы түйіндердің жалпы санын табу қажет болмайды. Тиімді тәсіл ағашты кері бағытта кесіп өту болады. Екілік іздеу ағашының кері инерсиялы қозғалысы ағашты кему ретімен өтеді. Сонымен, кері тәртіпте жұмыс істей отырып, біз түйіндерді санауды жалғастырамыз. ал санау k-ге тең болғанда, сол түйіндегі мәнді қайтарамыз.

код

BST модификациясына жол берілмеген кезде BST-те K'th ірі элементін табуға арналған C ++ коды

#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* findKthLargest(node* root, int& k)
{
    // base case
    if(!root)
        return NULL;
    node *right = findKthLargest(root->right, k);
    if(right)
        return right;
    // if current element is kth largest
    if(k==1)
        return root;
    // if the kth largest is not found in the left subtree
    // search in left subtree
    k--;
    return findKthLargest(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 = findKthLargest(root, k);
    if(res == NULL)
        cout<<"No kth largest found";
    else
        cout<<"Kth largest element is "<<res->data;
}
6
3 2 1 5 4 6
4
Kth largest element is 3

BST модификациясына жол берілмеген кезде BST-те K'th ірі элементін табуға арналған Java коды

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 findKthLargest(node root, int k)
  {
      // base case
      if(root == null)
          return null;
      node right = findKthLargest(root.right, k);
      if(right != null)
          return right;
      count++;
      // if current element is kth largest
      if(k==count)
          return root;
      // if the kth largest is not found in the left subtree
      // search in left subtree
      return findKthLargest(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();
      count = 0;
      node res = findKthLargest(root, k);
      if(res == null)
          System.out.println("No kth largest found");
      else
          System.out.println("Kth largest element is "+res.data);
  }
}
6
3 2 1 5 4 6
4
Kth largest element is 3

Күрделілікті талдау

Уақыттың күрделілігі

O (N), өйткені біз жай жолды жүріп өттік BSTжәне BST-ден бастап тек N түйін болған. Біз O (N) сызықтық уақыттық күрделілігіне қол жеткіздік.

Ғарыштың күрделілігі

O (1), біз тек тұрақты қосымша орынды пайдаландық. Осылайша, тек осы алгоритмнің кеңістіктің тұрақты күрделілігі бар, ал жалпы алғанда сызықтық кеңістіктің күрделілігі бар. Себебі біз N екілік ағаш түйіндерін сақтаймыз.