Хязгаарлагдмал нэмэлт зайтай хоёр БСТ-ийг нэгтгэх


Хэцүү байдлын түвшин Хатуу
Байнга асуудаг Амазоны Google-ийн Microsoft- PayU Uber
Хоёртын хайлтын мод Хоёртын мод Мод

Асуудлын мэдэгдэл

"Хязгаарлагдмал нэмэлт зайтай хоёр БСТ-ийг нэгтгэх" гэсэн асуудалд танд хоёрыг өгсөн гэж заасан байдаг хоёртын хайлтын мод(BST) ба та хоёр модны элементүүдийг эрэмбэлсэн дарааллаар хэвлэх хэрэгтэй. Энэ нь ийм дарааллаар элементүүд нь нэг BST-ийнх юм шиг санагдаж байна.

Жишээ нь

Оролт

Хязгаарлагдмал нэмэлт зайтай хоёр БСТ-ийг нэгтгэх

гаралтын

Хязгаарлагдмал нэмэлт зайтай хоёр БСТ-ийг нэгтгэх

4 5 6 7 9 13

Тайлбар: Оруулсан модыг хоёуланг нь нэгтгэх замаар үүссэн шинэ модыг зураг дээр харуулав. Үр дүнгийн модны хөндлөн огтлол нь гаралтыг өгдөг.

Хязгаарлагдмал нэмэлт зайтай хоёр БСТ-ийг нэгтгэх арга

"Хязгаарлагдмал нэмэлт зайтай хоёр BST-ийг нэгтгэх" гэсэн асуудал нь биднээс нэгтгэсэн модны хөндлөн огтлолыг хэвлэхийг шаарддаг. Нэгдсэн мод нь өгөгдсөн хоёр модыг нэгтгэх замаар бий болно. Тиймээс бид өгөгдсөн модыг нэгтгэхийг хичээх болно. Гэхдээ бид модоо нэгтгэх гэж байгаа бол энэ нь илүү их зардал шаарддаг. Шууд нэгтгэхийн оронд бид өөр арга замыг бодож болно. Бид өгөгдсөн модны аль алиных нь зангилааны утгыг зөвхөн эрэмбэлсэн хэлбэрээр хэвлэх хэрэгтэй.

Үүнийг шийдвэрлэхийн тулд бид хоёр модон дээрх хайлтын модны давталтын зөрчлийг нэгэн зэрэг ажиллуулахыг хичээх болно. Хэрэв бид гүйвэл үүнийг хийж болно хөндлөн огтлолцол. Inorder traversal дээрх хоёр зангилааны утгыг харьцуулж үзээрэй. Дараа нь бид хоёуланг нь жижигрүүлж хэвлээд, зангилааны том зангилааг түлхэх болно (давталтын хөндлөн огтлолын үед ашиглах стек). Модны аль нэгийг нь хийж дуусгахад бид зангилаа үлдсэн модон дээгүүр хөндлөн гулсаж гүйх болно.

код

Хязгаарлагдмал нэмэлт зай бүхий хоёр BST-ийг нэгтгэх C ++ код

#include <bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *left;
    node *right;
};

// returns a new node with supplied data
node* create(int data)
{
    node *temp = new node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}

void inorder(node *root)
{
    if(root){
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(root->right);
    }
}

void merge(node *root1, node *root2)
{
    stack<node*> s1;node* cur1 = root1;
    stack<node*> s2;node* cur2 = root2;
    //if first tree is empty, print second tree
    if(!root1){
        inorder(root2);
        return;
    }
    // if second tree is empty, print first tree
    if(!root2){
        inorder(root2);
        return;
    }
    // print the nodes which are not yet visited or visited but not printed
    while(cur1 != NULL || !s1.empty() || cur2 != NULL || !s2.empty())
    {
        // iterative inorder
        if(cur1 != NULL || cur2 != NULL)
        {
            // Reach the leftmost node of both BSTs and push ancestors of
            // leftmost nodes to stack s1 and s2 respectively
            if(cur1 != NULL)
            {
                s1.push(cur1);
                cur1 = cur1->left;
            }
            if (cur2 != NULL)
            {
                s2.push(cur2);
                cur2 = cur2->left;
            }
        }
        else
        {
            // if anyone of the tree's current node becomes Null
            // then we need to check if stack is empty
            if(s1.empty())
            {
                while(!s2.empty())
                {
                    cur2 = s2.top();s2.pop();
                    cur2->left = NULL;
                    inorder(cur2);
                }
                return;
            }
            if(s2.empty())
            {
                while(!s1.empty())
                {
                    cur1 = s1.top();s1.pop();
                    cur1->left = NULL;
                    inorder(cur1);
                }
                return;
            }

            // compare elements at the top of both stacks
            cur1 = s1.top();s1.pop();
            cur2 = s2.top();s2.pop();

            // print the smaller of the two and push the larger element into the corresponding stack
            if(cur1->data < cur2->data)
            {
                cout<<cur1->data<<" ";
                cur1 = cur1->right;
                s2.push(cur2);
                cur2 = NULL;
            }
            else
            {
                cout<<cur2->data<<" ";
                cur2 = cur2->right;
                s1.push(cur1);
                cur1 = NULL;
            }
        }
    }
}

