אַרייַנשטעלן אַ ביינערי זוכן בוים לעעטקאָדע סאַלושאַן


שוועריקייט לעוועל מיטל
אָפט געבעטן אין אַמאַזאָן עפּל אַטלאַססיאַן facebook גוגל מייקראָסאָפֿט
ביינערי זוכן בוים

אין דעם פּראָבלעם, מיר באַקומען די וואָרצל נאָדע פון ​​אַ ביינערי זוכן בוים כּולל ינטעגער וואַלועס און אַ גאַנץ נומער פון אַ נאָדע וואָס מיר האָבן צו לייגן אין די ביינערי זוכן בוים און צוריקקומען די סטרוקטור. נאָך ינסערטינג דעם עלעמענט אין די BST, מיר מוזן דרוקן די ינאָרדער טראַווערסאַל.

בייַשפּיל

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 () וואָס קערט דער אַדרעס פון די וואָרצל פון BST נאָך ינסערטינג די געגעבן נאָדע
  2. insertIntoBST () האט צוויי פּאַראַמעטערס: וואָרצל פון דעם בוים און ווערט פון די נאָדע צו זיין ינסערטאַד
  3. די פֿונקציע וועט טאָן די פאלגענדע:
    • If וואָרצל is נול, צוריקקומען אַ נייַ בוים נאָדע מיט ווערט זעלביקער ווי די געגעבן ווערט
    • אויב די געגעבן ווערט איז גרעסער ווי ווערט פון וואָרצל נאָדע, דאַן רופן די זעלבע פּראָבלעם צו די רעכט סובטרעע און צוריקקומען די וואָרצל
      • root.right = insertIntoBST (וואָרצל-> רעכט, ווערט)
      • צוריקקומען וואָרצל
    • אַנדערש זוכן אין די לינקס סובטרעמע ווי:
      • root.left= insertIntoBST (root.left, ווערט)
      • צוריקקומען וואָרצל
  4. דרוק דעם ינאָרדער דורך די ביינערי זוכן בוים

ימפּלעמענטאַטיאָן פון ינסערט אין אַ ביינערי זוכן בוים לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון ינסערט אין אַ ביינערי זוכן בוים לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אוי) = הייך פון BST = logN (וווּ N = נומער פון נאָדעס אין BST) אין דורכשניטלעך קאַסעס (ווען מיר מאַכן רופן רעקורסיווע רופן). אָבער אָ (N) אין די ערגסט פאַל ווען דער בוים איז אַ קרום. ווייַל אין פאַל דער בוים איז סקיוד, די זוכן ווערט אַ לינעאַר איינער.

אָרט קאַמפּלעקסיטי

אוי) אין דורכשניטלעך פאלן. אָ (N) אין די ערגסטע פאַל. דער פאַל מיט ספעיס קאַמפּלעקסיטי איז זעלביקער ווי צייט קאַמפּלעקסיטי דאָ, ווייַל עס דעפּענדס אויף די נומער פון רעקורסיווע רופט מיר מאַכן.

צוגאַנג (יטעראַטיוו)

מיר קענען נאָכגיין די אויבן צוגאַנג יטעראַטיוולי צו פֿאַרבעסערן פּלאַץ קאַמפּלעקסיטי. רעקורסיאָן ניצט סטאַק ראָמען וואָס פאַרנוצן זכּרון. אַזוי, אין די יטעראַטיווע לייזונג, מיר פאַרמייַדן די רעקורסיווע רופן מאַסע און גיין אַראָפּ די בוים אויף אונדזער זוכן דרך ביז מיר שלאָגן אַ נאָדע וועמענס לינקס אָדער רעכט איז נאַל. ווען מיר האָבן root.left / root.right = NULL, מיר שטעלן דעם נאָדע גלייַך צו אַ נייַע נאָדע מיט די זעלבע ווערט ווי די געגעבן ווערט. באַמערקונג אַז מיר באַשליסן דעם וועג דורך קאַמפּערינג די וואַלועס מיט וואָרצל ווערט אין יעדער רעקורסיאָן רופן.

אַלגאָריטהם

  1. מיר ווידער האָבן אַ insertIntoBST () פֿאַר דער זעלביקער ציל ווי אויבן
  2. אויב די וואָרצל איז נול
    1. צוריקקומען נייַ נאָדע מיט ווערט זעלביקער ווי די געגעבן ווערט
  3. שאַפֿן אַ קאָפּיע פון ​​וואָרצל, זאָגן דאַמי צו מאַניפּולירן די אינהאַלט פון בסט
  4. ווייַלע דאַמי is טאָן נאַל
    1. אויב געגעבן ווערט איז גרעסער ווי root.val
      1. If root.right איז נול
        1. root.right = נייַ נאָדע מיט געגעבן ווערט
        2. צוריקקומען וואָרצל
      2. אַנדערש, שטעלן
        1. וואָרצל = root.right, צו שפּרינגען צו די רעכט סובטרעמע
    2. אַנדערש אויב די ווערט איז ווייניקער ווי אָדער גלייַך צו root.val
      1. אויב root.left איז NULL
        1. root.left = נייַ נאָדע מיט געגעבן ווערט
        2. צוריקקומען וואָרצל
      2. אַנדערש, שטעלן
        1. וואָרצל = root.left, צו שפּרינגען צו לינקס סובטרעמע
  5. דרוק די ינאָרדער דורך די BST

ימפּלעמענטאַטיאָן פון ינסערט אין אַ ביינערי זוכן בוים לעעטקאָדע סאַלושאַן

C ++ פּראָגראַם

#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;
}

Java פּראָגראַם

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

קאַמפּלעקסיטי אַנאַליסיס פון ינסערט אין אַ ביינערי זוכן בוים לעעטקאָדע סאַלושאַן

צייט קאַמפּלעקסיטי

אוי) = הייך פון BST = logN (וווּ N = נומער פון נאָודז אין BST) אין דורכשניטלעך קאַסעס. אָבער אָ (N) אין די ערגסט פאַל ווען דער בוים איז אַ קרום. ווידער, די צייט קאַמפּלעקסיטי איז אָפענגיק אויף די נומער פון יטעריישאַנז מיר דערגרייכן צו די דעסטיניישאַן נאָך וואָס די געגעבן נאָדע זאָל זיין ינסערטאַד און עס דעפּענדס אויף די בוים סטרוקטור.

אָרט קאַמפּלעקסיטי

אָ (1). אפילו אין די ערגסט פאַל, מיר נאָר נוצן קעסיידערדיק פּלאַץ פֿאַר וועריאַבאַלז.