បំលែងអារេតម្រង់ទៅជាដំណោះស្រាយគោលពីរនៃដើមឡេធីកូដ


កម្រិតលំបាក មានភាពងាយស្រួល
សួរញឹកញាប់ កម្មវិធី Adob ​​e Airbnb ក្រុមហ៊ុន Amazon ផ្លែប៉ោម ទីភ្នាក់ងារ Bloomberg ស៊ីស្កូ ក្រុមហ៊ុន google ក្រុមហ៊ុន Microsoft ក្រុមហ៊ុន Oracle តាម Online VMware ក្រុមហ៊ុន Yahoo
មែកធាងស្វែងរកគោលពីរ ជម្រៅស្វែងរកដំបូង

ពិចារណាយើងត្រូវបានគេផ្តល់ឱ្យតម្រៀបមួយ អារេ នៃចំនួនគត់។ គោលដៅគឺដើម្បីបង្កើតមែកធាងស្វែងរកគោលពីរពីអារេនេះដែលដើមឈើមានតុល្យភាពកម្ពស់។ សូមកត់សម្គាល់ថាដើមឈើមួយត្រូវបានគេនិយាយថាមានកំពស់ខ្ពស់ប្រសិនបើកម្ពស់ខុសគ្នានៃអនុក្រឹតខាងឆ្វេងនិងស្តាំនៃថ្នាំងណាមួយនៅក្នុងមែកធាងគឺមានច្រើនបំផុត ១ ។

វាងាយស្រួលក្នុងការរកឃើញថាវាអាចមានដំណោះស្រាយច្រើន។ យើងត្រូវរកដំណោះស្រាយត្រឹមត្រូវ។ ចំណាំថានៅក្នុងបញ្ហានេះយើងមិនចាំបាច់បោះពុម្ពដើមឈើទេប៉ុន្តែដើម្បីបង្កើតវា។ យើងគ្រាន់តែត្រូវការបោះពុម្ពការផ្លាស់ប្តូរជាមុន។

ឧទាហរណ៍

Array = {-4 , 0 , 1 , 2 , 7}
1 -4 0 2 7

ការពន្យល់៖ BST គឺ៖

បំលែងអារេតម្រង់ទៅជាដំណោះស្រាយគោលពីរនៃដើមឡេធីកូដ

 

Array = {1 , 2 , 3}
2 1 3

ការពន្យល់៖ BST គឺ៖

បំលែងអារេតម្រង់ទៅជាដំណោះស្រាយគោលពីរនៃដើមឡេធីកូដ

វិធីសាស្រ្ត (ការហៅខ្លួនឯង)

យើងត្រូវតាមដានរឿងពីរ៖

  1. ថ្នាំងណាមួយគួរតែមានធាតុតូចៗដូចជាកូនខាងឆ្វេងនិងច្រាសមកវិញសម្រាប់កុមារស្តាំ
  2. BST គួរតែមានកំពស់ខ្ពស់

ដើម្បីរក្សាដើមឈើឱ្យមានលំនឹងនៅពេលណាមួយយើងត្រូវជ្រើសរើសធាតុកណ្តាលនៃអារេជាឫស។ តាមវិធីនេះយើងនឹងមានកំពស់ខុសគ្នា 1 រវាងអក្សរតូចឆ្វេងនិងស្តាំប្រសិនបើអារេមានទំហំប៉ុននិងកំពស់ខុសគ្នា នៅពេលអារេគឺជាហាងឆេង។

ឥឡូវនេះនៅពេលយើងជ្រើសរើសថ្នាំងកណ្តាលណាមួយជាឫសយើងត្រូវបង្កើតអនុក្រិតខាងឆ្វេងពីអនុក្រោមនិងខាងឆ្វេងក្រោមពីស្តាំក្រោមបាតសមុទ្រខាងស្តាំ។ នេះគឺជាបញ្ហារងនៃបញ្ហាដើមរបស់យើងហេតុដូចនេះហើយយើងអាចដោះស្រាយវាឡើងវិញ។ បន្ទាប់ពីការប្រគល់អនុក្រឹត្យខាងឆ្វេងនិងស្តាំទៅថ្នាំងពាក់កណ្តាលយើងអាចប្រគល់វាមកវិញហើយបោះពុម្ភផ្ទាំងរូបភាពនៃដើមនៃការស្វែងរកគោលពីរ។

