균형 잡힌 BST로 정렬 된 배열

난이도 쉽게
자주 묻는 질문 어도비 벽돌 아마존 Apple 블룸버그 게시물에서 구글 Microsoft VM웨어
배열 이진 검색 트리 이진 트리 깊이 우선 검색 나무조회수 86

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

균형 잡힌 BST 문제에 대한 정렬 된 배열에서 우리는 정렬 정렬 된 순서로 균형 이진 검색 구성 나무 정렬 된 배열에서.

입력
arr [] = {1, 2, 3, 4, 5}
산출

균형 잡힌 BST로 정렬 된 배열

선주문 : 3 2 1 5 4

입력
arr [] = {7, 11, 13, 20, 22, 41}
산출

균형 잡힌 BST로 정렬 된 배열

선주문 : 20 11 7 13

암호알고리즘

또한 순회 순회 이진 검색 트리의 결과는 정렬 된 데이터가됩니다. 여기에 정렬 된 배열이 주어지고이를 Balanced Binary Search Tree로 변환해야합니다.
배열의 중간 요소가 균형 이진 검색 트리의 루트를 형성하고 배열의 왼쪽에있는 요소가 균형 BST의 왼쪽 하위 트리를 형성하고 중간 요소의 오른쪽에있는 요소를 형성 함을 알 수 있습니다. 균형 잡힌 BST의 오른쪽 하위 트리를 형성합니다. 이 절차를 왼쪽 및 오른쪽 하위 트리에서 반복적으로 반복하면 균형 잡힌 이진 검색 트리가 생성됩니다.

Sorted의 경우와 마찬가지로 연결된 목록 Balanced BST의 경우 연결 목록에서 중간 요소를 찾는 데 O (n) 시간 복잡성이 필요하지만 배열의 경우 배열의 임의 액세스 속성으로 인해 복잡성이 O (1)로 줄어 듭니다. . 따라서 연결된 목록의 경우 순진한 접근 방식이 배열의 경우 최적의 접근 방식이됩니다.

  1. 배열의 중간 요소를 찾고 인덱스를 mid가되도록합니다.
  2. 인덱스 중간에있는 요소는 균형 잡힌 BST의 루트를 형성합니다.
  3. 중간의 왼쪽에있는 요소는 왼쪽 하위 트리를 형성하므로 왼쪽 하위 트리에 대해이 함수를 재귀 적으로 호출합니다.
  4. 중간의 오른쪽에있는 요소는 오른쪽 하위 트리를 형성하므로 오른쪽 하위 트리에 대해서도이 함수를 재귀 적으로 호출합니다.
  5. 루트를 반환합니다.

시간 복잡성 = O (N)
공간 복잡성 = O (N), 재귀로 인해
여기서 n은 주어진 배열의 크기입니다.

정렬 된 배열을 균형 BST로 변환하기위한 JAVA 코드

public class SortedArrayToBalancedBST {
    // 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 the preorder 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);
        }
    }

    private static Node convertSortedArrayToBalancedBST(int[] arr, int start, int end) {
        // Base Case
        if (start > end) {
            return null;
        }

        // find the middle element of the array
        int mid = (start + end) / 2;

        // the middle element forms the root of the balanced BST
        Node root = new Node(arr[mid]);

        // elements to the left of mid forms the left subtree
        root.left = convertSortedArrayToBalancedBST(arr, start, mid - 1);
        // elements to the right of mid forms the right subtree
        root.right = convertSortedArrayToBalancedBST(arr, mid + 1, end);

        // return root
        return root;
    }

    public static void main(String[] args) {
        // Example 1
        int arr1[] = new int[] {1, 2, 3, 4, 5};
        Node root1 = convertSortedArrayToBalancedBST(arr1, 0, arr1.length - 1);
        preorder(root1);
        System.out.println();

        // Example 2
        int arr2[] = new int[] {7, 11, 13, 20, 22, 41};
        Node root2 = convertSortedArrayToBalancedBST(arr2, 0,arr2.length - 1);
        preorder(root2);
        System.out.println();
    }
}
3 1 2 4 5 
13 7 11 22 20 41

정렬 된 배열을 균형 BST로 변환하기위한 C ++ 코드

#include <iostream>
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 the preorder traversal of a binary tree
void preOrder(Node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preOrder(root->left);
        preOrder(root->right);
    }
}

Node* convertSortedArrayToBalancedBST(int *arr, int start, int end) {
    // Base Case
    if (start > end) {
        return NULL;
    }
    
    // find the middle element of the array
    int mid = (start + end) / 2;
    
    // the middle element forms the root of the balanced BST
    Node *root = new Node(arr[mid]);
    
    // elements to the left of mid forms the left subtree
    root->left = convertSortedArrayToBalancedBST(arr, start, mid - 1);
    // elements to the right of mid forms the right subtree
    root->right = convertSortedArrayToBalancedBST(arr, mid + 1, end);

    // return root
    return root;
}

int main() {
    // Example 1
    int arr1[] = {1, 2, 3, 4, 5};
    Node *root1 = convertSortedArrayToBalancedBST(arr1, 0, sizeof(arr1) / sizeof(arr1[0]) - 1);
    preOrder(root1);
    cout<<endl;

    // Example 2
    int arr2[] = {7, 11, 13, 20, 22, 41};
    Node *root2 = convertSortedArrayToBalancedBST(arr2, 0, sizeof(arr2) / sizeof(arr2[0]) - 1);
    preOrder(root2);
    cout<<endl;
    
    return 0;
}
3 1 2 4 5 
13 7 11 22 20 41

참조

균열 시스템 설계 인터뷰
Translate »