അടുക്കിയ അറേയെ ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് പരിവർത്തനം ചെയ്യുക


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു അഡോബി airbnb ആമസോൺ ആപ്പിൾ ബ്ലൂംബർഗ് സിസ്കോ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ് ഒറാക്കിൾ നീനുവിനും വിഎംവെയർ യാഹൂ
ബൈനറി തിരയൽ മരം ആഴത്തിലുള്ള ആദ്യ തിരയൽ

ഞങ്ങൾക്ക് ഒരു അടുക്കിയത് പരിഗണിക്കുക ശ്രേണി പൂർണ്ണസംഖ്യകളുടെ. ഈ ശ്രേണിയിൽ‌ നിന്നും ഒരു ബൈനറി തിരയൽ‌ ട്രീ നിർമ്മിക്കുക എന്നതാണ് ലക്ഷ്യം, അത് മരം ഉയരം-സമതുലിതമാണ്. വൃക്ഷത്തിലെ ഏതെങ്കിലും നോഡിന്റെ ഇടത്, വലത് സബ്‌ട്രീകളുടെ ഉയരം വ്യത്യാസം 1 ആണെങ്കിൽ ഒരു വൃക്ഷം ഉയരം സമതുലിതമാണെന്ന് പറയപ്പെടുന്നു.

ഒന്നിലധികം പരിഹാരങ്ങൾ ഉണ്ടെന്ന് കണ്ടെത്തുന്നത് എളുപ്പമാണ്. സാധുവായ ഏതെങ്കിലും പരിഹാരം ഞങ്ങൾ കണ്ടെത്തേണ്ടതുണ്ട്. ഈ പ്രശ്‌നത്തിൽ‌, ഞങ്ങൾ‌ക്ക് മരം അച്ചടിക്കേണ്ട ആവശ്യമില്ല, മറിച്ച് ഒന്ന് സൃഷ്‌ടിക്കുക എന്നതാണ്. ഞങ്ങൾ അതിന്റെ പ്രീഓർഡർ ട്രാവെർസൽ പ്രിന്റുചെയ്യേണ്ടതുണ്ട്.

ഉദാഹരണം

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

വിശദീകരണം: ജിഎസ്ടി ഇതാണ്:

അടുക്കിയ അറേയെ ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് പരിവർത്തനം ചെയ്യുക

 

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

വിശദീകരണം: ജിഎസ്ടി ഇതാണ്:

അടുക്കിയ അറേയെ ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് പരിവർത്തനം ചെയ്യുക

സമീപനം (റിക്കറിഷൻ)

ഞങ്ങൾ രണ്ട് കാര്യങ്ങളുടെ ട്രാക്ക് സൂക്ഷിക്കേണ്ടതുണ്ട്:

  1. ഏതൊരു നോഡിനും ഇടത് കുട്ടികളായി ചെറിയ ഘടകങ്ങളും വലത് കുട്ടികൾക്ക് തിരിച്ചും ഉണ്ടായിരിക്കണം
  2. ജിഎസ്ടി ഉയരം തുലനം ചെയ്യണം

ഏത് നിമിഷവും മരം സമതുലിതമായി നിലനിർത്തുന്നതിന്, ഞങ്ങൾ അറേയുടെ മധ്യഭാഗം റൂട്ടായി തിരഞ്ഞെടുക്കണം. ഈ രീതിയിൽ, നമുക്ക് ഉയരം വ്യത്യാസമുണ്ടാകും 1 അറേ ഇരട്ട വലുപ്പവും ഉയരത്തിന്റെ വ്യത്യാസവും ആണെങ്കിൽ ഇടത്, വലത് സബ്‌ട്രീകൾക്കിടയിൽ അറേ ഒരു വിചിത്രമാകുമ്പോൾ.

