آرایه به BST متعادل مرتب شده است


سطح دشواری ساده
اغلب در خشت آمازون سیب بلومبرگ گوگل مایکروسافت آموزش 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

الگوریتم

La پیمایش به ترتیب از یک درخت جستجوی دودویی در داده های مرتب شده نتیجه می گیرد. در اینجا یک آرایه مرتب شده به ما داده می شود و باید آن را به یک درخت جستجوی دودویی متعادل تبدیل کنیم.
دیده می شود که عنصر میانی آرایه ریشه یک درخت جستجوی دودویی متعادل را تشکیل می دهد و عناصر سمت چپ آرایه زیر درخت چپ BST متعادل و عناصر سمت راست عنصر میانی را تشکیل می دهند. زیرشاخه مناسب BST متعادل را تشکیل می دهد. تکرار متناوب این روش در زیر درخت چپ و راست منجر به ایجاد یک درخت جستجوی دودویی متعادل می شود.

مانند مورد مرتب شده لیست پیوند داده شده به حالت Balanced BST ، مشاهده کرده ایم که یافتن عنصر میانی در لیست پیوندی به پیچیدگی O (n) زمان نیاز دارد ، اما در صورت آرایه به دلیل ویژگی دسترسی تصادفی آرایه ، این پیچیدگی به O (1) کاهش می یابد . از این رو رویکرد ساده لوحانه در صورت لیست پیوندی ، در صورت وجود آرایه به رویکرد بهینه تبدیل می شود.

  1. عنصر میانی آرایه را پیدا کنید ، اجازه دهید شاخص آن میانه باشد.
  2. عنصر در فهرست میانی ریشه BST متعادل است.
  3. عناصر سمت چپ وسط زیر درخت چپ را تشکیل می دهند ، بنابراین به صورت بازگشتی این تابع را برای زیر درخت سمت چپ فراخوانی می کنید.
  4. عناصر سمت راست وسط زیر درخت راست را تشکیل می دهند ، بنابراین به طور بازگشتی این تابع را برای زیر درخت راست نیز فراخوانی می کنید.
  5. ریشه را برگردانید.

پیچیدگی زمان = O (N)
پیچیدگی فضا = O (N)، به دلیل بازگشت
که 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

منابع