Balanslaşdırılmış BST-yə sıralanmış massiv

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Balanslaşdırılmış BST probleminə görə sıralanmış massivdə bir array sıralanmış qaydada, Balanslı İkili Axtarış qurun Ağac sıralanmış massivdən.

Nümunələr

Input
arr [] = {1, 2, 3, 4, 5}
Buraxılış

Pin

Əvvəlcədən sifariş: 3 2 1 5 4

Input
arr [] = {7, 11, 13, 20, 22, 41}
Buraxılış

Pin

Ön sifariş: 20 11 7 13 41 22

Alqoritm

The nizamlı xain ikili axtarış ağacının sıralanmış məlumatları ilə nəticələnir. Burada bizə sıralanmış bir sıra verilir və onu Balanslı İkili Axtarış Ağacına çevirməliyik.
Göründüyü kimi, serialın orta elementi balanslaşdırılmış ikili axtarış ağacının kökünü təşkil edir və massivin solundakı elementlər balanslaşdırılmış BST-nin sol alt ağacını və orta elementin sağ tərəfindəki elementləri təşkil edir. balanslaşdırılmış BST-nin sağ alt ağacını təşkil edir. Bu proseduru sol və sağ alt ağac üzərində təkrarən təkrarlamaq balanslı İkili Axtarış Ağacı ilə nəticələnəcəkdir.

Sortlaşdırıldığı işdə olduğu kimi Bağlı siyahı Balanced BST vəziyyətinə, əlaqəli siyahıda orta elementi tapmaq üçün bir O (n) zaman mürəkkəbliyi tələb etdiyini gördük, lakin sıra halında bu mürəkkəblik massivin təsadüfi giriş xüsusiyyəti sayəsində O (1) -ə enir. . Beləliklə, əlaqəli siyahıdakı sadəlövh yanaşma bir sıra halında optimal yanaşma halına gəlir.

1. Massivin orta elementini tapın, indeksinin ortası olsun.
2. İndeks ortasındakı element balanslaşdırılmış BST-nin kökünü təşkil edir.
3. Ortanın solundakı elementlər sol alt ağacı əmələ gətirir, buna görə bu funksiyanı sol alt ağac üçün rekursiv olaraq çağırırıq.
4. Ortanın sağındakı elementlər sağ alt ağacı əmələ gətirir, buna görə də sağ alt ağac üçün bu funksiyanı öz-özünə çağırırıq.
5. Kökə qayıdın.

Zaman Mürəkkəbliyi = O (n)
Kosmik Mürəkkəblik = O (n), rekursiyaya görə
burada n müəyyən bir sıra ölçüsüdür.

Sıralanmış massivi Balanslaşdırılmış BST-yə çevirmək üçün JAVA kodu

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

Sıralanmış massivi Balanslaşdırılmış BST-yə çevirmək üçün C ++ kodu

#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

References