Вставте в двійкове дерево пошуку рішення штрих-коду  


Рівень складності Medium
Часто запитують у Амазонка Apple Atlassian Facebook Google Microsoft
алгоритми Бінарне дерево пошуку кодування інтерв'ю інтерв'юпідготовка LeetCode LeetCodeSolutions

У цій задачі ми отримуємо кореневий вузол a Бінарне дерево пошуку що містить цілі значення та ціле значення вузла, яке ми повинні додати у бінарне дерево пошуку та повернути його структуру. Після вставки елемента в BST, ми повинні надрукувати його 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

Пояснення

Вставте в двійкове дерево пошуку рішення штрих-кодуPin

Вставте в двійкове дерево пошуку рішення штрих-кодуPin

Підхід (Рекурсивний 

Для того, щоб вирішити, куди слід вставити будь-який даний вузол у наше Бінарне дерево пошуку, ми повинні встановити шлях від кореня до відповідного вузла, лівий / правий дочірній елемент якого буде даним вузлом.

Ми можемо вирішити це рекурсивно, передавши завдання від задачі до її підзадачі. У цьому випадку вставка нового вузла в дерево означає вставлення його або в його ліве піддерево, або в праве піддерево. Ця ж ідея також стосується будь-яких подальших піддерев. Нам потрібно створити базовий випадок. Коли ми доходимо до точки, де знаходиться кореневий вузол будь-якого піддерева NULL, це означало б, що ми дійшли до кінця шляху, щоб вставити цільовий вузол. Отже, ми повертаємо a новий адреса вузла, що має значення вузла як задане значення. Бінарні дерева пошуку мають значну перевагу для пошуку будь-якого довільного елемента в O (logN) час під середніми випадками. Отже, у цьому випадку ми знаходимо позицію нового вузла, який потрібно вставити за ефективний час.

Дивись також
Домашнє Розбійник II Рішення Leetcode

Алгоритм

  1. Створіть функцію insertIntoBST () який повертає адресу корінь BST після вставки даного вузол
  2. insertIntoBST () має два параметри: корінь дерева і значення вузла, який потрібно вставити
  3. Функція виконає наступне:
    • If корінь is НУЛЬ, повернути новий вузол дерева зі значенням, таким самим, що і дане значення
    • Якщо задане значення великий ніж значення корінь вузол, а потім викликати ту саму проблему до правого піддерева, а потім повернути корінь
      • корінь.право = insertIntoBST (корінь-> право, значення)
      • повертати корінь
    • Інший пошук у лівому піддереві як:
      • корінь.ліворуч= insertIntoBST (root.left, значення)
      • повертати корінь
  4. Роздрукуйте обхід обходу дерева двійкового пошуку

Реалізація вставки в двійкове дерево пошуку рішення Leetcode

Програма С ++

#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

Аналіз складності вставки в двійкове дерево рішення рішення Leetcode

Складність часу

O (H) = Висота BST = logN (де N = кількість вузлів у BST) у середніх випадках (оскільки ми робимо logN рекурсивні виклики). Але O (N) в гіршому випадку, коли дерево перекошене. Оскільки у випадку, коли дерево перекошене, пошук стає лінійний один.

Дивись також
Додайте двійкове рішення Leetcode

Космічна складність

O (H) в середніх випадках. O (N) в гіршому випадку. Випадок із просторовою складністю тут такий же, як і складність часу, оскільки це залежить від кількості рекурсивних викликів, які ми робимо.

Підхід (Ітеративний 

Ми можемо слідувати вищезазначеному підходу ітеративно для покращення складності простору. Рекурсія використовує стекові кадри, які споживають пам'ять. Отже, в ітераційному рішенні ми запобігаємо рекурсивне навантаження виклику і спускатися по дереву на нашому шляху пошуку, поки ми не вдаримось у вузол, лівий чи правий NULL. Коли ми маємо root.left / root.right = NULL, ми встановлюємо цей вузол рівним новому вузлу зі значенням, однаковим із заданим значенням. Зверніть увагу, що ми визначаємо шлях шляхом порівняння значень з корінь значення в кожному виклику рекурсії.

Алгоритм

  1. У нас знову є insertIntoBST () з тією ж метою, що і вище
  2. Якщо корінь дорівнює NULL
    1. повертає новий вузол зі значенням, однаковим із заданим значенням
  3. Скажімо, створіть копію root манекен маніпулювати змістом BST
  4. У той час як манекен is НЕ NULL
    1. якщо задане значення більше ніж корінь.валь
      1. If корінь.право дорівнює NULL
        1. корінь.право = новий вузол із заданим значенням
        2. повертати корінь
      2. В іншому, встановити
        1. корінь = корінь.право, щоб перейти до правого піддерева
    2. Інакше, якщо значення менше або дорівнює корінь.валь
      1. Якщо root.left має значення NULL
        1. корінь.ліворуч = новий вузол із заданим значенням
        2. повертати корінь
      2. В іншому, встановити
        1. корінь = корінь.ліворуч, щоб перейти до лівого піддерева
  5. Роздрукуйте Inverse обхід BST

Реалізація вставки в двійкове дерево пошуку рішення Leetcode

Програма С ++

#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

Аналіз складності вставки в двійкове дерево рішення рішення Leetcode

Складність часу

O (H) = Висота BST = logN (де N = кількість вузлів у BST) у середніх випадках. Але O (N) в гіршому випадку, коли дерево перекошене. Знову ж таки, складність часу залежить від кількості ітерацій, які ми робимо для досягнення пункту призначення, після чого даний вузол слід вставити, і це залежить від структури дерева.

Дивись також
Вид зверху бінарного дерева

Космічна складність

O (1). Навіть у гіршому випадку ми використовуємо постійний простір лише для змінних.