Спојте две избалансирани стебла на бинарно пребарување


Ниво на тешкотија Тешко
Често прашувано во Амазон ГЕ здравство Google Мајкрософт Salesforce Spotify
Дрво за бинарно пребарување Бинарно дрво Дрво

Изјава за проблем

Со оглед на две балансирани стебла на бинарно пребарување, има n елементи во првиот BST и m елементи во вториот BST. Напишете алгоритам за да споите две избалансирани стебла на бинарно пребарување за да формирате трето избалансирано Дрво за бинарно пребарување со (n + m) елементи.

пример

Внесете

Спојте две избалансирани стебла на бинарно пребарувањеСпојте две избалансирани стебла на бинарно пребарување

излез

Спојте две избалансирани стебла на бинарно пребарување

Пред-нарачка: 5 2 1 3 4 7 6 8 9

Алгоритам за спојување на две стебла за бинарно пребарување

Отпрвин, се чини дека вметнувањето на сите елементи од дрво2 на дрво1 еден по еден е најдобро решение. Но, ова решение има временска сложеност на O (n дневник (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) време. Така, тотално можеме да кажеме дека решението има линеарна временска комплексност.

Комплексноста на просторот = НА) 

Тука за овој проблем, ние имаме линеарна вселенска комплексност. Бидејќи сме зачувале три низи со една големина 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 ++ код за спојување на две 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