ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಸೇರಿಸಿ


ತೊಂದರೆ ಮಟ್ಟ ಮಧ್ಯಮ
ಆಗಾಗ್ಗೆ ಕೇಳಲಾಗುತ್ತದೆ ಅಮೆಜಾನ್ ಆಪಲ್ Atlassian ಫೇಸ್ಬುಕ್ ಗೂಗಲ್ ಮೈಕ್ರೋಸಾಫ್ಟ್
ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ

ಈ ಸಮಸ್ಯೆಯಲ್ಲಿ, ನಮಗೆ 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

ವಿವರಣೆ

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಸೇರಿಸಿ

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಸೇರಿಸಿ

ಅನುಸಂಧಾನ (ಪುನರಾವರ್ತಿತ)

ನಮ್ಮ ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀನಲ್ಲಿ ಯಾವುದೇ ನೋಡ್ ಅನ್ನು ಎಲ್ಲಿ ಸೇರಿಸಬೇಕು ಎಂದು ನಿರ್ಧರಿಸಲು, ನಾವು ಮೂಲದಿಂದ ಅನುಗುಣವಾದ ನೋಡ್ಗೆ ಒಂದು ಮಾರ್ಗವನ್ನು ಹೊಂದಿಸಬೇಕು, ಅವರ ಎಡ / ಬಲ ಮಗು ನೀಡಿದ ನೋಡ್ ಆಗಿರುತ್ತದೆ.

ಸಮಸ್ಯೆಯನ್ನು ಸಮಸ್ಯೆಯಿಂದ ಅದರ ಉಪ-ಸಮಸ್ಯೆಗೆ ರವಾನಿಸುವ ಮೂಲಕ ನಾವು ಇದನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಪರಿಹರಿಸಬಹುದು. ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಹೊಸ ನೋಡ್ ಅನ್ನು ಮರಕ್ಕೆ ಸೇರಿಸುವುದು ಎಂದರೆ ಅದರ ಎಡ ಸಬ್‌ಟ್ರೀ ಅಥವಾ ಬಲ ಸಬ್‌ಟ್ರೀಗೆ ಸೇರಿಸುವುದು. ಯಾವುದೇ ಮುಂದಿನ ಸಬ್‌ಟ್ರೀಗಳಿಗೂ ಇದೇ ಆಲೋಚನೆ ಇದೆ. ನಾವು ಬೇಸ್ ಕೇಸ್ ಅನ್ನು ಹೊಂದಿಸಬೇಕಾಗಿದೆ. ಯಾವುದೇ ಸಬ್‌ಟ್ರೀನ ಮೂಲ ನೋಡ್ ಇರುವ ಹಂತವನ್ನು ನಾವು ತಲುಪಿದಾಗ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು, ಗುರಿ ನೋಡ್ ಅನ್ನು ಸೇರಿಸಲು ನಾವು ಮಾರ್ಗದ ಅಂತ್ಯವನ್ನು ತಲುಪಿದ್ದೇವೆ ಎಂದರ್ಥ. ಆದ್ದರಿಂದ, ನಾವು ಒಂದು ಮರಳುತ್ತೇವೆ ಹೊಸ ಕೊಟ್ಟಿರುವ ಮೌಲ್ಯದಂತೆ ನೋಡ್ ಮೌಲ್ಯವನ್ನು ಹೊಂದಿರುವ ನೋಡ್ ವಿಳಾಸ. ಯಾವುದೇ ಅನಿಯಂತ್ರಿತ ಅಂಶವನ್ನು ಹುಡುಕಲು ಬೈನರಿ ಸರ್ಚ್ ಮರಗಳು ಗಮನಾರ್ಹ ಪ್ರಯೋಜನವನ್ನು ಹೊಂದಿವೆ ಒ (ಲಾಗ್ ಎನ್) ಸರಾಸರಿ ಸಂದರ್ಭಗಳಲ್ಲಿ ಸಮಯ. ಆದ್ದರಿಂದ, ಈ ಸಂದರ್ಭದಲ್ಲಿ, ಹೊಸ ನೋಡ್ನ ಸ್ಥಾನವನ್ನು ಸಮರ್ಥ ಸಮಯದಲ್ಲಿ ಸೇರಿಸಲು ನಾವು ಕಂಡುಕೊಳ್ಳುತ್ತೇವೆ.

