İki balanslaşdırılmış ikili axtarış ağaclarını birləşdirin

Çətinlik səviyyəsi Ağır
Tez-tez soruşulur Amazon GE Healthcare google microsoft Salesforce Spotify
İkili Axtarış Ağacı İkili ağac AğacBaxılıb 86

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

İki Balanslaşdırılmış İkili Axtarış Ağacını nəzərə alsaq, birinci BST-də n element, ikinci BST-də m element var. İki balanslaşdırılmış ikili axtarış ağacını birləşdirərək üçüncü tarazlı yaratmaq üçün bir alqoritm yazın İkili Axtarış Ağacı (n + m) elementləri ilə.

misal

Input

İki balanslaşdırılmış ikili axtarış ağaclarını birləşdirinPinİki balanslaşdırılmış ikili axtarış ağaclarını birləşdirinPin

Buraxılış

İki balanslaşdırılmış ikili axtarış ağaclarını birləşdirinPin

Öncədən sifariş: 5 2 1 3 4 7 6 8 9

İki ikili axtarış ağacını birləşdirmək üçün alqoritm

Əvvəlcə, bütün elementləri tree2-dən tree1-ə bir-bir əlavə etmək ən yaxşı həll kimi görünür. Ancaq bu həll zaman karmaşıklığına sahibdir O (n log (n)), bundan daha yaxşısını edə biləcək bir həll var.
İndi sıralanmış bir massivi balanslı ikili ağaca necə çevirəcəyimizi bilirik, verilən problemi həmin problemə endirəcəyik.

Fikir hər iki ağacın qeyri-qanuni keçişini iki sıra, məsələn, arr1 və arr2-də saxlamaqdır. İndi arr1 və arr2-nin bütün elementlərini birləşdirilmiş şəkildə birləşdirilmiş daha bir sıra düzəldirik. İki sıralanmış massiv birləşdirilərək xətti zaman mürəkkəbliyində yeni bir sıralanmış bir sıra meydana gətirir. Daha sonra sıralanmış massivi balanslaşdırılmış ikili axtarış ağacına çeviririk, bu səbəbdən iki ağac birləşdirilir.

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.

 

Zamanın mürəkkəbliyi = O (n + m)

Birinci və ikinci massivin sıralama keçişini tapdığımız üçün bu sayılır O (n + m). Sonra bu iki sıralanmış massivin birləşdirilməsi yenidən O (n + m) zaman mürəkkəbliyi sayılır. Və yeni balanslaşdırılmış ikili axtarış ağacının yaradılması da O (n + m) vaxt aparır. Beləliklə, həllin xətti zaman mürəkkəbliyinə malik olduğunu tamamilə deyə bilərik.

Kosmik Mürəkkəblik = O (N) 

Bu problem üçün, biz bir xətti kosmik mürəkkəbliyə sahibik. Üç ölçülü bir massiv saxladığımız üçün n, ölçüdə ikinci m, və bu sıralanmış massivlərin birləşməsindən sonra. Yenə də ölçülü bir sıra var n + m. Bundan sonra son ağacı düzəltdiyimiz zaman yalnız bizlə məşğul oluruq n + m qovşaqlar. Beləliklə, biz xətti bir kosmik mürəkkəbliyə sahibik = O (N).

n -> ağacdakı qovşaq sayı1
m -> ağacdakı qovşaq sayı2

Kodu

İki BST-ni birləşdirmək üçün JAVA Kodu

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

İki BST-ni birləşdirmək üçün C ++ kodu

#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
Crack Sistemi Dizayn Müsahibələri
Translate »