Рубрики

Объединить два BST с ограниченным дополнительным пространством

Учитывая два дерева двоичного поиска (BST), выведите элементы обоих BST в отсортированном виде. Ожидаемая сложность по времени O (m + n) где m — количество узлов в первом дереве, а n — количество узлов во втором дереве. Максимально допустимое вспомогательное пространство составляет O (высота первого дерева + высота второго дерева).

Примеры:

First BST 
       3
    /     \
   1       5
Second BST
    4
  /   \
2       6
Output: 1 2 3 4 5 6


First BST 
          8
         / \
        2   10
       /
      1
Second BST 
          5
         / 
        3  
       /
      0
Output: 0 1 2 3 5 8 10 

Источник: вопрос об интервью Google

Подобный вопрос обсуждался ранее. Давайте сначала обсудим уже обсужденные методы предыдущего поста, который был для Сбалансированных BST. Метод 1 может быть применен и здесь, но сложность времени будет O (n ^ 2) в худшем случае. Метод 2 также может быть применен здесь, но требуемое дополнительное пространство будет O (n), что нарушает ограничение, данное в этом вопросе. Метод 3 может быть применен здесь, но шаг 3 метода 3 не может быть выполнен в O (n) для несбалансированного BST.

Спасибо Кумару за предложение следующего решения.

Идея состоит в том, чтобы использовать итеративный обход по порядку . Мы используем два вспомогательных стека для двух BST. Поскольку нам нужно печатать элементы в отсортированном виде, всякий раз, когда мы получаем элемент меньшего размера из любого дерева, мы печатаем его. Если элемент больше, мы помещаем его обратно в стек для следующей итерации.

C ++

#include <bits/stdc++.h>

using namespace std;

  
// Структура узла BST

class node 

    public:

    int data; 

    node *left; 

    node *right; 

}; 

  
// .................... ЗАПУСК СТЕКОВОЙ СВЯЗИ ....................
// узел стека

class snode 

    public:

    node *t; 

    snode *next; 

}; 

  
// Функция для добавления элемента k в стек

void push(snode **s, node *k) 

    snode *tmp = new snode(); 

  

    // выполнить проверку памяти здесь

    tmp->t = k; 

    tmp->next = *s; 

    (*s) = tmp; 

  
// Функция для извлечения элемента t из стека
node *pop(snode **s) 

    node *t; 

    snode *st; 

    st=*s; 

    (*s) = (*s)->next; 

    t = st->t; 

    free(st); 

    return t; 

  
// Функция, чтобы проверить, пуст ли стек

int isEmpty(snode *s) 

    if (s == NULL ) 

        return 1; 

  

    return 0; 


// .................... КОНЕЦ ПЕРСПЕКТИВ, СВЯЗАННЫХ С STACK ....................

  

  
/ * Служебная функция для создания нового узла двоичного дерева * /

node* newNode (int data) 

    node *temp = new node; 

    temp->data = data; 

    temp->left = NULL; 

    temp->right = NULL; 

    return temp; 

  
/ * Утилита для печати обхода Inoder бинарного дерева * /

void inorder(node *root) 

    if (root != NULL) 

    

        inorder(root->left); 

        cout<<root->data<<" "

        inorder(root->right); 

    

  
// Функция для печати данных двух BST в отсортированном порядке

