ثنائی تلاش کے درخت لیٹ کوڈ حل میں داخل کریں  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایمیزون ایپل اٹلی فیس بک گوگل مائیکروسافٹ
یلگوردمز ثنائی تلاش درخت کوڈنگ انٹرویو انٹرویو کی تیاری لیٹ کوڈ LeetCodeSolutions۔

اس پریشانی میں ، ہمیں a کا جڑ نوڈ دیا جاتا ہے ثنائی تلاش درخت انٹیجر ویلیوز اور نوڈ کی ایک انٹیجر ویلیو پر مشتمل ہے جو ہمیں بائنری سرچ ٹری میں شامل کرنا ہے اور اس کی ساخت کو واپس کرنا ہے۔ عنصر کو بی ایس ٹی میں داخل کرنے کے بعد ، ہمیں اس کا انڈر ٹراورسال پرنٹ کرنا ہے۔

مثال کے طور پر  

Binary Search Tree:
 
    7
 
  /     \

3         10

        /

      8
Integer Value = 11
3 7 8 10 11
Binary Search Tree:
           5

         /

       4

     /

   3
Integer Value = 2
2 3 4 5

وضاحت

ثنائی تلاش کے درخت لیٹ کوڈ حل میں داخل کریںپن

ثنائی تلاش کے درخت لیٹ کوڈ حل میں داخل کریںپن

نقطہ نظر (تکرار کرنا۔ 

ہمارے بائنری سرچ ٹری میں کسی بھی دیئے گئے نوڈ کو کہاں ڈالا جانا چاہئے اس کے فیصلہ کے ل. ، ہمیں جڑ سے متعلقہ نوڈ تک ایک راستہ طے کرنا ہوگا جس کا بائیں / دائیں بچ childہ دیا ہوا نوڈ ہوگا۔

ہم کام کو کسی پریشانی سے لے کر اس کے ذیلی پریشانی میں بھیج کر اسے بار بار حل کر سکتے ہیں۔ اس معاملے میں ، درخت میں نیا نوڈ ڈالنے کا مطلب یہ ہے کہ اسے اپنے بائیں ذیلی یا دائیں سب ٹری میں داخل کرنا ہے۔ یہی خیال کسی بھی مزید ذیلی ذخیروں کے لئے بھی ہے۔ ہمیں بیس کیس مرتب کرنے کی ضرورت ہے۔ جب ہم اس مقام پر پہنچ جاتے ہیں جہاں کسی بھی ذیلی جگہ کا جڑ نوڈ ہوتا ہے خالی، اس کا مطلب یہ ہوگا کہ ہم ہدف نوڈ داخل کرنے کیلئے راستے کے اختتام پر پہنچ چکے ہیں۔ تو ، ہم ایک واپس نیا نوڈ ایڈریس جس میں نوڈ ویلیو ہے جس کی دی گئی ویلیو بطور ہے۔ ثنائی تلاش درختوں میں کسی صوابدیدی عنصر کو تلاش کرنے میں ایک اہم فائدہ ہوتا ہے O (logN) اوسط مقدمات کے تحت وقت. لہذا ، اس معاملے میں ، ہم موثر وقت میں ڈالنے کے لئے نئے نوڈ کی پوزیشن تلاش کرتے ہیں۔

یہ بھی دیکھتے ہیں
ہاؤس ڈاکو II لیٹکوڈ حل

الگورتھم

  1. ایک فنکشن بنائیں InsertIntoBST () جس کا پتہ واپس کرتا ہے جڑ دیئے گئے داخل کرنے کے بعد BST کا نوڈ
  2. InsertIntoBST () دو پیرامیٹرز ہیں: جڑ درخت اور قیمت داخل کرنے کے لئے نوڈ کی
  3. تقریب مندرجہ ذیل کام کرے گی:
    • If جڑ is خالی، ایک نیا ٹری نوڈ جس کی قیمت دی گئی قیمت کے ساتھ ہی واپس کریں
    • اگر دی گئی قیمت ہے زیادہ سے زیادہ کی قدر سے زیادہ جڑ نوڈ ، پھر اسی مسئلے کو دائیں سب ٹری پر کال کریں اور پھر روٹ واپس کردیں
      • root.right = insertIntoBST (جڑ-> دائیں ، قدر)
      • واپسی جڑ
    • بائیں ذیلی درخت میں دوسری تلاش جیسے:
      • جڑ بائیں= insertIntoBST (root.left، value)
      • واپسی جڑ
  4. ثنائی سرچ درخت کے اندرونی عبور کو پرنٹ کریں

ثنائی تلاش کے درخت لیٹ کوڈ حل میں داخل کرنے کا نفاذ

سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}


BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    if(val > root->value)
    {
        root->right = insertIntoBST(root->right , val);
        return root;
    }
    root->left = insertIntoBST(root->left , val);
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

جاوا پروگرام

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        if(val > root.value)
        {
            root.right = insertIntoBST(root.right , val);
            return root;
        }
        root.left = insertIntoBST(root.left , val);
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

ثنائی تلاش درخت لیٹ کوڈ حل میں داخل کرنے کا پیچیدہ تجزیہ

وقت کی پیچیدگی

O (H) = بی ایس ٹی کی اونچائی = logN (جہاں بی ایس ٹی میں N = تعداد کے نوڈس ہیں) اوسط معاملات میں (جیسا کہ ہم لاگ این ریکورسی کالز کرتے ہیں)۔ لیکن O (N) بدترین صورت میں جب درخت کھوٹ ہوجائے۔ کیوں کہ اگر درخت کے اسکینگ ہوجائے تو ، تلاش ایک ہوجاتی ہے لکیری ایک.

یہ بھی دیکھتے ہیں
ثنائی لیٹ کوڈ حل شامل کریں

خلائی پیچیدگی

O (H) اوسط معاملات میں O (N) بدترین صورت میں اسپیس کمپلیکسٹی کا معاملہ یہاں وقت کی پیچیدگی کی طرح ہی ہے کیونکہ یہ انحصار کرتا ہے جو ہم کرتے ہیں۔

نقطہ نظر (تجاویز 

ہم خلائی پیچیدگی کو بہتر بنانے کے لئے مذکورہ بالا نقطہ نظر کو تکرار سے عمل کر سکتے ہیں۔ تکرار میں اسٹیک فریم استعمال ہوتے ہیں جو میموری کو استعمال کرتے ہیں۔ لہذا ، تکراری حل میں ، ہم اس کی روک تھام کرتے ہیں تکرار کال لوڈ اور ہمارے تلاش کے راستے پر درخت سے نیچے جاو یہاں تک کہ جب تک ہم کسی نوڈ پر حملہ نہ کریں جس کا بائیں اور دائیں دونوں طرف سے ایک ہے خالی. جب ہمارے پاس ہے root.left / root.right = NULL ، ہم نے یہ نوڈ دیئے گئے قدر کے ساتھ ایک نئے نوڈ کے برابر مقرر کیا ہے۔ نوٹ کریں کہ ہم اقدار کا موازنہ کرکے راہ کا فیصلہ کرتے ہیں جڑ ہر تکرار کال میں قیمت۔

الگورتھم

  1. ہم نے پھر ایک InsertIntoBST () مذکورہ بالا مقصد کے لئے
  2. اگر جڑ NULL ہے
    1. دیئے گئے ویلیو کی طرح ویلیو کے ساتھ نیا نوڈ لوٹائیں
  3. کہتے ہیں کہ جڑ کی ایک کاپی بنائیں ڈمی بی ایس ٹی کے مشمولات میں ہیرا پھیری کرنا
  4. جبکہ ڈمی is نوٹ خالی
    1. اگر دی گئی قیمت سے زیادہ ہے root.val
      1. If root.right NULL ہے
        1. root.right = دی گئی قیمت کے ساتھ نیا نوڈ
        2. واپسی جڑ
      2. اور ، سیٹ کریں
        1. جڑ = root.right، دائیں subtree کودنے کے لئے
    2. بصورت دیگر اگر قیمت اس سے کم یا مساوی ہے root.val
      1. اگر root.left NULL ہے
        1. جڑ بائیں = دی گئی قیمت کے ساتھ نیا نوڈ
        2. واپسی جڑ
      2. اور ، سیٹ کریں
        1. جڑ = جڑ بائیں، بائیں سب ٹری پر کودنا
  5. بی ایس ٹی کے اندرونی عبور کو پرنٹ کریں

ثنائی تلاش کے درخت لیٹ کوڈ حل میں داخل کرنے کا نفاذ

سی ++ پروگرام

#include <bits/stdc++.h>
using namespace std;
struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

void inorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    inorderTraversal(root->left);
    cout << root->value << " ";
    inorderTraversal(root->right);
    return;
}