ಕ್ರಮಾವಳಿ

  1. ಕಾರ್ಯವನ್ನು ರಚಿಸಿ insertIntoBST () ಇದು ವಿಳಾಸವನ್ನು ಹಿಂದಿರುಗಿಸುತ್ತದೆ ಬೇರು ನೀಡಿರುವ ನಂತರ ಬಿಎಸ್ಟಿ ನೋಡ್
  2. insertIntoBST () ಎರಡು ನಿಯತಾಂಕಗಳನ್ನು ಹೊಂದಿದೆ: ಬೇರು ಮರದ ಮತ್ತು ಮೌಲ್ಯ ಸೇರಿಸಬೇಕಾದ ನೋಡ್ನ
  3. ಕಾರ್ಯವು ಈ ಕೆಳಗಿನವುಗಳನ್ನು ಮಾಡುತ್ತದೆ:
    • If ಬೇರು is ಸೊನ್ನೆ, ಕೊಟ್ಟಿರುವ ಮೌಲ್ಯದಂತೆಯೇ ಹೊಸ ಮರದ ನೋಡ್ ಅನ್ನು ಹಿಂತಿರುಗಿ
    • ಕೊಟ್ಟಿರುವ ಮೌಲ್ಯ ಇದ್ದರೆ ಹೆಚ್ಚಿನ ಮೌಲ್ಯಕ್ಕಿಂತ ಬೇರು ನೋಡ್, ನಂತರ ಅದೇ ಸಮಸ್ಯೆಯನ್ನು ಬಲ ಸಬ್‌ಟ್ರೀಗೆ ಕರೆ ಮಾಡಿ ನಂತರ ಮೂಲವನ್ನು ಹಿಂತಿರುಗಿ
      • root.right = insertIntoBST (root-> ಬಲ, ಮೌಲ್ಯ)
      • ರಿಟರ್ನ್ ಬೇರು
    • ಎಡ ಸಬ್‌ಟ್ರೀನಲ್ಲಿ ಬೇರೆ ಹುಡುಕಾಟ:
      • root.left= insertIntoBST (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

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಸೇರಿಸುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎಚ್) = ಬಿಎಸ್ಟಿ ಎತ್ತರ = ಲಾಗ್ ಎನ್ (ಅಲ್ಲಿ ಬಿಎಸ್‌ಟಿಯಲ್ಲಿ ಎನ್ = ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ) ಸರಾಸರಿ ಸಂದರ್ಭಗಳಲ್ಲಿ (ನಾವು ಲಾಗ್‌ಎನ್ ಪುನರಾವರ್ತಿತ ಕರೆಗಳನ್ನು ಮಾಡುತ್ತಿರುವಂತೆ). ಆದರೆ ಒ (ಎನ್) ಮರವು ಓರೆಯಾದಾಗ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ. ಒಂದು ವೇಳೆ ಮರವನ್ನು ಓರೆಯಾಗಿಸಿದರೆ, ಹುಡುಕಾಟವು a ಆಗುತ್ತದೆ ರೇಖೀಯ ಒಂದು.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (ಎಚ್) ಸರಾಸರಿ ಸಂದರ್ಭಗಳಲ್ಲಿ. ಒ (ಎನ್) ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ. ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯ ವಿಷಯವು ಇಲ್ಲಿ ಸಮಯ ಸಂಕೀರ್ಣತೆಗೆ ಸಮನಾಗಿರುತ್ತದೆ ಏಕೆಂದರೆ ಅದು ನಾವು ಮಾಡುವ ಪುನರಾವರ್ತಿತ ಕರೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ.

