بائنري سرچ وڻ ليٽ ڪوڊ حل ۾ داخل ڪريو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon ايپل Atlassian ڪريو گوگل Microsoft جي
ثنائي ڳولا وارو وڻ

ھن مسئلي ۾ ، اسان کي ھڪڙي جو روٽ نوڊ ڏنو ويو آھي ثنائي ڳولا وارو وڻ انٽيگر ويلز ۽ هڪ نوڊ جي انگيري قيمت جيڪا اسان کي بائنري سرچ وڻ ۾ شامل ڪرڻ ۽ ان جي returnانچي کي واپس ڪرڻ گهرجي. بي ايس ٽي ۾ عنصر داخل ڪرڻ کان پوءِ ، اسان کي ان جو Inder Traversal پرنٽ ڪرڻو پوندو.

مثال

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ي ٻار کي ڏنل نوڊ ڏنو ويندو.

اسان مسئلي کان وٺي انهي جي ذيلي مسئلي ڏانهن ڪم کي منتقل ڪندي ٻيهر حل ڪري سگھون ٿا. انهي صورت ۾ ، وڻ ۾ هڪ نئون نوڊ داخل ڪرڻ جو مطلب آهي ته ان کي پنهنجي بائیں يا اڇي سبجيڪٽ ۾ داخل ڪرڻ جو مطلب آهي. ساڳيو خيال ڪنهن ٻئي ذيلي ذخيري لاءِ رکيل آهي. اسان کي بي بنياد ڪيس جوڙڻ جي ضرورت آهي. جڏهن اسان هڪ نقطي تي پهچي چڪا آهيون جتي ڪنهن ذيلي وڻن جو بنيادي نوڊ هوندو آهي NULL، انهي جو مطلب اهو ٿيندو ته اسان ٽارگيٽ نوڊ داخل ڪرڻ لاءِ رستي جي آخر ۾ پهچي چڪا آهيون. تنهن ڪري ، اسان هڪ واپس موٽون ٿا نئون نوڊ ايڊريس ڏنل نوڊ جي طور تي نوڊ ويل آھي. ثنائي تلاش جا وڻ اھڙي فائدي ۾ آھن ڪنھن به ثالثي عنصر کي ڳولڻ لاءِ اي (لاگ اين) سراسري ڪيسن جي تحت وقت. تنهن ڪري ، انهي صورت ۾ ، اسان موثر وقت ۾ داخل ٿيڻ جا نوان نوڊ جي پوزيشن ڳوليندا آهيون.

الورورٿم

  1. ڪم ٺاهيو داخل ڪريو انٽ بيسٽ () جيڪو پتو جو پتو موٽائي ٿو پاڙ جي بي ايس ٽي پاران داخل ڪرڻ کان پوءِ جوڙ
  2. داخل ڪريو انٽ بيسٽ () ٻه پيمانا آهن: پاڙ وڻ جو ۽ قدر داخل ٿيڻ لاءِ نوڊ جو
  3. هيٺيان ڪم ڪندو:
    • If پاڙ is نول ، نئين وڻ سان جوڙيو ويو ساڳيو قدر جيترو قدر ڏنو ويو هجي
    • جيڪڏهن ڏنل قيمت آهي تمام وڏو جي قيمت کان پاڙ نوڊ ، پوءِ ساڳي مسئلي کي سا subي ذيلي طرف سڏيو ۽ پوءِ روٽ کي واپس ڪيو
      • root.right = داخل ڪريو اين بي بي ايس (root-> صحيح ، قدر)
      • موٽڻ پاڙ
    • بائیں سبجيڪٽ ۾ ٻين ڳولها جيئن:
      • root.ft= داخل ڪريو اين بي بي ايس (root.left ، ويليو)
      • موٽڻ پاڙ
  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

بائنري سرچ وڻ ليوٽ ڪوڊ حل ۾ داخل ڪرڻ جي پيچيدگي تجزيو

وقت جي پيچيدگي