void merge(node *root1, node *root2) 

    // s1 - стек для хранения узлов первого BST

    snode *s1 = NULL; 

  

    // Текущий узел первого BST

    node *current1 = root1; 

  

    // s2 - стек для хранения узлов второго BST

    snode *s2 = NULL; 

  

    // Текущий узел второго BST

    node *current2 = root2; 

  

    // Если первый BST пуст, то вывод имеет порядок

    // обход второго BST

    if (root1 == NULL) 

    

        inorder(root2); 

        return

    

    // Если второй BST пуст, то выходные данные имеют порядок

    // обход первого BST

    if (root2 == NULL) 

    

        inorder(root1); 

        return

    

  

    // Запускаем цикл, пока есть узлы, которые еще не напечатаны.

    // Узлы могут быть в стеке (исследованы, но не распечатаны)

    // или еще не исследовано

    while (current1 != NULL || !isEmpty(s1) || 

        current2 != NULL || !isEmpty(s2)) 

    

        // Следующие шаги следуют итеративному обходу Inorder

        if (current1 != NULL || current2 != NULL ) 

        

            // Достичь самого левого узла обоих BST и пуш-предков

            // крайние левые узлы для стека s1 и s2 соответственно

            if (current1 != NULL) 

            

                push(&s1, current1); 

                current1 = current1->left; 

            

            if (current2 != NULL) 

            

                push(&s2, current2); 

                current2 = current2->left; 

            

  

        

        else

        

            // Если мы достигаем NULL-узла и один из стеков пуст,

            // тогда одно дерево исчерпано, распечатать другое дерево

            if (isEmpty(s1)) 

            

                while (!isEmpty(s2)) 

                

                    current2 = pop (&s2); 

                    current2->left = NULL; 

                    inorder(current2); 

                

                return

            

            if (isEmpty(s2)) 

            

                while (!isEmpty(s1)) 

                

                    current1 = pop (&s1); 

                    current1->left = NULL; 

                    inorder(current1); 

                

                return

            

  

            // Извлекаем элемент из обоих стеков и сравниваем

            // всплывающие элементы

            current1 = pop(&s1); 

            current2 = pop(&s2); 

  

            // Если элемент первого дерева меньше, выведите его

            // и нажмите правое поддерево. Если элемент больше,

            // затем мы возвращаем его обратно в соответствующий стек

            if (current1->data < current2->data) 

            

                cout<<current1->data<<" "

                current1 = current1->right; 

                push(&s2, current2); 

                current2 = NULL; 

            

            else

            

                cout<<current2->data<<" "

                current2 = current2->right; 

                push(&s1, current1); 

                current1 = NULL; 

            

        

    

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main() 

    node *root1 = NULL, *root2 = NULL; 

  

    / * Давайте создадим следующее дерево как первое дерево

            3

        / /

        1 5

    * /

    root1 = newNode(3); 

    root1->left = newNode(1); 

    root1->right = newNode(5); 

  

    / * Давайте создадим следующее дерево как второе дерево

            4

        / /

        2 6

    * /

    root2 = newNode(4); 

    root2->left = newNode(2); 

    root2->right = newNode(6); 

  

    // Печать отсортированных узлов обоих деревьев

    merge(root1, root2); 

  

    return 0; 

  
// Этот код предоставлен rathbhupendra

С

#include<stdio.h>
#include<stdlib.h>

  
// Структура узла BST

struct node

{

    int data;

    struct node *left;

    struct node *right;

};

  
// .................... ЗАПУСК СТЕКОВОЙ СВЯЗИ ....................
// узел стека

struct snode

{

    struct node  *t;

    struct snode *next;

};

  
// Функция для добавления элемента k в стек

void push(struct snode **s, struct node *k)

{

    struct snode *tmp = (struct snode *) malloc(sizeof(struct snode));

  

    // выполнить проверку памяти здесь

    tmp->t = k;

    tmp->next = *s;

    (*s) = tmp;

}

  
// Функция для извлечения элемента t из стека

struct node *pop(struct snode **s)

{

    struct  node *t;

    struct snode *st;

    st=*s;

    (*s) = (*s)->next;

    t = st->t;

    free(st);

    return t;

}

  
// Функция, чтобы проверить, пуст ли стек

int isEmpty(struct snode *s)

{

    if (s == NULL )

        return 1;

  

    return 0;

}
// .................... КОНЕЦ ПЕРСПЕКТИВ, СВЯЗАННЫХ С STACK ....................

  

  
/ * Служебная функция для создания нового узла двоичного дерева * /

struct node* newNode (int data)

{

    struct node *temp = (struct node*)malloc(sizeof(struct node));

