Сартаваны масіў па збалансаваным BST


Узровень складанасці Лёгка
Часта пытаюцца ў Саман амазонка яблык 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

Алгарытм

,en абход у парадку двайковага дрэва пошуку прыводзіць да сартавання дадзеных. Тут мы атрымліваем адсартаваны масіў, і мы павінны пераўтварыць яго ў збалансаванае двайковае дрэва пошуку.
Відаць, што сярэдні элемент масіва ўтварае корань збалансаванага дрэва двайковага пошуку, а элементы злева ад масіва ўтвараюць левае паддрэва збалансаванага BST і элементы справа ад сярэдняга элемента утварае правае паддрэва збалансаванага BST. Рэкурсіўнае паўтарэнне гэтай працэдуры над левым і правым пад-дрэвам прывядзе да збалансаванага двайковага дрэва пошуку.

Як і ў выпадку сартаванага Звязаны спіс у выпадку "Збалансаваны 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

Спасылкі