اي (ايڇ) = بي ٽي ايس جي اوچائي = لاگ اين (جتي اين = بي ٽي ايس ۾ نوڊس جو تعداد) اوسط ڪيسن ۾ (جيئن اسان لاگ اين ترسيل ڪالون ڪندا آهيون). پر اي (اين) بدترين صورت ۾ جڏهن وڻ هڪ ٺڪيل هوندو آهي. ڇو ته صورت ۾ وڻ جھلڻ جي صورت ۾ ، ڳولا بنجي ويندي آهي قطار هڪ.

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

اي (ايڇ) سراسري ڪيسن ۾. اي (اين) بدترين صورت ۾. خلائي ڪمپليڪس سان اهو معاملو ساڳيو آهي هتي وقت جي پيچيدگي جيئن ته اهو دارومدار ڪالن جي تعداد تي منحصر آهي اسان کي.

پهچ (جانورن جي)

اسان مٿي ڏنل طريقي سان پيروي ڪري سگھون ٿا بار بار خلائي پيچيدگي تي. recursion اسٽريم فريم استعمال ڪندو آهي جيڪي ياداشت ڪتب آڻين. تنهن ڪري ، ورثي حل ۾ ، اسان کي روڪيو ٿا ٻيهر موٽڻ وارو لوڊ ۽ وڻ کي اسان جي ڳولا واري رستي تي وڃو جيستائين اسان هڪ نوڊ strikeاٽيو جيڪو اسان جي کاٻي يا سا isي آهي NULL. جڏهن اسان وٽ آهي root.left / root.right = نول ، اسان هي نوڊ نئين نوڊ جي برابر برابر قدر سان ٺهرايو آهي. ياد رکو ته اسان قدرن کي مقابلي سان رستو جو فيصلو ڪريون ٿا پاڙ هر ريٽنگ ڪال ۾ قدر.

الورورٿم

  1. اسان وٽ ٻيهر هڪ آهي داخل ڪريو انٽ بيسٽ () مٿي ساڳين مقصدن لاءِ
  2. ته پاڙ نول آهي
    1. نئين نوڊ کي ويليو وانگر ساڳيو قدر موٽايو
  3. روٽ جي ڪاپي ٺاهيو ، چئو ٿڌي بي ٽي ٽي جي مواد کي بگاڙڻ لاءِ
  4. جڏهن ته ٿڌي is نه NULL
    1. جيڪڏهن ڏنل قيمت کان وڌيڪ آهي root.val
      1. If root.right نول آهي
        1. root.right = نئين نوڊ ڏنل قيمت سان
        2. موٽڻ پاڙ
      2. ايلس ، سيٽيو
        1. پاڙ = root.right، سا subي طرف وڃڻ جي لاءِ
    2. ٻئي صورت ۾ جيڪڏهن قدر وڌيڪ يا برابر هجي root.val
      1. جي روٽ. ليف نه آھي
        1. root.ft = نئين نوڊ ڏنل قيمت سان
        2. موٽڻ پاڙ
      2. ايلس ، سيٽيو
        1. پاڙ = root.ft، کاٻي ڌر ڏانهن وڃڻ
  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

بائنري سرچ وڻ ليوٽ ڪوڊ حل ۾ داخل ڪرڻ جي پيچيدگي تجزيو

وقت جي پيچيدگي

اي (ايڇ) = بي ٽي ايس جي اوچائي = لاگ اين (جتي N = بي او ايس ۾ جوڙ جو تعداد) اوسط ڪيسن ۾. پر اي (اين) بدترين صورت ۾ جڏهن وڻ هڪ ٺڪيل هوندو آهي. ٻيهر ، وقت جي پيچيدگي ان انحرافي جي تعداد تي منحصر آهي جيڪا اسان منزل تائين پهچڻ لاءِ ٺاهيون ٿا جنهن کان پوءِ ڏنل نوڊ داخل ڪيو وڃي ۽ اهو وڻ جي جوڙجڪ تي منحصر آهي.

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

اي (1). بدترين صورت ۾ به ، اسان رڳو متغير جي لاءِ مستقل جڳهه استعمال ڪندا آهيون.