சமப்படுத்தப்பட்ட பைனரி மரம் லீட்கோட் தீர்வு


சிரமம் நிலை எளிதாக
அடிக்கடி கேட்கப்படுகிறது அமேசான் கூகிள் மைக்ரோசாப்ட்
அணி

A பைனரி மரம் மரத்தின் ஒவ்வொரு முனையின் இடது மற்றும் வலது சப்டிரீயின் உயரங்களின் வேறுபாடு அதிகபட்சமாக இருந்தால் உயரம் சமநிலையானது. இந்த சிக்கலில், நாம் ஒரு சீரான பைனரி மரத்தை சோதிக்கப் போகிறோம்.

சமப்படுத்தப்பட்ட பைனரி மரம் லீட்கோட் தீர்வு

உதாரணமாக

             2
        
          / 
    
        1

      /
 
    4
Not balanced
     1

  /     \

2         3
Balanced

அணுகுமுறை

என்று நினைப்பது உள்ளுணர்வு ஒவ்வொரு பைனரி மரத்தில் உள்ள முனை, இடது மற்றும் வலது சப்டிரீக்கள் தேவையான நிலையைப் பின்பற்றுகிறதா இல்லையா என்பதை நாம் சரிபார்க்கலாம். அதுதான் “முரட்டு படை”முறை.

ஆனால், மரம் சீரானதா என்பதை சரிபார்க்க, அணுகுமுறையை அடிப்படையாகக் கொண்டு மேம்படுத்தலாம் நேரம் & இடம் சிக்கல்கள்.

ஒரு அணுகுமுறையை நாங்கள் பின்பற்றுகிறோம் பாட்டம் அப் முறை. ஒரு முனையின் சப்டிரீக்கள் தானே, சீரான பைனரி என்பதை சரிபார்க்கவும் மரங்கள்(அல்லது இல்லை) மற்றும் பைனரி மரத்தின் உயரத்தை ஒரே நேரத்தில் பெறுங்கள், அவை மறுநிகழ்வைப் பயன்படுத்தி பொதுமைப்படுத்தப்படலாம்.

அல்காரிதம் (முரட்டு படை)

  1. வேரிலிருந்து தொடங்கி பைனரி மரத்தை கடந்து செல்லும் வரை ரூட் ஆகிறது சுழியாக
  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

சமச்சீர் பைனரி மரம் லீட்கோட் தீர்வின் சிக்கலான பகுப்பாய்வு

நேர சிக்கலானது

ப்ரூட் ஃபோர்ஸ் முறை ஒரு நேர சிக்கலைக் கொண்டுள்ளது ஓ (என் * என்), மிக மோசமான நிலையில் (வளைந்த மரம்). இருப்பினும், உகந்த அணுகுமுறை செயல்படுகிறது ஓ (என்) நாம் ஒரு பாஸ் மட்டுமே செய்யும் நேரம்.

விண்வெளி சிக்கலானது

ஓ (என்) இரண்டு நிகழ்வுகளிலும், மறுநிகழ்வு துணை அடுக்கு இடத்தைப் பயன்படுத்துகிறது.