ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് തിരുകുക


വൈഷമ്യ നില മീഡിയം
പതിവായി ചോദിക്കുന്നു ആമസോൺ ആപ്പിൾ അത്ലഷിഅന് ഫേസ്ബുക്ക് ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
ബൈനറി തിരയൽ മരം

ഈ പ്രശ്‌നത്തിൽ, a യുടെ റൂട്ട് നോഡ് ഞങ്ങൾക്ക് നൽകിയിരിക്കുന്നു ബൈനറി തിരയൽ മരം ബൈനറി തിരയൽ‌ ട്രീയിൽ‌ ഞങ്ങൾ‌ ചേർ‌ത്ത് അതിന്റെ ഘടന മടക്കിനൽകേണ്ട ഒരു നോഡിന്റെ ഇൻ‌റിജർ‌ മൂല്യങ്ങളും ഒരു ഇൻ‌റിജർ‌ മൂല്യവും അടങ്ങിയിരിക്കുന്നു. ജിഎസ്ടിയിലേക്ക് ഘടകം തിരുകിയ ശേഷം, ഞങ്ങൾ അതിന്റെ Inorder 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

വിശദീകരണം

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് തിരുകുക

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് തിരുകുക

സമീപനം (ആവർത്തന)

ഞങ്ങളുടെ ബൈനറി തിരയൽ ട്രീയിൽ ഏതെങ്കിലും നോഡ് എവിടെ ചേർക്കണമെന്ന് തീരുമാനിക്കുന്നതിന്, റൂട്ട് മുതൽ അനുബന്ധ നോഡിലേക്കുള്ള ഒരു പാത ഞങ്ങൾ സജ്ജീകരിക്കണം, അതിന്റെ ഇടത് / വലത് കുട്ടി നൽകിയ നോഡ് ആയിരിക്കും.

ഒരു പ്രശ്‌നത്തിൽ നിന്ന് അതിന്റെ ഉപപ്രശ്നത്തിലേക്ക് ചുമതല കൈമാറുന്നതിലൂടെ നമുക്ക് ഇത് ആവർത്തിച്ച് പരിഹരിക്കാൻ കഴിയും. ഈ സാഹചര്യത്തിൽ, ഒരു പുതിയ നോഡ് ഒരു ട്രീയിൽ ഉൾപ്പെടുത്തുന്നത് അതിന്റെ ഇടത് സബ്‌ട്രീയിലേക്കോ വലത് സബ്‌ട്രീയിലേക്കോ തിരുകുക എന്നാണ്. ഇതേ ആശയം കൂടുതൽ സബ്‌ട്രീകൾക്കും ബാധകമാണ്. ഞങ്ങൾ ഒരു അടിസ്ഥാന കേസ് സജ്ജീകരിക്കേണ്ടതുണ്ട്. ഏതെങ്കിലും സബ്‌ട്രീയുടെ റൂട്ട് നോഡ് ഉള്ള ഒരു സ്ഥലത്ത് എത്തുമ്പോൾ NULL, ടാർഗെറ്റ് നോഡ് ചേർക്കുന്നതിനുള്ള പാതയുടെ അവസാനത്തിൽ ഞങ്ങൾ എത്തിയെന്നാണ് ഇതിനർത്ഥം. അതിനാൽ, ഞങ്ങൾ ഒരു മടക്കം നൽകുന്നു പുതിയ തന്നിരിക്കുന്ന മൂല്യമായി നോഡ് മൂല്യമുള്ള നോഡ് വിലാസം. ഏതെങ്കിലും ഏകപക്ഷീയമായ ഘടകത്തിനായി തിരയുന്നതിന് ബൈനറി തിരയൽ മരങ്ങൾക്ക് ഒരു പ്രധാന നേട്ടമുണ്ട് O (logN) ശരാശരി കേസുകളിൽ സമയം. അതിനാൽ, ഈ സാഹചര്യത്തിൽ, പുതിയ നോഡിന്റെ സ്ഥാനം കാര്യക്ഷമമായ സമയത്ത് ചേർക്കേണ്ടതായി ഞങ്ങൾ കാണുന്നു.