ഇപ്പോൾ, ഏതെങ്കിലും മിഡിൽ നോഡിനെ റൂട്ടായി തിരഞ്ഞെടുക്കുമ്പോൾ, ഇടത് സബ്‌റേയിൽ നിന്ന് ഇടത് സബ്‌ട്രീയും വലത് സബ്‌റേയിൽ നിന്ന് വലത് സബ്‌ട്രീയും സൃഷ്ടിക്കേണ്ടതുണ്ട്. ഇത് ഞങ്ങളുടെ യഥാർത്ഥ പ്രശ്നത്തിന്റെ ഒരു ഉപപ്രശ്നമാണ്, അതിനാൽ നമുക്ക് ഇത് ആവർത്തിച്ച് പരിഹരിക്കാൻ കഴിയും. മധ്യ നോഡിലേക്ക് ഇടത്, വലത് സബ്‌ട്രീ നൽകിയ ശേഷം, ഞങ്ങൾക്ക് അത് മടക്കി ബൈനറി തിരയൽ ട്രീയുടെ പോസ്റ്റർ‌ഓർ‌ഡർ‌ ട്രാവെർ‌സൽ‌ അച്ചടിക്കാൻ‌ കഴിയും.

അൽഗോരിതം

  1. മറ്റൊരു പ്രവർത്തനം സൃഷ്ടിക്കുക convertArrayToBST () അത് തന്നിരിക്കുന്ന അറേയുടെ ഏതെങ്കിലും പ്രത്യേക ശ്രേണിയെ പരിവർത്തനം ചെയ്യുകയും അതിന്റെ അനുബന്ധ ജിഎസ്ടി റൂട്ട് നോഡ് നൽകുകയും ചെയ്യും.
  2. മുകളിൽ സൂചിപ്പിച്ച ശ്രേണിയിൽ എൽ = അറേയുടെ ഇടത് പരിധി, അറേയുടെ വലത് പരിധി എന്നിവ അനുവദിക്കുക.
    1. L> R. എങ്കിൽ
      • മടക്കം NULL, ഞങ്ങൾക്ക് ഒരു തെറ്റായ ശ്രേണി ലഭിക്കുന്നതിനാൽ
    2. L == R. എങ്കിൽ
      • തുല്യ മൂല്യമുള്ള ഒരു പുതിയ നോഡ് നൽകുക അറേ [L] 
    3. ഈ ശ്രേണിയുടെ മധ്യ നോഡ് ഇതായി കണ്ടെത്തുക mid = (L + (R - L) / 2)
      • മൂല്യം ഉള്ള ഒരു പുതിയ ജിഎസ്ടി നോഡായി തല സമാരംഭിക്കുക അറേ [മധ്യത്തിൽ]
      • നിയോഗിക്കുക ഇടത്തെ ഒപ്പം വലത് യഥാക്രമം ഇടത്, വലത് ഉപ ശ്രേണികളിൽ വിളിക്കുന്ന അതേ ഫംഗ്ഷന്റെ സബ്‌ട്രീസ്
      • മടങ്ങുക തല
  3. ബൈനറി തിരയൽ ട്രീയുടെ പ്രീഓർഡർ ട്രാവെർസൽ പ്രിന്റുചെയ്യുക

ബൈനറി തിരയൽ ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിലേക്ക് അടുക്കിയ ക്രമീകരണം നടപ്പിലാക്കുക

അടുക്കിയ അറേയെ ബൈനറി തിരയൽ ട്രീയിലേക്ക് പരിവർത്തനം ചെയ്യുന്നതിനുള്ള സി ++ പരിഹാരം

#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 = മരത്തിന്റെ ഉയരം = ലോഗ് എൻ. രണ്ട് ആവർത്തന പ്രവർത്തനങ്ങളിലും, വൃക്ഷം ഉയരം സമതുലിതമാണെന്ന് ഞങ്ങൾ ഉറപ്പാക്കുന്നു, അതിനാൽ, ഞങ്ങൾ പരമാവധി ഉപയോഗിക്കുന്നു O (H) ആവർത്തന സ്റ്റാക്ക് ഫ്രെയിമുകൾക്കുള്ള ഇടം.