Συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο


Επίπεδο δυσκολίας Σκληρά
Συχνές ερωτήσεις αμαζόνα Google Microsoft PayU Uber
Δυαδικό δέντρο αναζήτησης Δυαδικό δέντρο Δέντρο

Δήλωση προβλήματος

Το πρόβλημα "Συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο" δηλώνει ότι σας δίνονται δύο δυαδικό δέντρο αναζήτησης(BST) και πρέπει να εκτυπώσετε τα στοιχεία και από τα δύο δέντρα σε ταξινομημένη σειρά. Αυτό είναι με τέτοια σειρά που φαίνεται ότι τα στοιχεία προέρχονται από ένα μόνο BST.

Παράδειγμα

Εισαγωγή

Συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο

Παραγωγή

Συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο

4 5 6 7 9 13

Επεξήγηση: Το νέο δέντρο που σχηματίζεται με τη συγχώνευση και των δύο δέντρων εισόδου εμφανίζεται στην εικόνα. Η εγκάρσια διασταύρωση του προκύπτοντος δέντρου δίνει την έξοδο.

Προσέγγιση συγχώνευσης δύο BST με περιορισμένο επιπλέον χώρο

Το πρόβλημα "Συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο" μας ζητά να εκτυπώσουμε την εγκάρσια διασταύρωση του συγχωνευμένου δέντρου. Το συγχωνευμένο δέντρο θα σχηματιστεί με τη συγχώνευση των δύο δέντρων. Έτσι θα προσπαθήσουμε να συγχωνεύσουμε τα δέντρα. Αλλά αν θέλαμε να συγχωνεύσουμε τα δέντρα τότε αυτό απαιτεί πολύ γενικά έξοδα. Αντί να συγχωνευτούμε άμεσα, μπορούμε να σκεφτούμε κάποιον άλλο τρόπο. Εφόσον χρειάζεται μόνο να εκτυπώσουμε τις τιμές των κόμβων και στα δύο δέντρα σε ταξινομημένη μορφή.

Για την επίλυση αυτού, θα προσπαθήσουμε να εκτελέσουμε επαναλαμβανόμενη διαδοχική διασταύρωση του δέντρου δυαδικής αναζήτησης και στα δύο δέντρα ταυτόχρονα. Αυτό μπορεί να γίνει αν τρέξουμε εγκάρσια διέλευση. Και συγκρίνετε την τιμή και στους δύο κόμβους στην εγκάρσια διέλευση. Στη συνέχεια, θα εκτυπώσουμε το μικρότερο από τα δύο και θα πιέσουμε τον μεγαλύτερο κόμβο στη στοίβα (στοίβα που χρησιμοποιείται κατά τη διάρκεια της επαναλαμβανόμενης διάταξης διατομής). Όποτε τελειώσουμε με οποιοδήποτε από τα δέντρα, θα τρέξουμε απλώς ενδιάμεση διασταύρωση πάνω από το δέντρο με τους κόμβους που απομένουν.

Κώδικας

Κωδικός C ++ για συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο

#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

Κωδικός Java για συγχώνευση δύο BST με περιορισμένο επιπλέον χώρο

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), πιο επίσημα η πολυπλοκότητα του χώρου θα είναι το άθροισμα του ύψους και των δύο δέντρων. Αλλά στη χειρότερη περίπτωση, η είσοδος μπορεί να είναι λοξή δέντρα και στην περίπτωση αυτή, το ύψος θα είναι ίσο με τον αριθμό κόμβων στα δέντρα.