Відсортований масив до збалансованого BST


Рівень складності Легко
Часто запитують у саман Амазонка Apple Bloomberg Google Microsoft VMware
масив Бінарне дерево пошуку Бінарне дерево Глибина Перший пошук Дерево

У відсортованому масиві до збалансованої задачі 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 41 22

Алгоритм

повне г, повне г,, показали, від, номер, XNUMX порядок обходу двійкового дерева пошуку призводить до сортування даних. Тут ми отримуємо відсортований масив, і ми маємо перетворити його на Збалансоване двійкове дерево пошуку.
Видно, що середній елемент масиву утворює корінь дерева збалансованого двійкового пошуку, а елементи ліворуч від масиву утворюють ліве піддерево збалансованого BST та елементи праворуч від середнього елемента утворює праве піддерево збалансованого BST. Рекурсивне повторення цієї процедури над лівим і правим піддеревом призведе до збалансованого дерева двійкового пошуку.

Як і у випадку з Sorted Зв’язаний список у випадку збалансованого BST ми бачили, що для знаходження середнього елемента у зв’язаному списку потрібна складність часу O (n), але у випадку масиву ця складність зменшується до O (1) через властивість довільного доступу масиву . Отже, наївний підхід у випадку пов’язаного списку стає оптимальним підходом у випадку масиву.

  1. Знайдіть середній елемент масиву, нехай його індекс буде середнім.
  2. Елемент із середнім показником утворює корінь збалансованої BST.
  3. Елементи зліва від середини утворюють ліве піддерево, тому рекурсивно викликайте цю функцію для лівого піддерева.
  4. Елементи праворуч від середини утворюють праве піддерево, тому рекурсивно викликайте цю функцію і для правого піддерева.
  5. Повернути корінь.

Складність часу = О (п)
Складність простору = О (п), через рекурсію
де n - розмір даного масиву.

Код JAVA для перетворення відсортованого масиву у збалансований BST

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

Код C ++ для перетворення відсортованого масиву у збалансований BST

#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

посилання