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


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ആമസോൺ ഗൂഗിൾ മൈക്രോസോഫ്റ്റ്
അറേ

A ബൈനറി ട്രീ വൃക്ഷത്തിലെ ഓരോ നോഡിന്റെയും ഇടത്, വലത് സബ്‌ട്രീയുടെ ഉയരങ്ങളുടെ വ്യത്യാസം പരമാവധി 1 ആണെങ്കിൽ ഉയരം സമതുലിതമാണ്. ഈ പ്രശ്‌നത്തിൽ, ഞങ്ങൾ ഒരു സമീകൃത ബൈനറി ട്രീ പരിശോധിക്കാൻ പോകുന്നു.

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

ഉദാഹരണം

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

സമീപനം

അത് ചിന്തിക്കുന്നത് അവബോധജന്യമാണ്, കാരണം ഓരോ ബൈനറി ട്രീയിലെ നോഡ്, ഇടത്, വലത് സബ്‌ട്രീകൾ ആവശ്യമായ അവസ്ഥ പാലിക്കുന്നുണ്ടോ ഇല്ലയോ എന്ന് ഞങ്ങൾക്ക് പരിശോധിക്കാൻ കഴിയും. അതാണ് “ബ്രൂട്ട് ഫോഴ്സ്”രീതി.

പക്ഷേ, മരം സമതുലിതമാണോയെന്ന് പരിശോധിക്കുന്നതിന്, അതിന്റെ അടിസ്ഥാനത്തിൽ സമീപനം മെച്ചപ്പെടുത്താൻ കഴിയും സമയവും സ്ഥലവും സങ്കീർണ്ണതകൾ.

A- ൽ പ്രശ്നം പരിഹരിക്കുന്ന തരത്തിലുള്ള ഒരു സമീപനമാണ് ഞങ്ങൾ പിന്തുടരുന്നത് Bottom-up വിധത്തിൽ. ഒരു നോഡിന്റെ സബ്‌ട്രീകൾ തന്നെയാണോ, സമതുലിതമായ ബൈനറി ആണോയെന്ന് പരിശോധിക്കുക മരങ്ങൾ(അല്ലെങ്കിൽ അല്ല) ഒരേ സമയം ബൈനറി ട്രീയുടെ ഉയരം നേടുക, ഇത് ആവർത്തനം ഉപയോഗിച്ച് സാമാന്യവൽക്കരിക്കാനാകും.

അൽഗോരിതം (ബ്രൂട്ട് ഫോഴ്സ്)

  1. റൂട്ടിൽ നിന്ന് ആരംഭിച്ച് ബൈനറി ട്രീയിലൂടെ സഞ്ചരിക്കുന്നത് വരെ വേര് മാറുന്നു NULL
  2. ഉപയോഗിച്ച് ഇടത്, വലത് സബ്‌ട്രീകളുടെ ഉയരം വീണ്ടെടുക്കുക ഉയരം () ഫംഗ്ഷൻ
    • വ്യത്യാസം കൂടുതലാണെങ്കിൽ '1':
      • തെറ്റായി മടങ്ങുക. മരം ബാലൻസ് അവസ്ഥയെ തൃപ്തിപ്പെടുത്താത്തതിനാൽ
    • ഇടത്, വലത് സബ്‌ട്രീകൾക്കായി ബാലൻസ് അവസ്ഥ ആവർത്തിച്ച് പരിശോധിക്കുക
  3. ഫലം അച്ചടിക്കുക

അൽഗോരിതം (ഒപ്റ്റിമൽ)

  1. മരം ആണെങ്കിൽ ശൂന്യമാണ്, ഇത് സമതുലിതമാണെന്ന് നമുക്ക് പറയാം. ഇല്ലെങ്കിൽ, ഞങ്ങൾക്ക് മറ്റ് ഘട്ടങ്ങൾ പാലിക്കാം:
  2. “തിരികെ നൽകാൻ ഒരു സഹായി ഫംഗ്ഷൻ സൃഷ്ടിക്കുകപൊക്കംആവർത്തനം ഉപയോഗിച്ച് നിലവിലെ സബ്‌ട്രീയുടെ ”.
  3. ഉയരം പ്രവർത്തനം മടങ്ങും:
    • -1, ഇത് അസന്തുലിതമായ വൃക്ഷമാകുമ്പോൾ
    • അല്ലാത്തപക്ഷം ഉയരം.
  4. ഒരു സബ്‌ട്രീ ഇടത് അല്ലെങ്കിൽ വലത് സബ്‌ട്രീ ഉണ്ടെങ്കിൽ അസന്തുലിതമായ, അല്ലെങ്കിൽ അവയുടെ ഉയരം '1' എന്നതിനേക്കാൾ വ്യത്യാസപ്പെട്ടിരിക്കുന്നു, മടങ്ങുക -1.
  5. അല്ലെങ്കിൽ, ഈ സബ്‌ട്രീയുടെ ഉയരം ഇപ്രകാരം നൽകുക: 1 + പരമാവധി (ഇടത്_ ഉയരം, വലത്_ ഉയരം)

