દ્વિસંગી શોધ વૃક્ષ લીટકોડ સોલ્યુશનમાં દાખલ કરો


મુશ્કેલી સ્તર મધ્યમ
વારંવાર પૂછવામાં આવે છે એમેઝોન સફરજન Atlassian ફેસબુક Google માઈક્રોસોફ્ટ
દ્વિસંગી શોધ વૃક્ષ

આ સમસ્યામાં, અમને 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

સમજૂતી

દ્વિસંગી શોધ વૃક્ષ લીટકોડ સોલ્યુશનમાં દાખલ કરો

દ્વિસંગી શોધ વૃક્ષ લીટકોડ સોલ્યુશનમાં દાખલ કરો

અભિગમ (પુનરાવર્તિત)

આપેલ દ્વિસંગી શોધ વૃક્ષમાં આપેલ નોડ ક્યાં દાખલ કરવા જોઈએ તે નક્કી કરવા માટે, આપણે મૂળથી સંબંધિત નોડ તરફનો માર્ગ બનાવવો આવશ્યક છે, જેનો ડાબો / જમણો બાળક આપેલ નોડ હશે.

અમે સમસ્યામાંથી તેની પેટા-સમસ્યાનું કાર્ય પસાર કરીને આને વારંવાર ઉકેલી શકીએ છીએ. આ કિસ્સામાં, એક નોડને ઝાડમાં દાખલ કરવાનો અર્થ છે કે તેને ક્યાં તો તેની ડાબી સબટ્રી અથવા જમણી સબટ્રીમાં દાખલ કરવું. આ જ વિચાર આગળના કોઈપણ પેટાશીલો માટે પણ ધરાવે છે. આપણે બેઝ કેસ ગોઠવવાની જરૂર છે. જ્યારે આપણે એવા બિંદુએ પહોંચીએ જ્યાં કોઈપણ પેટાશ્રીનું મૂળ નોડ હોય NULL, તેનો અર્થ એ થશે કે લક્ષ્ય નોડ દાખલ કરવા માટે આપણે પાથની છેડે પહોંચી ગયા છે. તેથી, અમે એ નવા આપેલ કિંમત તરીકે નોડ મૂલ્ય ધરાવતા નોડ સરનામું. દ્વિસંગી શોધ વૃક્ષો માં કોઈપણ મનસ્વી તત્વ શોધવા માટે એક મહત્વપૂર્ણ ફાયદો છે ઓ (લોગએન) સરેરાશ કેસ હેઠળ સમય. તેથી, આ કિસ્સામાં, અમને કાર્યક્ષમ સમયમાં શામેલ કરવા માટે નવા નોડની સ્થિતિ મળી છે.

અલ્ગોરિધમ

  1. ફંકશન બનાવો insertIntoBST () જેનું સરનામું આપે છે રુટ આપેલ દાખલ કર્યા પછી બી.એસ.ટી. નોડ
  2. insertIntoBST () બે પરિમાણો છે: રુટ વૃક્ષ અને કિંમત દાખલ કરવા માટે નોડની
  3. આ કાર્ય નીચે મુજબ કરશે:
    • If રુટ is નલ, આપેલ મૂલ્ય જેટલું મૂલ્ય ધરાવતું નવું ટ્રી નોડ પાછો
    • જો આપેલ કિંમત છે વધારે ની કિંમત કરતાં રુટ નોડ, પછી તે જ સમસ્યાને જમણા સબટ્રી પર ક callલ કરો અને પછી રુટ પાછા ફરો
      • root.right = insertIntoBST (મૂળ-> અધિકાર, મૂલ્ય)
      • વળતર રુટ
    • ડાબી સબટ્રીમાં બીજું શોધ આ પ્રમાણે:
      • 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

બાઈનરી સર્ચ ટ્રી લીટકોડ સોલ્યુશનમાં દાખલ કરવાના જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એચ) = બીએસટીની Heંચાઈ = લોગએન (જ્યાં બીએસટીમાં N = નોડ્સની સંખ્યા) સરેરાશ કેસોમાં (જેમ આપણે લોગએન રિકરિવ કોલ કરીએ છીએ). પણ ઓ (એન) સૌથી ખરાબ કિસ્સામાં જ્યારે ઝાડ કાપવામાં આવેલો હોય છે. કારણ કે જો ઝાડ કાપવામાં આવે છે, તો શોધ એ બની જાય છે રેખીય એક.