ಅನುಸಂಧಾನ (ಪುನರಾವರ್ತನೆ)

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆಯನ್ನು ಸುಧಾರಿಸಲು ನಾವು ಮೇಲಿನ ವಿಧಾನವನ್ನು ಪುನರಾವರ್ತಿತವಾಗಿ ಅನುಸರಿಸಬಹುದು. ಪುನರಾವರ್ತನೆಯು ಸ್ಟಾಕ್ ಫ್ರೇಮ್‌ಗಳನ್ನು ಬಳಸುತ್ತದೆ, ಅದು ಮೆಮೊರಿಯನ್ನು ಬಳಸುತ್ತದೆ. ಆದ್ದರಿಂದ, ಪುನರಾವರ್ತನೆಯ ದ್ರಾವಣದಲ್ಲಿ, ನಾವು ತಡೆಯುತ್ತೇವೆ ಪುನರಾವರ್ತಿತ ಕರೆ ಲೋಡ್ ಮತ್ತು ಎಡ ಅಥವಾ ಬಲ ಇರುವ ನೋಡ್ ಅನ್ನು ನಾವು ಹೊಡೆಯುವವರೆಗೆ ನಮ್ಮ ಹುಡುಕಾಟ ಹಾದಿಯಲ್ಲಿರುವ ಮರದ ಕೆಳಗೆ ಹೋಗಿ ಸಾಂಕೇತಿಕಕೊಂಡಿಯು. ನಾವು ಹೊಂದಿರುವಾಗ 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, ಬಲ ಸಬ್‌ಟ್ರೀಗೆ ನೆಗೆಯುವುದಕ್ಕೆ
    2. ಮೌಲ್ಯವು ಕಡಿಮೆ ಅಥವಾ ಸಮನಾಗಿದ್ದರೆ ಬೇರೆ root.val
      1. ರೂಟ್.ಲೆಫ್ಟ್ NULL ಆಗಿದ್ದರೆ
        1. root.left = ಕೊಟ್ಟಿರುವ ಮೌಲ್ಯದೊಂದಿಗೆ ಹೊಸ ನೋಡ್
        2. ರಿಟರ್ನ್ ಬೇರು
      2. ಬೇರೆ, ಹೊಂದಿಸಿ
        1. ಬೇರು = root.left, ಎಡ ಸಬ್‌ಟ್ರೀಗೆ ನೆಗೆಯುವುದಕ್ಕೆ
  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

ಬೈನರಿ ಸರ್ಚ್ ಟ್ರೀ ಲೀಟ್‌ಕೋಡ್ ಪರಿಹಾರಕ್ಕೆ ಸೇರಿಸುವ ಸಂಕೀರ್ಣತೆ ವಿಶ್ಲೇಷಣೆ

ಸಮಯ ಸಂಕೀರ್ಣತೆ

ಒ (ಎಚ್) = ಬಿಎಸ್ಟಿ ಎತ್ತರ = ಲಾಗ್ ಎನ್ (ಅಲ್ಲಿ ಬಿಎಸ್‌ಟಿಯಲ್ಲಿ ಎನ್ = ನೋಡ್‌ಗಳ ಸಂಖ್ಯೆ) ಸರಾಸರಿ ಸಂದರ್ಭಗಳಲ್ಲಿ. ಆದರೆ ಒ (ಎನ್) ಮರವು ಓರೆಯಾದಾಗ ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ. ಮತ್ತೊಮ್ಮೆ, ಸಮಯದ ಸಂಕೀರ್ಣತೆಯು ಗಮ್ಯಸ್ಥಾನವನ್ನು ತಲುಪಲು ನಾವು ಮಾಡುವ ಪುನರಾವರ್ತನೆಗಳ ಸಂಖ್ಯೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ, ಅದರ ನಂತರ ನಿರ್ದಿಷ್ಟ ನೋಡ್ ಅನ್ನು ಸೇರಿಸಬೇಕು ಮತ್ತು ಅದು ಮರದ ರಚನೆಯನ್ನು ಅವಲಂಬಿಸಿರುತ್ತದೆ.

ಬಾಹ್ಯಾಕಾಶ ಸಂಕೀರ್ಣತೆ

ಒ (1). ಕೆಟ್ಟ ಸಂದರ್ಭದಲ್ಲಿ ಸಹ, ನಾವು ಅಸ್ಥಿರಗಳಿಗಾಗಿ ಸ್ಥಿರ ಸ್ಥಳವನ್ನು ಮಾತ್ರ ಬಳಸುತ್ತೇವೆ.