K'th Largest Element في BST عندما لا يُسمح بالتعديل على BST


مستوى الصعوبة متوسط
كثيرا ما يطلب في أمازون سيسكو جوجل UHG Optum
شجرة البحث الثنائية شجرة ثنائية شجرة

المشكلة بيان

يوضح "K'th Largest Element في BST عندما لا يُسمح بالتعديل على BST" أنه يتم إعطاؤك شجرة بحث ثنائية وتحتاج إلى العثور على أكبر عنصر k. هذا يعني أنه عندما يتم ترتيب جميع عناصر شجرة البحث الثنائية بترتيب تنازلي. ثم علينا إعادة العنصر k من المتسلسلة.

مثال

إدخال

K'th Largest Element في BST عندما لا يُسمح بالتعديل على BST

ك = 4

3

التفسير: صورة الشجرة موضحة أعلاه. وعلينا إيجاد رابع أكبر عنصر. لذلك إذا رتبناها بترتيب تصاعدي ، فهي {4 ، 1 ، 2 ، 3 ، 4 ، 5}. لذا فإن رابع أكبر عنصر هو ثالث أصغر عنصر. وهكذا نعيد 6 كناتج.

نهج للعثور على K'th Largest Element في BST عندما لا يُسمح بالتعديل على BST

لقد أجرينا بالفعل سؤالًا مشابهًا ، حيث وجدنا أصغر عنصر k-th في BST. المشكلة هي مجرد تعديل على ذلك. في المنشور السابق ، ناقشنا الحلول لهذا السؤال. كان النهج الأول هو تعديل هيكل بيانات الشجرة. بينما كان الآخر هو تشغيل اجتياز بالترتيب لشجرة البحث الثنائي والاستمرار في عد العقد. منذ السؤال السابق كان إرجاع k لأصغر. لقد قمنا ببساطة بحساب عدد العقد وبمجرد أن كان العدد مساويًا لـ k ، قمنا بإرجاع القيمة على تلك العقدة.

نهج ساذج

هنا الوضع مختلف بعض الشيء. علينا إيجاد أكبر عنصر k ، يمكننا أولًا إيجاد العدد الإجمالي للعقد في الشجرة ثم طرح k-1 من العدد الإجمالي للعقد. نجد الآن n-k + 1 أصغر عقدة ، حيث n هو العدد الإجمالي للعقد في شجرة البحث الثنائية. لكن هذا النهج سيتطلب تمريرين أو تمريرين اجتياز فوق الشجرة.

نهج فعال

يمكننا حل المشكلة بكفاءة إذا تمكنا من إيجاد العقد بترتيب تنازلي. بهذه الطريقة لن نحتاج إلى إيجاد العدد الإجمالي للعقد في الشجرة. سيكون النهج الفعال هو إجراء اجتياز عكسي للشجرة. يتجاوز اجتياز الداخل العكسي لشجرة البحث الثنائية الشجرة بترتيب تنازلي. لذلك أثناء القيام بالعكس بالترتيب ، سنستمر في عد العقد. وعندما يصبح العدد مساويًا لـ k ، نعيد القيمة على تلك العقدة.

رمز

كود C ++ للعثور على K'th Largest Element في 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'th Largest Element في 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

تحليل التعقيد

تعقيد الوقت

O (N) لأننا اجتزنا ببساطة خلال BST، ونظرًا لأن BST لم يكن بها سوى N من العقد. لقد حققنا تعقيدًا زمنيًا خطيًا لـ O (N).

تعقيد الفضاء

يا (1) ، لقد استخدمنا مساحة إضافية ثابتة فقط. وبالتالي فإن هذه الخوارزمية فقط لها تعقيد مساحة ثابت ولكن البرنامج ككل لديه تعقيد مساحة خطي. لأننا نقوم بتخزين عدد N من العقد الشجرية الثنائية.