    temp->data = data;

    temp->left = NULL;

    temp->right = NULL;

    return temp;

}

  
/ * Утилита для печати обхода Inoder бинарного дерева * /

void inorder(struct node *root)

{

    if (root != NULL)

    {

        inorder(root->left);

        printf("%d ", root->data);

        inorder(root->right);

    }

}

  
// Функция для печати данных двух BST в отсортированном порядке

void  merge(struct node *root1, struct node *root2)

{

    // s1 - стек для хранения узлов первого BST

    struct snode *s1 = NULL;

  

    // Текущий узел первого BST

    struct node  *current1 = root1;

  

    // s2 - стек для хранения узлов второго BST

    struct snode *s2 = NULL;

  

    // Текущий узел второго BST

    struct node  *current2 = root2;

  

    // Если первый BST пуст, то вывод имеет порядок

    // обход второго BST

    if (root1 == NULL)

    {

        inorder(root2);

        return;

    }

    // Если второй BST пуст, то выходные данные имеют порядок

    // обход первого BST

    if (root2 == NULL)

    {

        inorder(root1);

        return ;

    }

  

    // Запускаем цикл, пока есть узлы, которые еще не напечатаны.

    // Узлы могут быть в стеке (исследованы, но не распечатаны)

    // или еще не исследовано

    while (current1 != NULL || !isEmpty(s1) ||

          current2 != NULL || !isEmpty(s2))

    {

        // Следующие шаги следуют итеративному обходу Inorder

        if (current1 != NULL || current2 != NULL )

        {

            // Достичь самого левого узла обоих BST и пуш-предков

            // крайние левые узлы для стека s1 и s2 соответственно

            if (current1 != NULL)

            {

                push(&s1, current1);

                current1 = current1->left;

            }

            if (current2 != NULL)

            {

                push(&s2, current2);

                current2 = current2->left;

            }

  

        }

        else

        {

            // Если мы достигаем NULL-узла и один из стеков пуст,

            // тогда одно дерево исчерпано, распечатать другое дерево

            if (isEmpty(s1))

            {

                while (!isEmpty(s2))

                {

                    current2 = pop (&s2);

                    current2->left = NULL;

                    inorder(current2);

                }

                return ;

            }

            if (isEmpty(s2))

            {

                while (!isEmpty(s1))

                {

                    current1 = pop (&s1);

                    current1->left = NULL;

                    inorder(current1);

                }

                return ;

            }

  

            // Извлекаем элемент из обоих стеков и сравниваем

            // всплывающие элементы

            current1 = pop(&s1);

            current2 = pop(&s2);

  

            // Если элемент первого дерева меньше, выведите его

            // и нажмите правое поддерево. Если элемент больше,

            // затем мы возвращаем его обратно в соответствующий стек

            if (current1->data < current2->data)

            {

                printf("%d ", current1->data);

                current1 = current1->right;

                push(&s2, current2);

                current2 = NULL;

            }

            else

            {

                printf("%d ", current2->data);

                current2 = current2->right;

                push(&s1, current1);

                current1 = NULL;

            }

        }

    }

}

  
/ * Программа драйвера для проверки вышеуказанных функций * /

int main()

{

    struct node  *root1 = NULL, *root2 = NULL;

  

    / * Давайте создадим следующее дерево как первое дерево

            3

          / /

         1 5

     * /

    root1 = newNode(3);

    root1->left = newNode(1);

    root1->right = newNode(5);

  

    / * Давайте создадим следующее дерево как второе дерево

            4

          / /

         2 6

     * /

    root2 = newNode(4);

    root2->left = newNode(2);

    root2->right = newNode(6);

  

    // Печать отсортированных узлов обоих деревьев

    merge(root1, root2);

  

    return 0;

}

Выход:

1 2 3 4 5 6

Сложность времени: O (m + n)
Вспомогательное пространство: O (высота первого дерева + высота второго дерева)

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Объединить два BST с ограниченным дополнительным пространством

0.00 (0%) 0 votes