int main()
{
    node *root1 = NULL, *root2 = NULL;
    //first tree
    root1 = create(5);
    root1->left = create(4);
    root1->right = create(13);

    //second tree
    root2 = create(7);
    root2->left = create(6);
    root2->right = create(9);

    // Print sorted nodes of both trees
    merge(root1, root2);

    return 0;
}
4 5 6 7 9 13

Хязгаарлагдмал нэмэлт зайтай хоёр BST-ийг нэгтгэх Java код

import java.util.*;
import java.lang.*;
import java.io.*;
 
class node{
  int data;
  node left;
  node right;
}
 
class Tree{
  static node root;
  static int count;
  static node create(int data){
    node tmp = new node();
    tmp.data = data;
    tmp.left = null;
    tmp.right = null;
    return tmp;
  }
  
  static void inorder(node root)
  {
      if(root != null){
          inorder(root.left);
          System.out.print(root.data+" ");
          inorder(root.right);
      }
  }
  
  static void merge(node root1, node root2)
  {
      Stack<node> s1 = new Stack<>();node cur1 = root1;
      Stack<node> s2 = new Stack<>();node cur2 = root2;
      //if first tree is empty, print second tree
      if(root1 == null){
          inorder(root2);
          return;
      }
      // if second tree is empty, print first tree
      if(root2 == null){
          inorder(root1);
          return;
      }
      // print the nodes which are not yet visited or visited but not printed
      while(cur1 != null || s1.empty() == false || cur2 != null || s2.empty() == false)
      {
          if(cur1 != null || cur2 != null)
          {
              // Reach the leftmost node of both BSTs and push ancestors of
              // leftmost nodes to stack s1 and s2 respectively
              if(cur1 != null)
              {
                  s1.push(cur1);
                  cur1 = cur1.left;
              }
              if (cur2 != null)
              {
                  s2.push(cur2);
                  cur2 = cur2.left;
              }
          }
          else
          {
              // if anyone of the tree's current node becomes Null
              // then we need to check if stack is empty
              if(s1.empty() == true)
              {
                  while (s2.empty() == false)
                  {
                      cur2 = s2.pop();
                      cur2.left = null;
                      inorder(cur2);
                  }
                  return ;
              }
              if(s2.empty() == true)
              {
                  while (s1.empty() == false)
                  {
                      cur1 = s1.pop();
                      cur1.left = null;
                      inorder(cur1);
                  }
                  return ;
              }
  
              // compare elements at the top of both stacks
              cur1 = s1.pop();
              cur2 = s2.pop();
              
              // print the smaller of the two and push the larger element into the corresponding stack
              if (cur1.data < cur2.data)
              {
                  System.out.print(cur1.data+" ");
                  cur1 = cur1.right;
                  s2.push(cur2);
                  cur2 = null;
              }
              else
              {
                  System.out.print(cur2.data+" ");
                  cur2 = cur2.right;
                  s1.push(cur1);
                  cur1 = null;
              }
          }
      }
  }
  
  public static void main(String[] args)
  {
      node root1 = null;
      node root2 = null;
      //first tree
      root1 = create(5);
      root1.left = create(4);
      root1.right = create(13);
  
      //second tree
      root2 = create(7);
      root2.left = create(6);
      root2.right = create(9);
  
      // Print sorted nodes of both trees
      merge(root1, root2);
  }

}
4 5 6 7 9 13

Нарийн төвөгтэй байдлын шинжилгээ

Цаг хугацааны нарийн төвөгтэй байдал

O (N + M), Учир нь бид хоёр модон дээгүүр нэгэн зэрэг хөндлөн огтлолцол хийсэн. Шилжилтийн үеэр бид хоёр модны зангилаа дээгүүр өнгөрч, ингэснээр цаг хугацааны шугаман нарийн төвөгтэй байдал үүссэн.

Сансрын нарийн төвөгтэй байдал

O (N + M), илүү албан ёсоор орон зайн нарийн төвөгтэй байдал нь хоёр модны өндрийн нийлбэр байх болно. Гэхдээ хамгийн муу тохиолдолд оролтыг налуу хэлбэртэй болгож болох бөгөөд энэ тохиолдолд өндөр нь модны зангилааны тоотой тэнцүү байх болно.