Ду дарахти ҷустуҷӯи дутарафаи мутавозинро муттаҳид кунед


Сатҳи душворӣ мушкил
Аксар вақт пурсида мешавад Amazon GE Тандурустӣ Google Microsoft Salesforce Spotify
Дарахти ҷустуҷӯи бинарӣ Дарахти дуӣ Дарахт

Изҳороти мушкилот

Бо назардошти ду дарахти мутавозини ҷустуҷӯи дуӣ, дар BST аввал n элемент ва дар BST дуюм m элемент мавҷуданд. Алгоритми нависед, ки ду дарахти ҷустуҷӯи бинарии мутавозинро муттаҳид карда, мувозинати сеюмро ба вуҷуд оред Дарахти ҷустуҷӯи бинарӣ бо (n + m) унсурҳо.

мисол

вуруди

Ду дарахти ҷустуҷӯи дутарафаи мутавозинро муттаҳид кунедДу дарахти ҷустуҷӯи дутарафаи мутавозинро муттаҳид кунед

Натиҷаи

Ду дарахти ҷустуҷӯи дутарафаи мутавозинро муттаҳид кунед

Пешакӣ фармоиш: 5 2 1 3 4 7 6 8 9

Алгоритми якҷоя кардани ду дарахти ҷустуҷӯи дуӣ

Дар аввал, чунин ба назар мерасад, ки ҳамаи унсурҳоро аз дарахт2 ба дарахт1 як ба як гузоштан беҳтарин роҳи ҳал аст. Аммо ин ҳалли мушкилоти вақт дорад O (n log (n)), як ҳалли беҳтаре аз ин вуҷуд дорад.
Ҳоло мо медонем, ки чӣ гуна массиви мураттабро ба дарахти дутарафа табдил диҳем, мо масъалаи додашударо ба он масъала коҳиш медиҳем.

Ғоя иборат аз он аст, ки ҳаракати ҳарду дарахтро дар ду массив, масалан, arr1 ва arr2 нигоҳ доред. Ҳоло мо боз як массиви дигар месозем, ки дар он ҳамаи унсурҳои arr1 ва arr2 якҷоя дар шакли мураттаб сохта шудаанд. Ду массиви ҷудошударо якҷоя кардан мумкин аст, то массиви навро дар мураккабии вақти хаттӣ ба вуҷуд орад. Пас массиви ҷудошударо ба дарахти ҷустуҷӯи мувозинаи бинарӣ табдил медиҳем, аз ин рӯ ду дарахт якҷоя карда мешаванд.

1. Store the in-order traversal of both the trees in two arrays, say, arr1 and arr2 respectively.
2. Merge arr1 and arr2 to form another array arr, that contains the elements of arr1 and arr2 in sorted form.
3. We now use this sorted array(arr) to build a balanced binary search tree, which is a merged version of the given trees.
4. The middle element of the array forms the root of the balanced BST and all the elements to the left of the middle element form the left sub-tree and all the elements to the right of the middle element form the right sub-tree.
5. Recursively do step 4 for the left subtree and attach it to the left of root.
6. Recursively do step 4 for the right subtree and attach it to the right of root.
7. Return root.

 

Мураккабии вақт = O (n + m)

Азбаски мо гардиши тартибии массиви якум ва дуюмро пайдо кардем, ин ба ҳисоб меравад O (n + m). Сипас якҷоя кардани ин ду массиви ҷудошуда бори дигар мураккабии вақт (O + n + m) -ро ҳисоб мекунад. Ва сохтани дарахти нави мутавозуни ҷустуҷӯи дуӣ низ вақти O (n + m) -ро мегирад. Ҳамин тариқ, мо комилан гуфта метавонем, ки ҳалли он мураккабии хаттии вақт дорад.

Мураккабии фазо = О (Н) 

Дар ин ҷо барои ин мушкилот, мо як мураккабии фазоии хаттӣ дорем. Азбаски мо се массивро як андоза захира кардем n, сонияи андозаи m, ва пас аз якҷоякунии ин массивҳои ҷудошуда. Боз мо массиви мураттабшуда дорем n + m. Баъд аз ин, вақте ки мо дарахти ниҳоиро месозем, пас мо низ танҳо бо он сару кор дорем n + m гиреҳҳо. Ҳамин тавр, мо як мураккабии фазоии хаттӣ = O (N) дорем.

n -> шумораи гиреҳҳо дар дарахт1
m -> шумораи гиреҳҳо дар дарахт2

рамз

Рамзи JAVA барои якҷоя кардани ду BST

import java.util.ArrayList;

class MergeTwoBalancedBinarySearchTrees {
    // class representing node of a binary tree
    static class Node {
        int data;
        Node left, right;

        public Node(int data) {
            this.data = data;
        }
    }

    // function to print pre-order traversal of a binary tree
    private static void preOrder(Node root) {
        if (root != null) {
            System.out.print(root.data + " ");
            preOrder(root.left);
            preOrder(root.right);
        }
    }

    // function to store in-order traversal of a binary tree in an array-list
    private static void storeInOrder(Node root, ArrayList<Integer> arr) {
        if (root != null) {
            storeInOrder(root.left, arr);
            arr.add(root.data);
            storeInOrder(root.right, arr);
        }
    }

