K'th туруктуу кошумча мейкиндикти колдонуп, BST ири элемент


Кыйынчылык деңгээли катуу
Көп суралган Amazon Expedia FreeCharge Microsoft Snapdeal Yahoo Яндекс
Binary Search Tree Binary Tree дарак

Маселени билдирүү

"Туруктуу ашыкча мейкиндикти колдонгон BSTдеги эң чоң элемент" сизге экилик издөө дарагы берилгендигин жана андагы k-чоң элементти табуу керектигин билдирет. Демек, экилик издөө дарагынын элементтерин азайуу ирети боюнча жайгаштырсак, анда k-санды катардан кайтаруу керек.

мисал

K'th туруктуу кошумча мейкиндикти колдонуп, BST ири элемент

k = 4

3

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

Туруктуу ашыкча мейкиндикти колдонуп, BSTтен K'th ири элементин табуу ыкмасы

Наивдик мамиле

Бул көйгөйдү адегенде сактоо менен чечсек болот inorder traversal андан кийин n-k + 1 элементин ырааттуулуктан тапса, маселе жооп берет. Бирок бул ыкма O (N) мейкиндигинин татаалдыгына ээ болот. Биз ошондой эле натыйжалуу чечимди талкууладык, анда тескерисинче артка өтүү жасап, түйүндөрдүн санын эсептеп турдук. Түйүндөрдү санап жатып, биз түйүндөрдүн эсептөө к-ге барабар экендигин текшерип жатабыз. Эгерде түйүндүн саны kге барабар болсо, анда биз түйүндү кайтарабыз. Башка учурда, акырында, kth чоң түйүн табылбай жатат деген билдирүү беребиз.

Натыйжалуу мамиле

Ичинде мурунку ыкма, биз рекурсия үчүн O (H) мейкиндигин талап кылган, тескерисинче, артка өтүүнү колдондук. Биз инордералдык өтмөктү кандай кылсак, ошондой кыла алабыз. Inorder traversal артка кайтарып жатканда. Моррис өтүүсүн O (1) мейкиндигинде инердералдык өтүүнү жүргүзүү үчүн колдонобуз. бирок, муну жөн эле жасоонун ордуна, биз Моррис Траверсалды колдонуп, тескери тартипте өтүүнү жасайбыз.

Моррис Траверсал экилик жип дарагында колдонулат, экилик жип дарагы кошумча жипке ээ экилик дарактан башка эч нерсе эмес. Бул даракта траверсалды аткарууну жеңилдетет. Reverse Morris Traversal бул жөн гана Morris Traversal, бирок тескерисинче. Кадимки моррис өтүшүндө биз адегенде сол терекке, андан кийин оң терекке жылмакпыз. Бирок бул жерде алгач оң, андан кийин сол субтритке өтөбүз. Ушундай жол менен траекторалды төмөндөө тартиби менен аткара алат. Анан 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), анткени биз траверсалды рекурсивдүү жасоонун ордуна моррис траверсалын колдондук.