જગ્યાની જટિલતા

ઓ (એચ) સરેરાશ કિસ્સાઓમાં. ઓ (એન) સૌથી ખરાબ કિસ્સામાં. સ્પેસ કોમ્પ્લેક્સિટી સાથેનો કેસ અહીં સમય જટિલતા જેવો જ છે કારણ કે તે આપણે કરેલા રિકરિવ કોલ્સની સંખ્યા પર આધારિત છે.

અભિગમ (આઇટરેટિવ)

જગ્યાની જટિલતામાં સુધારો કરવા માટે આપણે ઉપરોક્ત અભિગમને પુનરાવર્તિત રીતે અનુસરી શકીએ છીએ. રિકર્ઝન સ્ટેક ફ્રેમ્સનો ઉપયોગ કરે છે જે મેમરીનો વપરાશ કરે છે. તેથી, પુનરાવર્તિત ઉકેલમાં, આપણે અટકાવીએ છીએ પુનરાવર્તિત ક callલ લોડ અને જ્યાં સુધી અમે કોઈ નોડ કે જેની ડાબી બાજુ અથવા જમણી બાજુએ નહીં ત્યાં સુધી અમારી શોધ પથ પરના ઝાડ નીચે જાઓ NULL. જ્યારે આપણી પાસે root.left / root.right = ન્યુઅલ, અમે આ નોડ આપેલ મૂલ્યની સમાન મૂલ્યવાળા નવા નોડની સમાન સેટ કરી છે. નોંધો કે આપણે મૂલ્યોની તુલના કરીને પાથ નક્કી કરીએ છીએ રુટ દરેક રિકર્ઝન ક inલમાં મૂલ્ય.

અલ્ગોરિધમ

  1. અમે ફરીથી એક insertIntoBST () ઉપરના સમાન હેતુ માટે
  2. જો રુટ નલ છે
    1. આપેલા મૂલ્યની સમાન મૂલ્ય સાથે નોડ ન returnર પરત કરો
  3. રુટની એક ક Createપિ બનાવો, કહો ડમી બીએસટીની સામગ્રીમાં ફેરફાર કરવા
  4. જ્યારે ડમી is નથી NULL
    1. જો આપેલ મૂલ્ય કરતા વધારે હોય રૂટ.વોલ
      1. If root.right નલ છે
        1. root.right = આપેલ કિંમત સાથે નવું નોડ
        2. વળતર રુટ
      2. બાકી, સમૂહ
        1. રુટ = root.right, જમણી સબટ્રી પર જવા માટે
    2. બાકી જો કિંમત ઓછી અથવા બરાબર હોય રૂટ.વોલ
      1. જો રૂટ.લેફ્ટ નલ છે
        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

બાઈનરી સર્ચ ટ્રી લીટકોડ સોલ્યુશનમાં દાખલ કરવાના જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એચ) = બીએસટીની Heંચાઈ = લોગએન (જ્યાં બીએસટીમાં N = સંખ્યાની સંખ્યા) સરેરાશ કિસ્સાઓમાં. પણ ઓ (એન) સૌથી ખરાબ કિસ્સામાં જ્યારે ઝાડ કાપવામાં આવેલો હોય છે. ફરીથી, સમયની જટિલતા એ લક્ષ્ય સુધી પહોંચવા માટે આપણે બનાવેલા પુનરાવર્તનોની સંખ્યા પર આધારિત છે જેના પછી આપેલ નોડ દાખલ થવો જોઈએ અને તે વૃક્ષના અસ્થિર પર આધાર રાખે છે.

જગ્યાની જટિલતા

ઓ (1). સૌથી ખરાબ કિસ્સામાં પણ, આપણે ફક્ત ચલો માટે સતત જગ્યા વાપરીએ છીએ.