K'th најголемиот елемент во BST кога не е дозволена измена во BST


Ниво на тешкотија Медиум
Често прашувано во Амазон Cisco Google UHG Optum
Дрво за бинарно пребарување Бинарно дрво Дрво

Изјава за проблем

„K'th Largest Element in BST кога модификацијата во BST не е дозволена" наведува дека ви е дадено бинарно стебло за пребарување и треба да го пронајдете kth најголемиот елемент. Ова значи дека кога сите елементи на стеблото за бинарно пребарување се подредени по опаѓачки редослед. Тогаш треба да го вратиме елементот kth од низата.

пример

Внесете

K'th најголемиот елемент во BST кога не е дозволена измена во BST

k = 4

3

Објаснување: Сликата на дрвото е прикажана погоре. И треба да го најдеме 4-тиот најголем елемент. Значи, ако ги подредиме по растечки редослед, тие се {1, 2, 3, 4, 5, 6}. Значи, 4-тиот најголем елемент е 3-тиот најмал елемент. Така враќаме 3 како излез.

Пристап да го пронајдете најголемиот елемент K'во BST кога не е дозволена измена во BST

Ние веќе направивме слично прашање, каде го најдовме k-најмалиот елемент во БСТ. Проблемот е само модификација над тоа. Во претходниот пост, разговаравме за решенијата за тоа прашање. Првиот пристап беше да се измени структурата на податоците на дрвото. Додека другиот требаше да изврши по ред редослед за стеблото за бинарно пребарување и да ги брои јазлите. Бидејќи претходното прашање беше да се врати враќањето најмало. Едноставно го изброивме бројот на јазли и штом броењето беше еднакво на k ја вративме вредноста на тој јазол.

Наивен пристап

Тука ситуацијата е малку поинаква. Треба да го најдеме најголемиот елемент kth, прво можеме да го најдеме вкупниот број на јазли во дрвото и потоа да го одземеме k-1 од вкупниот број на јазли. Сега наоѓаме n-k + 1 најмал јазол, каде n е вкупниот број на јазли во стеблото за бинарно пребарување. Но, за овој пристап ќе бидат потребни две додавања или две поминувања над дрвото.

Ефикасен пристап

Можеме ефикасно да го решиме проблемот ако можеме да ги најдеме јазлите во опаѓачки редослед. На тој начин нема да треба да го наоѓаме вкупниот број на јазли на дрвото. Ефикасен пристап ќе биде да се направи превртување на дрвото во обратен редослед. Превртувањето на обратната волумен на дрвото за бинарно пребарување го поминува дрвото по опаѓачки редослед. Значи, додека правиме обратен редослед, ќе продолжиме да ги броиме јазлите. и кога броењето ќе стане еднакво на k, ја враќаме вредноста на тој јазол.

Код

C ++ код за наоѓање на најголемиот елемент K во BST кога не е дозволена измена во BST

#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

Java код за наоѓање на најголемиот елемент K во BST кога не е дозволена измена во BST

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

Анализа на сложеност

Временска комплексност

НА), затоа што едноставно поминавме низ БСТ, и бидејќи BST имаше само N јазли. Постигнавме линеарна временска сложеност на O (N).

Комплексноста на просторот

О (1), користевме само постојан дополнителен простор. Така само овој алгоритам има постојана вселенска сложеност, но програмата како целина има линеарна вселенска сложеност. Бидејќи чуваме N бинарни јазли на дрвјата.