അൽഗോരിതം

  1. ഒരു ഫംഗ്ഷൻ സൃഷ്ടിക്കുക insertIntoBST () അത് വിലാസം നൽകുന്നു വേര് തന്നിരിക്കുന്നവ ഉൾപ്പെടുത്തിയ ശേഷം ജിഎസ്ടിയുടെ നോഡ്
  2. insertIntoBST () രണ്ട് പാരാമീറ്ററുകൾ ഉണ്ട്: വേര് മരത്തിന്റെ ഒപ്പം മൂല്യം ചേർക്കേണ്ട നോഡിന്റെ
  3. ഫംഗ്ഷൻ ഇനിപ്പറയുന്നവ ചെയ്യും:
    • If വേര് is ശൂന്യം, തന്നിരിക്കുന്ന മൂല്യത്തിന് തുല്യമായ ഒരു പുതിയ ട്രീ നോഡ് നൽകുക
    • നൽകിയ മൂല്യം ആണെങ്കിൽ കൂടുതൽ മൂല്യത്തേക്കാൾ വേര് നോഡ്, തുടർന്ന് അതേ പ്രശ്‌നം വലത് സബ്‌ട്രീയിലേക്ക് വിളിച്ച് റൂട്ട് നൽകുക
      • root.right = തിരുകുകഇന്റോബിഎസ്ടി (റൂട്ട്-> വലത്, മൂല്യം)
      • മടക്കം വേര്
    • ഇടത് സബ്‌ട്രീയിലെ മറ്റ് തിരയൽ:
      • root.left= തിരുകുകഇന്റോബിഎസ്ടി (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

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് തിരുകുന്നതിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (H) = ജിഎസ്ടിയുടെ ഉയരം = ലോഗ് എൻ (ഇവിടെ ബിഎസ്ടിയിലെ എൻ = നോഡുകളുടെ എണ്ണം) ശരാശരി കേസുകളിൽ (ഞങ്ങൾ ലോഗ് എൻ ആവർത്തന കോളുകൾ വിളിക്കുമ്പോൾ) പക്ഷേ O (N) വൃക്ഷം വളച്ചൊടിച്ച ഒന്നായിരിക്കുമ്പോൾ ഏറ്റവും മോശം അവസ്ഥയിൽ. കാരണം, മരം വളഞ്ഞാൽ, തിരയൽ a ആയി മാറുന്നു രേഖീയമായ ഒന്ന്.

സ്ഥല സങ്കീർണ്ണത

O (H) ശരാശരി കേസുകളിൽ. O (N) ഏറ്റവും മോശം അവസ്ഥയിൽ. സ്‌പേസ് കോംപ്ലക്‌സിറ്റിയുടെ കാര്യം ഇവിടെ ടൈം കോംപ്ലക്‌സിറ്റിക്ക് സമാനമാണ്, കാരണം ഇത് ഞങ്ങൾ ആവർത്തിച്ചുള്ള കോളുകളുടെ എണ്ണത്തെ ആശ്രയിച്ചിരിക്കുന്നു.

സമീപനം (രചന)

ബഹിരാകാശ സങ്കീർണ്ണത മെച്ചപ്പെടുത്തുന്നതിന് നമുക്ക് മുകളിലുള്ള സമീപനം ആവർത്തിച്ച് പിന്തുടരാനാകും. ആവർത്തനം മെമ്മറി ഉപയോഗിക്കുന്ന സ്റ്റാക്ക് ഫ്രെയിമുകൾ ഉപയോഗിക്കുന്നു. അതിനാൽ, ആവർത്തന പരിഹാരത്തിൽ, ഞങ്ങൾ തടയുന്നു ആവർത്തന കോൾ ലോഡ് ഇടത്തോട്ടോ വലത്തോട്ടോ ഉള്ള ഒരു നോഡ് അടിക്കുന്നതുവരെ ഞങ്ങളുടെ തിരയൽ പാതയിലെ ട്രീ താഴേക്ക് പോകുക NULL. ഉള്ളപ്പോൾ root.left / root.right = NULL, തന്നിരിക്കുന്ന മൂല്യത്തിന് തുല്യമായ മൂല്യമുള്ള ഒരു പുതിയ നോഡിന് തുല്യമാണ് ഞങ്ങൾ ഈ നോഡ് സജ്ജമാക്കുന്നത്. മൂല്യങ്ങളുമായി താരതമ്യപ്പെടുത്തി ഞങ്ങൾ പാത തീരുമാനിക്കുന്നുവെന്നത് ശ്രദ്ധിക്കുക വേര് എല്ലാ ആവർത്തന കോളിലെയും മൂല്യം.

അൽഗോരിതം

  1. ഞങ്ങൾക്ക് വീണ്ടും ഒരു insertIntoBST () മുകളിലുള്ള അതേ ആവശ്യത്തിനായി
  2. എങ്കില് വേര് NULL ആണ്
    1. തന്നിരിക്കുന്ന മൂല്യത്തിന് തുല്യമായ മൂല്യമുള്ള പുതിയ നോഡ് നൽകുക
  3. റൂട്ടിന്റെ ഒരു പകർപ്പ് സൃഷ്ടിക്കുക, പറയുക ഡമ്മി ജിഎസ്ടിയുടെ ഉള്ളടക്കം കൈകാര്യം ചെയ്യാൻ
  4. അതേസമയം ഡമ്മി is അല്ല NULL
    1. നൽകിയ മൂല്യം ഇതിലും വലുതാണെങ്കിൽ root.val
      1. If root.right NULL ആണ്
        1. root.right = നൽകിയ മൂല്യമുള്ള പുതിയ നോഡ്
        2. മടക്കം വേര്
      2. അല്ലെങ്കിൽ, സജ്ജമാക്കുക
        1. വേര് = root.right, വലത് സബ്‌ട്രീയിലേക്ക് പോകാൻ
    2. മൂല്യം കുറവോ തുല്യമോ ആണെങ്കിൽ root.val
      1. Root.left 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

ഒരു ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് തിരുകുന്നതിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (H) = ജിഎസ്ടിയുടെ ഉയരം = ലോഗ് എൻ (ഇവിടെ ബിഎസ്ടിയിലെ N = നോഡുകളുടെ എണ്ണം) ശരാശരി കേസുകളിൽ. പക്ഷേ O (N) വൃക്ഷം വളച്ചൊടിച്ച ഒന്നായിരിക്കുമ്പോൾ ഏറ്റവും മോശം അവസ്ഥയിൽ. വീണ്ടും, സമയ സങ്കീർണ്ണത ലക്ഷ്യസ്ഥാനത്തെത്താൻ ഞങ്ങൾ ചെയ്യുന്ന ആവർത്തനങ്ങളുടെ എണ്ണത്തെ ആശ്രയിച്ചിരിക്കുന്നു, അതിനുശേഷം നൽകിയ നോഡ് ചേർക്കേണ്ടതാണ്, അത് ട്രീ സ്റ്റക്ചറിനെ ആശ്രയിച്ചിരിക്കുന്നു.

സ്ഥല സങ്കീർണ്ണത

O (1). ഏറ്റവും മോശം അവസ്ഥയിൽ പോലും, വേരിയബിളുകൾക്കായി ഞങ്ങൾ സ്ഥിരമായ ഇടം മാത്രമേ ഉപയോഗിക്കുന്നുള്ളൂ.