K'th Бузургтарин унсур дар BST бо истифодаи фазои иловагии доимӣ


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon Expedia FreeCharge Microsoft Snapdeal Yahoo Yandex
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Дарахт

Изҳороти мушкилот

"K'th унсури калонтарин дар BST бо истифодаи фазои иловагии доимӣ" қайд мекунад, ки ба шумо як дарахти ҷустуҷӯии дуӣ дода мешавад ва шумо бояд kth калонтарин элементро дар он пайдо кунед. Пас, агар мо унсурҳои дарахти ҷустуҷӯи бинариро бо тартиби камшаванда тартиб диҳем, пас мо бояд рақами k-ро аз пайдарпаӣ баргардонем.

мисол

K'th Бузургтарин унсур дар BST бо истифодаи фазои иловагии доимӣ

k = 4

3

Шарҳ: Агар элементҳо бо тартиби камшаванда ҷойгир шаванд, пайдарпаӣ [6, 5, 4, 3, 2, 1] мебошад. Ҳоло чаҳорумин унсури калон унсури индекси чорум аст, ки 3 мебошад.

Равиши пайдо кардани K'th бузургтарин унсур дар BST бо истифодаи фазои иловагии доимӣ

Равиши соддалавҳона

Мо метавонем ин масъаларо бо нигоҳ доштани аввал ҳал кунем убур кардан ва пас дар пайдарпаии унсури n-k + 1 посух ба масъала оварда мерасонад. Аммо ин равиш дорои мураккабии фазои O (N) хоҳад буд. Мо инчунин ҳалли бештар самаранокро муҳокима кардем, ки дар он ҷо убурро баръакс анҷом дода, шумори гиреҳҳоро ҳисоб мекардем. Ҳангоми ҳисоб кардани гиреҳҳо мо инчунин месанҷидем, ки оё гиреҳ ба k баробар аст. Агар ҳисоб гиреҳ ба k баробар бошад, мо гиреҳро бармегардонем. Дар акси ҳол, дар ниҳоят, мо паёмеро бармегардонем, ки гиреҳи kth бузургтарин ёфт нашуд.

Усули самаранок

дар равиши қаблӣ, мо гардиши баръакси inorder -ро истифода кардем, ки барои рекурсия фазои O (H) -ро талаб мекард. Мо метавонем ҳамон кореро кунем, ки бо гузариши inorder анҷом додем. Ҳангоме ки мо гардиши ғайриқонуниро барқарор кардем. Мо гузариши Моррисро барои иҷрои гардиши inorder дар фазои O (1) истифода хоҳем кард. аммо ба ҷои ин танҳо ин корро анҷом диҳем, бо истифода аз Моррис Траверсал гардиши баръаксро иҷро мекунем.

Моррис Траверсал дар дарахти риштаи дуӣ истифода мешавад, дарахти риштаи дуӣ чизе нест, ҷуз дарахти дуӣ, ки риштаи изофӣ дорад. Ин иҷрои гардишро дар дарахт осон мекунад. Баръакси Моррис Траверсал танҳо Моррис Траверсал аст, аммо ба тариқи баръакс. Дар гардиши муқаррарии Моррис, мо аввал ба зери дарахти чап ва сипас ба зери дарахти рост ҳаракат мекардем. Аммо дар ин ҷо мо аввал ба зери дарахти рост ва сипас ба зери дарахти чап ҳаракат мекунем. Бо ин роҳ ҳаракатро бо тартиби камшавӣ иҷро карда метавонад. Ва он гоҳ мо элементи kth-ро аз оғоз бармегардонем. Яъне мо ҳисобро нигоҳ медорем ва вақте ки ҳисоб ба k баробар мешавад, он унсурро бармегардонем.

рамз

Коди C ++ барои ёфтани K'th бузургтарин элемент дар 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)
{
    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

Рамзи Java барои ёфтани K'th унсури калонтарин дар 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)
  {
      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).

Мураккабии фазо

О (1), зеро мо ба ҷои иҷро кардани траверсал аз трафики моррисса истифода кардем.