두 개의 균형 잡힌 이진 검색 트리 병합

난이도 하드
자주 묻는 질문 아마존 GE 헬스 케어 구글 Microsoft 세일즈 포스 스포티 파이
이진 검색 트리 이진 트리 나무조회수 86

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

문제 정책

두 개의 균형 이진 검색 트리가 주어지면 첫 번째 BST에 n 개의 요소가 있고 두 번째 BST에 m 개의 요소가 있습니다. 두 개의 균형 이진 검색 트리를 병합하여 세 번째 균형을 형성하는 알고리즘을 작성하십시오. 이진 검색 트리 (n + m) 요소로.

입력

두 개의 균형 잡힌 이진 검색 트리 병합두 개의 균형 잡힌 이진 검색 트리 병합

산출

두 개의 균형 잡힌 이진 검색 트리 병합

선주문 : 5 2 1 3 4 7 6 8 9

두 개의 이진 검색 트리를 병합하는 알고리즘

처음에는 tree2에서 tree1까지 모든 요소를 ​​하나씩 삽입하는 것이 최상의 솔루션 인 것처럼 보입니다. 그러나이 솔루션에는 다음과 같은 시간 복잡성이 있습니다. O (n 로그 (n)), 이것보다 더 잘할 수있는 솔루션이 있습니다.
이제 정렬 된 배열을 균형 잡힌 이진 트리로 변환하는 방법을 알았으므로 주어진 문제를 해당 문제로 줄일 것입니다.

아이디어는 두 트리의 inorder traversal을 각각 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-> tree1의 노드 수
m-> tree2의 노드 수

암호

두 개의 BST를 병합하는 JAVA 코드

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

두 BST를 병합하는 C ++ 코드

#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
균열 시스템 설계 인터뷰
Translate »