    // function to merge two sorted array-lists
    private static ArrayList<Integer> mergeSortedArrays(ArrayList<Integer> arr1, ArrayList<Integer> arr2) {
        int i = 0, j = 0;
        ArrayList<Integer> arr = new ArrayList<>();

        while (i < arr1.size() && j < arr2.size()) {
            if (arr1.get(i) < arr2.get(j)) {
                arr.add(arr1.get(i));
                i++;
            } else {
                arr.add(arr2.get(j));
                j++;
            }
        }

        while (i < arr1.size()) {
            arr.add(arr1.get(i));
            i++;
        }

        while (j < arr2.size()) {
            arr.add(arr2.get(j));
            j++;
        }

        return arr;
    }

    // function to convert sorted array-list to balanced BST
    private static Node constructBSTFromSortedArray(ArrayList<Integer> arr, int start, int end) {
        // base case
        if (start > end) {
            return null;
        }

        int mid = (start + end) / 2;

        Node root = new Node(arr.get(mid));
        root.left = constructBSTFromSortedArray(arr, start, mid - 1);
        root.right = constructBSTFromSortedArray(arr, mid + 1, end);

        return root;
    }

    private static Node mergeBST(Node root1, Node root2) {
        // store the in-order traversal of tree1 in an array
        ArrayList<Integer> arr1 = new ArrayList<>();
        storeInOrder(root1, arr1);
        // store the in-order traversal of tree2 in an array
        ArrayList<Integer> arr2 = new ArrayList<>();
        storeInOrder(root2, arr2);

        // merge the two sorted arrays
        ArrayList<Integer> arr = mergeSortedArrays(arr1, arr2);

        // construct the balanced BST from this sorted array
        return constructBSTFromSortedArray(arr, 0, arr.size() - 1);
    }

    public static void main(String[] args) {
        // Example
        Node root1 = new Node(7);
        root1.left = new Node(5);
        root1.right = new Node(8);
        root1.left.left = new Node(4);
        root1.left.right = new Node(6);
        root1.right.right = new Node(9);

        Node root2 = new Node(2);
        root2.left = new Node(1);
        root2.right = new Node(3);

        Node root = mergeBST(root1, root2);
        preOrder(root);
        System.out.println();
    }
}
5 2 1 3 4 7 6 8 9

C ++ Code барои якҷоя кардани ду BST

#include <bits/stdc++.h> 
using namespace std; 

// class representing node of a binary tree 
class Node { 
    public: 
    int data; 
    Node *left; 
    Node *right; 
    
    Node(int d) { 
        data = d; 
        left = right = NULL; 
    } 
};

// function to print pre-order traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

// function to store the inorder traversal of tree in a list
void storeInOrder(Node *root, vector<int> &arr) {
    if (root != NULL) {
        storeInOrder(root->left, arr);
        arr.push_back(root->data);
        storeInOrder(root->right, arr);
    }
}

// function to merge two sorted array-lists
vector<int> mergeSortedArrays(vector<int> &arr1, vector<int> &arr2) {
    int i = 0, j = 0;
    vector<int> arr;
    
    while (i < arr1.size() && j < arr2.size()) {
        if (arr1[i] < arr2[j]) {
            arr.push_back(arr1[i]);
            i++;
        } else {
            arr.push_back(arr2[j]);
            j++;
        }
    }
    
    while (i < arr1.size()) {
        arr.push_back(arr1[i]);
        i++;
    }
    
    while (j < arr2.size()) {
        arr.push_back(arr2[j]);
        j++;
    }
    
    return arr;
}

// function to convert sorted array-list to balanced BST
Node* constructBSTFromSortedArray(vector<int> &arr, int start, int end) {
    // base case
    if (start > end) {
        return NULL;
    }
    
    int mid = (start + end) / 2;
    
    Node *root = new Node(arr[mid]);
    root->left = constructBSTFromSortedArray(arr, start, mid - 1);
    root->right = constructBSTFromSortedArray(arr, mid + 1, end);

    return root;
}

Node* mergeBST(Node *root1, Node *root2) {
    // store the in-order traversal of tree1 in an array
    vector<int> arr1;
    storeInOrder(root1, arr1);
    
    // store the in-order traversal of tree2 in an array
    vector<int> arr2;
    storeInOrder(root2, arr2);
    
    // merge the two sorted arrays
    vector<int> arr = mergeSortedArrays(arr1, arr2);
    
    // construct the balanced BST from this sorted array
    return constructBSTFromSortedArray(arr, 0, arr.size() - 1);
}

int main() {
    // Example
    Node *root1 = new Node(7);
    root1->left = new Node(5);
    root1->right = new Node(8);
    root1->left->left = new Node(4);
    root1->left->right = new Node(6);
    root1->right->right = new Node(9);

    Node *root2 = new Node(2);
    root2->left = new Node(1);
    root2->right = new Node(3);

    Node *root = mergeBST(root1, root2);
    preOrder(root);
    cout<<endl;
    
    return 0;
}
5 2 1 3 4 7 6 8 9