Ба Solution Leetcode Tree Binary Search Tree ворид кунед


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад Amazon себ Atlassian Facebook Google Microsoft
Дарахти ҷустуҷӯи бинарӣ

Дар ин масъала, ба мо гиреҳи решаи a дода мешавад Дарахти ҷустуҷӯи бинарӣ ки дорои арзишҳои бутун ва арзиши бутуни гиреҳ мебошанд, ки мо бояд онҳоро ба дарахти ҷустуҷӯи бинарӣ илова кунем ва сохтори онро баргардонем. Пас аз ворид кардани элемент ба BST, мо бояд Inverse 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

Шарҳ

Ба Solution Leetcode Tree Binary Search Tree ворид кунед

Ба Solution Leetcode Tree Binary Search Tree ворид кунед

Равиш (Рекурсивӣ)

Барои он ки қарор қабул кунем, ки ягон гиреҳи додашуда ба дарахти ҷустуҷӯи бинарии мо дар куҷо гузошта шавад, мо бояд аз реша то гиреҳи мувофиқе роҳ созем, ки кудаки чап / рост гиреҳ дода шавад.

Мо метавонем инро тавассути интиқол додани вазифа аз мушкилот ба зерпроблемаи он рекурсивӣ ҳал кунем. Дар ин ҳолат, гузоштани гиреҳи нав ба дарахт маънои онро дорад, ки онро ба зери дарахти чап ё рости он дохил кунед. Худи ҳамин идея барои ҳар гуна зерсохторҳои минбаъда низ мавҷуд аст. Мо бояд як парвандаи пойгоҳӣ созем. Вақте ки мо ба нуқтае расидем, ки гиреҳи решаи ҳар як дарахт аст ночиз, ин маънои онро дошт, ки мо барои гузоштани гиреҳи ҳадаф ба поёни роҳ расидем. Ҳамин тавр, мо бармегардем a нав суроғаи гиреҳ дорои арзиши гиреҳ ҳамчун арзиши додашуда. Дарахтони ҷустуҷӯии дутарафа барои ҷустуҷӯи ҳама гуна унсури худсарона бартарии назаррас доранд О (logN) вақт дар ҳолатҳои миёна. Ҳамин тавр, дар ин ҳолат, мо мавқеи гиреҳи навро дар вақти муассир ворид мекунем.

Алгоритм

  1. Функсия эҷод кунед insertIntoBST () ки суроғаи реша пас аз гузоштани додашуда гиреҳ
  2. insertIntoBST () ду параметр дорад: реша дарахт ва арзиши гиреҳ гузошта мешавад
  3. Функсия амалҳои зеринро иҷро мекунад:
    • If реша is НУЛ, гиреҳи дарахти навро бо арзиши ҳамон арзиши додашуда баргардонед
    • Агар арзиши додашуда бештар аз арзиши реша гиреҳ, пас худи ҳамон мушкилотро ба зердарахти рост даъват кунед ва баъд решаро баргардонед
      • реша. рост = insertIntoBST (реша-> рост, арзиш)
      • бозгашт реша
    • Ҷустуҷӯи дигар дар зергурӯҳи чап ба тариқи зайл:
      • решаи чап= insertIntoBST (root.left, арзиш)
      • бозгашт реша
  4. Гузариши inorder дарахти ҷустуҷӯи бинариро чоп кунед

Татбиқи Воридкунӣ ба Solution Leetcode Tree Binary Search Tree

Барномаи 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

Таҳлили мураккабии дохилкунӣ ба Solution Leetcode Tree Binary Search Tree

Мураккабии вақт

О (Н) = Баландии BST = logN (ки дар он N = шумораи гиреҳҳо дар BST) дар ҳолатҳои миёна (вақте ки мо logN зангҳои рекурсивӣ мекунем). Аммо О (Н) дар бадтарин ҳолат, вақте ки дарахт як каҷ аст. Зеро дар сурати тахриб шудани дарахт, ҷустуҷӯ а мешавад хатти як

Мураккабии фазо

О (Н) дар ҳолатҳои миёна. О (Н) дар бадтарин ҳолат. Ҳолати мураккабии кайҳон бо мураккабии вақт монанд аст, зеро он ба шумораи зангҳои рекурсивӣ вобаста аст.

Равиш (Итеративӣ)

Мо метавонем бо усули дар боло зикршуда такмил диҳем, то мураккабии фазоро беҳтар намоем. Рекурсия фреймҳои стекро истифода мебарад, ки хотираро сарф мекунанд. Пас, дар ҳалли такроршаванда мо пешгирӣ мекунем бори рекурсивӣ ва то ба гиреҳе зарба занем, ки яке аз чап ё росташ бошад ночиз. Вақте ки мо дорем root.left / root.right = NULL, мо ин гиреҳро ба гиреҳи нав баробар бо арзиши якхела гузоштем. Дар хотир доред, ки мо роҳро бо муқоисаи арзишҳо бо реша арзиш дар ҳар як занги рекурсионӣ.

Алгоритм

  1. Мо боз як insertIntoBST () бо ҳамон мақсад, ки дар боло зикр шудааст
  2. Агар реша бекор аст
    1. гиреҳи навро бо арзиши якхела бо арзиши додашуда баргардонед
  3. Нусхаи решаро эҷод кунед, бигӯед данд ки мундариҷаи БСТ-ро таҳрир кунанд
  4. ҳол он данд is не ночиз
    1. агар арзиши додашуда аз root.val
      1. If реша. рост бекор аст
        1. реша. рост = гиреҳи нав бо арзиши додашуда
        2. бозгашт реша
      2. Дигар, муқаррар карда шудааст
        1. реша = реша. рост, ҷаҳидан ба зери дарахти рост
    2. Дигар агар арзиши он камтар ё баробар бошад root.val
      1. Агар root.left NULL бошад
        1. решаи чап = гиреҳи нав бо арзиши додашуда
        2. бозгашт реша
      2. Дигар, муқаррар карда шудааст
        1. реша = решаи чап, ҷаҳидан ба зери дарахти чап
  5. Гузариши Inorder аз BST -ро чоп кунед

Татбиқи Воридкунӣ ба Solution Leetcode Tree Binary Search Tree

Барномаи 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

Таҳлили мураккабии дохилкунӣ ба Solution Leetcode Tree Binary Search Tree

Мураккабии вақт

О (Н) = Баландии BST = logN (ки дар он N = шумораи гиреҳҳо дар BST) дар ҳолатҳои миёна. Аммо О (Н) дар бадтарин ҳолат, вақте ки дарахт як каҷ аст. Боз ҳам, мураккабии вақт аз шумораи такрориҳо барои расидан ба манзил вобаста аст ва пас аз он гиреҳи додашуда бояд ворид карда шавад ва он аз стуктураи дарахт вобаста аст.

Мураккабии фазо

О (1). Ҳатто дар ҳолати бадтарин, мо фақат фазои доимиро барои тағирёбандаҳо истифода мебарем.