பைனரி தேடல் மரம் லீட்கோட் தீர்வில் தேடுங்கள்


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

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

உதாரணமாக

     2
    
  /     \

1         3

             \

               4


Target Value = 3
3 4
     5

  /      \

1         10 


Target Value = 4
Empty BST

விளக்கம் # 1

பிஎஸ்டி மதிப்பு 3 உடன் ஒரு முனையைக் கொண்டுள்ளது, எனவே அதன் துணை மரத்தை திருப்பி அதன் முன்பதிவு பயணத்தை அச்சிடுகிறோம்.

விளக்கம் # 2

பிஎஸ்டியில் மதிப்பு 4 உடன் எந்த முனையும் இல்லை, எனவே நாங்கள் NULL ஐ திருப்பி “வெற்று BST” ஐ அச்சிடுகிறோம்.

அணுகுமுறை (சுழல்நிலை)

இந்த விஷயத்தில் ஒரு சிக்கல் எவ்வாறு துணைப் பிரச்சினையைப் பொறுத்தது என்பதைப் பற்றி சிந்திக்கலாம். கண்டுபிடிக்கப்பட்டால், இலக்கு மதிப்புடன் முனையின் முகவரியை எங்கள் செயல்பாடு வழங்குகிறது என்று சொல்லலாம். மரத்தின் வேரிலிருந்து ஆரம்பிக்கிறோம். இந்த முனை என்றால் ஏதுமில்லை, பைனரி தேடல் மரத்தின் முடிவை நாங்கள் அடைந்துவிட்டோம் என்பது வெளிப்படையானது, எனவே இலக்கு மதிப்புடன் முனை இல்லை. எனவே, நாங்கள் திரும்புவோம் ஏதுமில்லை. இதேபோல், நாம் முனை மதிப்பு இலக்கு மதிப்புக்கு சமம், இந்த முனையை நாங்கள் தருகிறோம். இல்லையெனில், இலக்கு மதிப்புள்ள முனை ஒன்று இருக்கும் என்பதை நாங்கள் அறிவோம் விட்டு subtree அல்லது வலது தற்போதைய மூலத்தின் துணை மரம். Root.value மற்றும் இலக்கு மதிப்பை ஒப்பிடுவதன் மூலம் நாம் திசையை (இடது அல்லது வலது) தீர்மானிக்க முடியும். எனவே, அதே சுழல்நிலை செயல்பாட்டை நாங்கள் அழைக்கிறோம் ரூட் as root.left or root.right.

பைனரி தேடல் மரம் லீட்கோட் தீர்வில் தேடுங்கள்

அல்காரிதம்

  1. ஒரு செயல்பாட்டை உருவாக்கவும் searchBST () இலக்கு முகவரியைத் தர
  2. If ரூட் சமமாக உள்ளது பூஜ்ய OR ரூட் இலக்கின் அதே மதிப்பைக் கொண்டுள்ளது:
    • திரும்ப ரூட்
  3. இலக்கு மதிப்பை விட root.value அதிகமாக இருந்தால்:
    1. திரும்ப searchBST (root.left, val)
  4. திரும்ப searchBST (root.right, val)
  5. இலக்கு முனையின் முன்பதிவு பயணத்தை அச்சிடுக

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

சி ++ திட்டம்

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

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

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    if(root == NULL)
        return root;
    if(val == root->value)
        return root;
    if(val < root->value)
        return searchBST(root->left , val);
    return searchBST(root->right , val);
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

ஜாவா திட்டம்

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        if(root == null)
            return root;
        if(val == root.value)
            return root;
        if(val < root.value)
            return searchBST(root.left , val);
        return searchBST(root.right , val);
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

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

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

O (H), H = logN = சராசரி நிகழ்வுகளில் பிஎஸ்டியின் உயரம் மற்றும் ஓ (என்), என் = மோசமான சந்தர்ப்பங்களில் பிஎஸ்டியின் அளவு. பி.எஸ்.டி வளைந்திருக்கும் போது ஏற்படும் மிக மோசமான நிலையில் மரத்தை ஒரு முறை பயணிக்கிறோம்.

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

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