ក្បួនដោះស្រាយ

  1. បង្កើតមុខងារមួយទៀត converArrayToBST () ដែលនឹងបំលែងជួរជាក់លាក់ណាមួយនៃអារេដែលបានផ្តល់ហើយត្រឡប់ថ្នាំងជា root BST ដែលត្រូវគ្នា។
  2. សូមឱ្យ L = ដែនកំណត់ខាងឆ្វេងនៃអារេនិង R = ចំនួនកំណត់ខាងស្តាំនៃអារេនៅក្នុងជួរដែលបានរៀបរាប់ខាងលើ។
    1. បើ L> R
      • ត្រឡប់មកវិញ NULLដូចដែលយើងទទួលបានជួរខុស
    2. បើ L == R
      • ត្រឡប់ថ្នាំងថ្មីដែលមានតម្លៃដូចគ្នា អារេ [អិល] 
    3. រកថ្នាំងពាក់កណ្តាលនៃជួរនេះ ពាក់កណ្តាល = (អិល + (អរ - អិល) / ២)
      • ក្បាលដំបូងជាថ្នាំងប៊ីអេសអេសថ្មីដែលមានតម្លៃដូចគ្នា អារេ [ពាក់កណ្តាល]
      • ផ្ដល់ ចាកចេញ និង នៅខាងស្ដាំ អនុមុខងារដូចគ្នានឹងអនុគមន៍នៅខាងឆ្វេងនិងខាងស្តាំរៀងគ្នា
      • ត្រឡប់ក្បាល
  3. បោះពុម្ពការប្តូរជាមុននៃមែកធាងស្វែងរកគោលពីរ

ការអនុវត្តការបំប្លែងអារេទៅជាដំណោះស្រាយប្រព័ន្ធគោលពីរនៃការស្វែងរកមែកធាងឡេស

C ++ ដំណោះស្រាយដើម្បីបំលែងអារេទៅជាមែកធាងស្វែងរកគោលពីរ

#include <bits/stdc++.h>
using namespace std;

struct BSTNode
{
    int value;
    BSTNode *left , *right;
    BSTNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};

BSTNode* convertArrayToBST(vector <int> &a , int l , int r)
{
    if(l > r)
        return NULL;
    if(l == r)
        return new BSTNode(a[l]);
    int mid = (l + (r - l) / 2);
    BSTNode* head = new BSTNode(a[mid]);
    head->left = convertArrayToBST(a , l , mid - 1);
    head->right = convertArrayToBST(a , mid + 1 , r);
    return head;
}

BSTNode* sortedArrayToBST(vector<int>& a)
{
    int n = a.size();
    return convertArrayToBST(a , 0 , n - 1);
}

void preorder(BSTNode* head)
{
    if(!head)
        return;
    cout << head->value << " ";
    preorder(head->left);
    preorder(head->right);
}


int main()
{
    vector <int> a = {-4 , 0 , 1 , 2 , 7};
    BSTNode* head = sortedArrayToBST(a);
    preorder(head);
    return 0;
}

ជ្វាដំណោះស្រាយដើម្បីបំលែងអារេទៅជាមែកធាងស្វែងរកគោលពីរ

class BSTNode
{
    int value;
    BSTNode left , right;
    BSTNode(int x)
    {
        value = x;
        left = null;
        right = null;
    }
}

class convert_array_to_BST
{
    public static void main(String args[])
    {
        int[] a = {-4 , 0 , 1 , 2 , 7};
        BSTNode head = sortedArrayToBST(a);
        preorder(head);
    }

    static BSTNode convertArrayToBST(int[] a , int l , int r)
    {
        if(l > r)
            return null;
        if(l == r)
            return new BSTNode(a[l]);
        int mid = (l + (r - l) / 2);
        BSTNode head = new BSTNode(a[mid]);
        head.left = convertArrayToBST(a , l , mid - 1);
        head.right = convertArrayToBST(a , mid + 1 , r);
        return head;
    }

    static BSTNode sortedArrayToBST(int[] a)
    {
        return convertArrayToBST(a , 0 , a.length - 1);
    }

    static void preorder(BSTNode head)
    {
        if(head == null)
            return;
        System.out.print(head.value + " ");
        preorder(head.left);
        preorder(head.right);
    }
}
1 -4 0 2 7

ការវិភាគភាពស្មុគស្មាញនៃការបំលែងអារេទៅជាដំណោះស្រាយគោលពីរនៃការស្វែងរកមែកធាងឡេតូលេខកូដ

ស្មុគស្មាញពេលវេលា

O (N), N = ចំនួនធាតុនៅក្នុងមែកធាង។ យើងទស្សនាគ្រប់ធាតុទាំងអស់ដើម្បីសាងសង់ប៊ីអេសអេសនិងបោះពុម្ពការផ្លាស់ប្តូរជាមុន។

ភាពស្មុគស្មាញនៃលំហ

O (H), ដែលក្រុមហ៊ុន H = កំពស់ដើមឈើ = logN ។ ទាំងមុខងារដែលយើងហៅឡើងវិញយើងធ្វើឱ្យប្រាកដថាដើមឈើមានកំពស់ខ្ពស់ដូច្នេះយើងប្រើអតិបរមា O (H) ចន្លោះសម្រាប់ស៊ុមជណ្តើរយន្តហៅខ្លួនឯង។