BSTNode* insertIntoBST(BSTNode* root , int val)
{
    if(root == NULL)
        return new BSTNode(val);
    BSTNode* dummy = root;
    while(dummy != NULL)
    {
        if(val > dummy->value)
        {
            if(dummy->right == NULL)
            {
                dummy->right = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->right;
        }
        else
        {
            if(dummy->left == NULL)
            {
                dummy->left = new BSTNode(val);
                return root;
            }
            else
                dummy = dummy->left;
        }
    }
    return root;
}

int main()
{
    BSTNode* root = new BSTNode(7);
    root->left = new BSTNode(3);
    root->right = new BSTNode(10);
    root->right->left = new BSTNode(8);
    int val = 11;
    root = insertIntoBST(root , val);
    inorderTraversal(root);
    return 0;
}

جاوا پروگرام

class BSTNode
{
    int value;
    BSTNode left , right;

    BSTNode(int val)
    {
        value = val;
        left = right = null;
    }
}

class insert_into_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(7);
        root.left = new BSTNode(3);
        root.right = new BSTNode(10);
        root.right.left = new BSTNode(8);
        int val = 11;
        root = insertIntoBST(root , val);
        inorderTraversal(root);
    }

    static BSTNode insertIntoBST(BSTNode root , int val)
    {
        if(root == null)
            return new BSTNode(val);
        BSTNode dummy = root;
        while(dummy != null)
        {
            if(val > dummy.value)
            {
                if(dummy.right == null)
                {
                    dummy.right = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.right;
            }
            else
            {
                if(dummy.left == null)
                {
                    dummy.left = new BSTNode(val);
                    return root;
                }
                else
                    dummy = dummy.left;
            }
        }
        return root;
    }

    static void inorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        inorderTraversal(root.left);
        System.out.print(root.value + " ");
        inorderTraversal(root.right);
        return;
    }
}

3 7 8 10 11

ثنائی تلاش درخت لیٹ کوڈ حل میں داخل کرنے کا پیچیدہ تجزیہ

وقت کی پیچیدگی

O (H) = بی ایس ٹی کی اونچائی = logN (جہاں بی ایس ٹی میں N = نمبروں کی تعداد ہے) اوسط معاملات میں۔ لیکن O (N) بدترین صورت میں جب درخت کھوٹ ہوجائے۔ ایک بار پھر ، وقت کی پیچیدگی کا انحصار اس تکرار کی تعداد پر ہوتا ہے جو ہم منزل تک پہنچنے کے ل make کرتے ہیں جس کے بعد دیئے گئے نوڈ کو ڈالا جانا چاہئے اور اس کا انحصار درختوں کے تناؤ پر ہوتا ہے۔

یہ بھی دیکھتے ہیں
ثنائی درخت کا اوپر دیکھیں

خلائی پیچیدگی

O (1). یہاں تک کہ بدترین حالت میں بھی ، ہم صرف متغیر کے ل constant مستقل جگہ استعمال کرتے ہیں۔