የተደረደሩ ድርድርን ወደ ሁለትዮሽ ፍለጋ ዛፍ ሊትኮድ መፍትሄ ይለውጡ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የ Adobe Airbnb አማዞን ፓም ብሉምበርግ Cisco google የ Microsoft በ Oracle Spotify VMware ያሁ
የሁለትዮሽ ፍለጋ ዛፍ ጥልቀት የመጀመሪያ ፍለጋ

የተደረገልን እንደሆንን ያስቡ ደርድር የቁጥር ቁጥሮች። ግቡ ከዚህ ድርድር የሁለትዮሽ ፍለጋ ዛፍ መገንባት ነው ፣ ምክንያቱም ዛፉ በቁመት ሚዛናዊ ነው። በዛፉ ውስጥ ያለው የየትኛውም መስቀለኛ ክፍል የግራ እና የቀኝ ንዑስ ክፍልፋዮች ቁመት ቢበዛ 1 ከሆነ አንድ ዛፍ ቁመት-ሚዛናዊ ነው ይባላል ይባላል ፡፡

ብዙ መፍትሄዎች ሊኖሩ እንደሚችሉ መፈለግ ቀላል ነው። ማንኛውንም ትክክለኛ መፍትሔ መፈለግ አለብን ፡፡ ልብ ይበሉ በዚህ ችግር ውስጥ ፣ አንድን ለመፍጠር እንጂ ዛፉን ማተም አያስፈልገንም ፡፡ የእሱ ቅድመ-ትዕዛዝ መተላለፍን ማተም ብቻ ያስፈልገናል።

ለምሳሌ

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

ማብራሪያ-ቢ.ኤስ.ቲ.

የተደረደሩ ድርድርን ወደ ሁለትዮሽ ፍለጋ ዛፍ ሊትኮድ መፍትሄ ይለውጡ

 

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

ማብራሪያ-ቢ.ኤስ.ቲ.

የተደረደሩ ድርድርን ወደ ሁለትዮሽ ፍለጋ ዛፍ ሊትኮድ መፍትሄ ይለውጡ

አቀራረብ (ዳግም መጥፋት)

ሁለት ነገሮችን መከታተል ያስፈልገናል

  1. ማንኛውም መስቀለኛ ክፍል እንደ ግራ ልጆች ትናንሽ አካላት እና በተቃራኒው ደግሞ ለትክክለኛው ልጆች ሊኖረው ይገባል
  2. BST ቁመት ሚዛናዊ መሆን አለበት

ዛፉ በማንኛውም ቅጽበት ሚዛናዊ ሆኖ እንዲቆይ ለማድረግ የአንድን ድርድር መካከለኛ አካል እንደ ሥሩ መምረጥ አለብን ፡፡ በዚህ መንገድ የከፍታ ልዩነት ይኖረናል 1 ድርድር መጠኑ እና የከፍተኛው ልዩነት እኩል ከሆነ በግራ እና በቀኝ ንዑስ ክፍል መካከል ድርድሩ ያልተለመደ ሆኖ ሲገኝ።

አሁን ማንኛውንም የመሃል አንጓ እንደ ስር ስንመርጥ የግራ ንዑስ ደረጃን ከግራ ንዑስ እና ከቀኝ ንዑስ ክፍል መፍጠር አለብን ፡፡ ይህ የእኛ የመጀመሪያ ችግር ንዑስ-ችግር ነው ስለሆነም እኛ ደጋግመን መፍታት እንችላለን ፡፡ ወደ መካከለኛው መስቀለኛ ክፍል የግራ እና የቀኝ ንዑስ ደረጃን ከሰጠነው በኋላ መመለስ እና የሁለትዮሽ ፍለጋ ዛፍ ፖስትደር ማቋረጥን ማተም እንችላለን።

አልጎሪዝም

  1. ሌላ ተግባር ይፍጠሩ converArrayToBST () የተሰጠውን ማንኛውንም የተወሰነ ክልል የሚቀይር እና ተጓዳኝ የ BST ስርወ መስቀሉን የሚመልስ።
  2. ከላይ በተጠቀሰው ክልል ውስጥ የ L = የግራ ድርድር እና R = የቀኝ ድርድር ወሰን ይስጥ።
    1. L> አር ከሆነ
      • መመለስ ባዶ፣ የተሳሳተ ክልል እንደደረሰን
    2. L == አር ከሆነ
      • እንደ ተመሳሳይ እሴት ያለው አዲስ መስቀለኛ መንገድ ይመልሱ ድርድር [L] 
    3. የዚህን ክልል መካከለኛ መስቀለኛ መንገድ ይፈልጉ እንደ አጋማሽ = (L + (R - L) / 2)
      • የመነሻ ራስ እንደ አዲስ የ BST መስቀለኛ መንገድ ዋጋ ካለው ጋር ድርድር [አጋማሽ]
      • መድብ ግራቀኝ በቅደም ተከተል በግራ እና በቀኝ ንዑስ ክልሎች የተጠራ ተመሳሳይ ተግባር ንዑስ
      • ተመለስ ራስ
  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

የተስተካከለ ድርድርን ወደ ሁለትዮሽ ፍለጋ ዛፍ ሌትኮድ መፍትሄ ውስብስብነት ትንተና

የጊዜ ውስብስብነት

ኦ (ኤን) ፣ N = በዛፉ ውስጥ ያሉት ንጥረ ነገሮች ብዛት። BST ን ለመገንባት እና የቅድመ-ተሻጋሪነትን ለማተም እያንዳንዱን ንጥረ ነገር እንጎበኛለን።

የቦታ ውስብስብነት

ኦ (ኤች) ፣ H = የዛፉ ቁመት = logN. በሁለቱም በድጋሜ ተግባራት ውስጥ ፣ ዛፉ ቁመት-ሚዛናዊ መሆኑን እናረጋግጣለን ፣ ስለሆነም ፣ ከፍተኛውን እንጠቀማለን ኦ (ኤች) ለተደጋጋሚ የቁልል ክፈፎች ቦታ።