அணுகுமுறை (மறுபயன்பாடு)

மேலேயுள்ள அணுகுமுறையைப் போலவே, தற்போதைய முனையில் இலக்கு மதிப்பு இல்லாவிட்டால் நாம் இடது அல்லது வலது சப்டிரீக்கு செல்லலாம், ஒதுக்குவதன் மூலம் அதை மீண்டும் செய்ய முடியும் root = root.left or root = root.right வேர் மாறும் வரை ஒவ்வொரு மறு செய்கையிலும் ஏதுமில்லை. எந்தவொரு மறு செய்கையிலும் வேரின் மதிப்பு இலக்கு மதிப்புக்கு சமம் என்று நாம் கண்டால், அந்த மூலத்தை நாங்கள் திருப்பித் தருகிறோம். இல்லையெனில், நாங்கள் திரும்புவோம் ஏதுமில்லை.

அல்காரிதம்

  1. இதே போன்ற செயல்பாட்டை உருவாக்கவும் searchBST () இது இலக்கு முனையின் முகவரியை வழங்குகிறது
  2. போது ரூட் is இல்லை ஏதுமில்லை:
    • if root.value இலக்கு மதிப்புக்கு சமம்
      • திரும்ப ரூட்
    • if root.val is அதிக இலக்கு மதிப்பை விட
      • வலது சப்டிரீக்கு இவ்வாறு நகர்த்தவும்: root = root.right
    • வேறு
      • இடது சப்டிரீக்கு இவ்வாறு நகர்த்தவும்: root = root.left
  3. திரும்ப பூஜ்ய
  4. இலக்கு முனையின் முன்பதிவு பயணத்தை அச்சிடுக

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

சி ++ திட்டம்

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

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

void preorderTraversal(BSTNode* root)
{
    if(root == NULL)
        return;
    cout << root->value << " ";
    preorderTraversal(root->left);
    preorderTraversal(root->right);
    return;
}

BSTNode* searchBST(BSTNode* root , int val)
{
    while(root != NULL)
    {
        if(root->value == val)
            return root;
        if(root->value > val)
            root = root->left;
        else
            root = root->right;
    }
    return NULL;
}

int main()
{
    BSTNode* root = new BSTNode(2);
    root->left = new BSTNode(1);
    root->right = new BSTNode(3);
    root->right->right = new BSTNode(4);
    int val = 3;
    BSTNode* targetNode = searchBST(root , val);
    if(targetNode == NULL)
    {
        cout << "Empty Tree" << '\n';
        return 0;
    }
    preorderTraversal(targetNode);
    return 0;
}

ஜாவா திட்டம்

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

class search_in_BST
{
    public static void main(String args[])
    {
        BSTNode root = new BSTNode(2);
        root.left = new BSTNode(1);
        root.right = new BSTNode(3);
        root.right.right = new BSTNode(4);
        int val = 3;
        BSTNode targetNode = searchBST(root , val);
        if(targetNode == null)
        {
            System.out.println("Empty Tree");
            System.exit(0);
        }
        preorderTraversal(targetNode);
    }

    static BSTNode searchBST(BSTNode root , int val)
    {
        while(root != null)
        {
            if(root.value == val)
                return root;
            if(root.value > val)
                root = root.left;
            else
                root = root.right;
        }
        return null;
    }

    static void preorderTraversal(BSTNode root)
    {
        if(root == null)
            return;
        System.out.print(root.value + " ");
        preorderTraversal(root.left);
        preorderTraversal(root.right);
        return;
    }
}
3 4

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

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

O (H = logN) சராசரி நிகழ்வுகளில் மற்றும் ஓ (என்) மோசமான சந்தர்ப்பங்களில் (வளைந்த பிஎஸ்டி), மேலே உள்ள அணுகுமுறையைப் போன்றது.

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

ஓ (1) நாம் நிலையான நினைவக இடத்தை மட்டுமே பயன்படுத்துகிறோம்.