നടപ്പിലാക്കൽ

സമീകൃത ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സി ++ പ്രോഗ്രാം

ബ്രൂട്ട് ഫോഴ്‌സ് രീതി

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    return max(height(root->left) , height(root->right)) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
    return true;

    int l = height(root->left) , r = height(root->right);
    //calling height function at every node
    if(abs(l - r) > 1)
        return false;

    return balanced(root->left) && balanced(root->right);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);
    
    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}

ഒപ്റ്റിമൽ രീതി

#include <bits/stdc++.h>
using namespace std;
struct treeNode
{
    int value;
    treeNode *left , *right;
    treeNode(int x)
    {
        value = x;
        left = NULL;
        right = NULL;
    }
};


int height(treeNode* root)
{
    if(root == NULL)
        return 0;
    int l = height(root->left);
    int r = height(root->right);
    if(l == -1 || r == -1 || abs(l - r) > 1)
        return -1;
    return max(l , r) + 1;
}


bool balanced(treeNode* root)
{
    if(root == NULL)
        return true;

    return (height(root) != -1);
}


int main()
{
    treeNode* root = new treeNode(2);
    root->left = new treeNode(2);
    root->left->left = new treeNode(4);

    if(balanced(root))
        cout << "Balanced" << '\n';
    else
        cout << "Not Balanced" << '\n';
    return 0;
}
Not Balanced

സമതുലിതമായ ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ ജാവ പ്രോഗ്രാം

ബ്രൂട്ട് ഫോഴ്സ്

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;
        return Math.max(height(root.left) , height(root.right)) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        int l = height(root.left) , r = height(root.right);
        if(Math.abs(r - l) > 1)
            return false;
        return balanced(root.left) && balanced(root.right);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.right = new treeNode(3);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}

ഒപ്റ്റിമൽ രീതി

import java.lang.Math;

class treeNode
{
    int value;
    treeNode left, right;

    public treeNode(int x)
    {
        value= x;
        left = right = null;
    }
}

class balanced_binary_tree
{
    public static int height(treeNode root)
    {
        if(root == null)
            return 0;

        int l = height(root.left);
        int r = height(root.right);

        if(l == -1 || r == -1 || Math.abs(l - r) > 1)
            return -1;

        return Math.max(l , r) + 1;
    }


    public static boolean balanced(treeNode root)
    {
        if(root == null)
            return true;

        return (height(root) != -1);
    }


    public static void main(String args[])
    {
        treeNode root = new treeNode(2);
        root.left = new treeNode(1);
        root.left.left = new treeNode(4);

        if(balanced(root))
            System.out.println("Balanced");
        else
            System.out.println("Not Balanced");
    }
}
Not Balanced

സമതുലിതമായ ബൈനറി ട്രീ ലീറ്റ്കോഡ് പരിഹാരത്തിന്റെ സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

ബ്രൂട്ട് ഫോഴ്‌സ് രീതിക്ക് സമയ സങ്കീർണ്ണതയുണ്ട് O (N * N), ഏറ്റവും മോശം അവസ്ഥയിൽ (വളഞ്ഞ വൃക്ഷം). എന്നിരുന്നാലും, ഒപ്റ്റിമൽ സമീപനം പ്രവർത്തിക്കുന്നു O (N) ഞങ്ങൾ ഒരു പാസ് മാത്രം ചെയ്യുന്ന സമയം.

ബഹിരാകാശ സങ്കീർണ്ണത

രണ്ട് സന്ദർഭങ്ങളിലും O (N), ആവർത്തനം സഹായ സ്റ്റാക്ക് സ്പേസ് ഉപയോഗിക്കുന്നു.