Mündəricat
Problem bəyanat
Problem "İki BST-ni məhdud əlavə yerlə birləşdirin" sizə iki verildiyini bildirir ikili axtarış ağacı(BST) və hər iki ağacdan elementləri sıralanmış qaydada çap etməlisiniz. Elə bir sırada ki, elementlərin tək bir BST-dən olduğu görünür.
misal
Input
Buraxılış
4 5 6 7 9 13
İzahat: Hər iki giriş ağacının birləşməsi nəticəsində əmələ gələn yeni ağac şəkildə göstərilir. Nəticə yaradan ağacın kənar keçidi nəticə verir.
Məhdud əlavə yerlə iki BST-ni birləşdirməyə yanaşma
Problem "İki BST-ni məhdud əlavə boşluqla birləşdirin" bizdən birləşdirilmiş ağacın kənar sərhədlərini çap etməyimizi tələb edir. Birləşdirilmiş ağac verilmiş iki ağacın birləşməsi ilə əmələ gələcəkdir. Beləliklə verilmiş ağacları birləşdirməyə çalışacağıq. Ancaq ağacları birləşdirəcəyiksə, bu, çox xərc tələb edir. Doğrudan birləşmək əvəzinə başqa bir yol düşünə bilərik. Yalnız hər iki ağacdakı qovşaqların dəyərlərini sıralanmış şəkildə çap etməyimiz lazım olduğundan.
Bunu həll etmək üçün ikili axtarış ağacının təkrarlanan inorder traversalını eyni vaxtda hər iki ağacın üzərində işləməyə çalışacağıq. Əgər qaçsaq bu edilə bilər sərhəd keçidi. Və sərhəd keçidindəki hər iki qovşaqdakı dəyəri müqayisə edin. Daha sonra ikisinin daha kiçikini çap edəcəyik və yığındakı daha böyük düyünü itələyəcəyik (iterativ inorder traversal zamanı istifadə olunan yığın). Ağaclardan hər hansı biri ilə işimiz bitdiyində, qovşaqları qalan ağacın üstündən keçid keçidini keçərik.
Kodu
Məhdud əlavə yerlə iki BST-ni birləşdirmək üçün C ++ kodu
#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
Məhdud əlavə yerlə iki BST-ni birləşdirmək üçün Java kodu
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
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (N + M), çünki hər iki ağac üzərində eyni vaxtda sərhəd keçidi etdik. Inorder traversal zamanı hər iki ağacdan qovşaqların üstündən keçdik və beləliklə xətti bir zaman mürəkkəbliyi keçdik.
Kosmik Mürəkkəblik
O (N + M), daha formal olaraq kosmik mürəkkəblik hər iki ağacın hündürlüyünün cəmi olacaqdır. Ancaq ən pis vəziyyətdə, giriş əyri ağaclar ola bilər və bu vəziyyətdə hündürlük ağaclardakı düyün sayına bərabər olacaqdır.
