K'th тұрақты қосымша кеңістікті қолданатын BST-тегі ең үлкен элемент


Күрделілік дәрежесі қиын
Жиі кіреді Amazon Expedia FreeCharge Microsoft Шапшаң Yahoo Яндекс
Екілік іздеу ағашы Екілік ағаш ағаш

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

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

мысал

K'th тұрақты қосымша кеңістікті қолданатын BST-тегі ең үлкен элемент

k = 4

3

Түсініктеме: егер элементтер кему ретімен орналасса, реттілік [6, 5, 4, 3, 2, 1] болады. Енді төртінші үлкен элемент - бұл төртінші индекстегі элемент, ол 3-ке тең.

Тұрақты қосымша кеңістікті қолдана отырып, BST-тегі ең үлкен элементті табу тәсілі

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

Бұл мәселені алдымен сақтау арқылы шеше аламыз ішке өту содан кейін тізбектегі n-k + 1 элементін табу есепке жауап береді. Бірақ бұл тәсіл O (N) кеңістігінің күрделілігіне ие болады. Сондай-ақ, біз кері инерсиялы қозғалыс жасап, түйіндер санының есебін жүргізген тиімді шешімді талқыладық. Түйіндерді санау кезінде біз түйіндер санының k-ге тең екендігін тексердік. Егер түйін саны k-ге тең болса, біз түйінді қайтарамыз. Басқа жағдайда, біз k-ші ең үлкен түйін табылмағаны туралы хабарлама жібереміз.

Тиімді тәсіл

Ішінде алдыңғы тәсіл, біз рекурсия үшін O (H) кеңістігін қажет ететін кері инерсивті жүрісті қолдандық. Біз инордеральды траверсалмен жасағанды ​​жасай аламыз. Біз инерциялық траверсті өзгерткен кезде. Біз Моррис травералын O (1) кеңістігінде инерциалды траверсті орындау үшін қолданамыз. бірақ мұны жасаудың орнына біз Моррис Траверсалды қолдана отырып, тәртіп бойынша траверсаль жасаймыз.

Моррис Траверсаль екілік бұрандалы ағашта қолданылады, екілік бұрандалы ағаш қосымша жіпке ие екілік ағаштан басқа ешнәрсе емес. Бұл ағашта траверсаль жасауды жеңілдетеді. Кері Моррис Траверсалы тек Моррис Траверсалы, бірақ керісінше. Морристің қалыпты қозғалысы кезінде біз алдымен сол жақ ағашқа, содан кейін оң жақ ағашқа ауысар едік. Бірақ мұнда алдымен оң жақ ағашқа, содан кейін сол жақ ағашқа ауысамыз. Бұл жол траверсалды кему ретімен орындай алады. Содан кейін біз kth элементін басынан бастап қайтарамыз. Яғни біз санауды жүргіземіз, ал санау k-ге тең болғанда, сол элементті қайтарамыз.

код

Тұрақты қосымша кеңістікті қолдана отырып, BST ішіндегі ең үлкен элементті табуға арналған 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)
{
    node *cur = root; node* kLargest = NULL;
    int cnt = 0;

    while(cur != NULL){
        // if right subtree is NULL, then move to left subtree
        if(cur->right == NULL){
            // if current node is kth largest
            if(cnt == k-1)
                kLargest = cur;
            cnt++;
            // move to the left subtree
            cur = cur->left;
        }
        else{
            // to find successor of current node
            node* successor = cur->right;

            while(successor->left != NULL && successor->left != cur)
                successor = successor->left;

            if(successor->left == NULL){
                // set current node as left child of successor as it doesn't have left child
                successor->left = cur;
                    cur = cur->right;
            }
            else{
                // remove threads to restore the original tree
                successor->left = NULL;
                if(cnt == k-1)
                    kLargest = cur;
                cnt++;
                cur = cur->left;
            }
        }
    }
    return kLargest;
}
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 ішіндегі ең үлкен элементті табуға арналған 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)
  {
      node cur = root; node kLargest = null;
      int cnt = 0;
  
      while(cur != null){
          // if right subtree is NULL, then move to left subtree
          if(cur.right == null){
              // if current node is kth largest
              if(cnt == k-1)
                  kLargest = cur;
              cnt++;
              // move to the left subtree
              cur = cur.left;
          }
          else{
              // to find successor of current node
              node successor = cur.right;
  
              while(successor.left != null && successor.left != cur)
                  successor = successor.left;
  
              if(successor.left == null){
                  // set current node as left child of successor as it doesn't have left child
                  successor.left = cur;
                      cur = cur.right;
              }
              else{
                  // remove threads to restore the original tree
                  successor.left = null;
                  if(cnt == k-1)
                      kLargest = cur;
                  cnt++;
                  cur = cur.left;
              }
          }
      }
      return kLargest;
  }
  
  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), өйткені біз бір кездері ағаштың барлық элементтерін басып өттік. Уақыттың күрделілігі сызықтық, яғни O (N).

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

O (1), өйткені біз траверсалды рекурсивті түрде жасамай, моррис траверсалын қолдандық.