बाइनरी सर्च ट्री


कठिनाई स्तर आसान
में अक्सर पूछा वीरांगना डीबीओआई चौपाई इंफोसिस माइक्रोसॉफ्ट
बाइनरी सर्च ट्री बाइनरी ट्री सिद्धांत पेड़

एक बाइनरी सर्च ट्री एक बाइनरी है पेड़ कुछ नियमों के साथ जो हमें क्रमबद्ध तरीके से डेटा को बनाए रखने की अनुमति देता है।

जैसा कि यह एक है बाइनरी ट्री इसलिए, एक नोड में अधिकतम 2 बच्चे हो सकते हैं।

एक द्विआधारी खोज ट्री नोड की संरचना

 

बाइनरी सर्च ट्री

बाइनरी ट्री के लिए नियम बाइनरी सर्च ट्री होना चाहिए

  1. किसी नोड के बाएं उपप्रकार में मौजूद नोड्स उस नोड से कम होना चाहिए।
  2. किसी नोड के सही उपप्रकार में मौजूद नोड्स उस नोड से अधिक होना चाहिए।
  3. पेड़ में सभी नोड्स के लिए उपरोक्त दो स्थितियां सही होनी चाहिए।

उदाहरण

बाइनरी सर्च ट्री

Left subtree of 8 contains: 5, 3, 7 which are smaller than 8

Right subtree of 8 contains: 16, 18 which are greater than 8

Left subtree of 5 contains: 3 which is smaller than 5

Right subtree of 5 contains: 7 which is greater than 5

Left subtree of 16 does not contain any node.

Right subtree of 16 contains: 18 which is greater than 16

3, 7, 18 are leaf nodes hence there will be no left and right subtree present.

हर नोड के लिए BST शर्तों की जांच करना हमेशा याद रखें।

उदाहरण के लिए:

यह बाइनरी सर्च ट्री नहीं है।

बाइनरी सर्च ट्री

बाइनरी सर्च ट्री के फायदे

  1. खोज O (लॉग (h)) में की जा सकती है जहां h BST की ऊंचाई है क्योंकि हम उस संपत्ति पर बाइनरी खोज को लागू कर सकते हैं जो डेटा को BST में क्रमबद्ध तरीके से संग्रहीत किया जाता है।
  2. सॉर्ट किए गए फ़ैशन में डेटा का सम्मिलन O (लॉग (h)) में भी किया जाता है, जबकि अन्य डेटा संरचनाएं जैसे arrays और लिंक्ड सूची इस ऑपरेशन में O (n) समय लगेगा।

बाइनरी सर्च ट्री का निर्माण

कलन विधि

  1. सम्मिलित किए जाने वाले मान के साथ एक नोड बनाएं
  2. सम्मिलित करें (नोड, मान)
    1. यदि रूट == NULL तो बना हुआ नोड लौटाएं
    2. यदि रूट-> मान <कुंजी:
      • बनाए गए नोड को सही उपशीर्षक में डालें
      • रूट-> राइट = इन्सर्टबस्ट (रूट-> राइट, वैल्यू)
    3.  यदि रूट-> मान> कुंजी:
      • बाएं उपप्रकार में निर्मित नोड डालें
      • रूट-> लेफ्ट = इन्सर्टबस्ट (रूट-> लेफ्ट, वैल्यू)
  1. मूल लौटाओ

आइए इसे एक उदाहरण से समझते हैं:

पूर्णांक की एक सरणी पर विचार करें [4, 7, 2, 8, 5]

क्रम से प्रत्येक तत्व को क्रम से लेते हुए BST बनाते हैं

1 कदम: 4 डालें

चूंकि जड़ अशक्त है, इसलिए नए बनाए गए नोड को रूट बनाएं।

बाइनरी सर्च ट्री

2 कदम: 7 डालें

रूट वैल्यू 4 है, इसलिए 7 को रूट के अधिकार में होना चाहिए।

बाइनरी सर्च ट्री

3 कदम: 2 डालें

रूट वैल्यू 4 है, इसलिए 2 को रूट के बाईं ओर रखा जाना चाहिए।

4 कदम: 8 डालें

रूट वैल्यू 4 है, इसलिए 8 को रूट के अधिकार में रखा जाना चाहिए।

अब हम 7 के साथ जांच करेंगे, 7 <8 के रूप में इसलिए 8 को 7 के अधिकार में रखा जाना चाहिए।

5 कदम: 5 डालें

रूट वैल्यू 4 है, इसलिए 5 को रूट के अधिकार में रखा जाना चाहिए।

अब हम 7 के साथ जांच करेंगे, 7> 5 के रूप में इसलिए 5 को 7 के बाईं ओर रखा जाना चाहिए।

बाइनरी सर्च ट्री का कार्यान्वयन

C ++ प्रोग्राम

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

struct node
{
    int value;
    struct node* left;
    struct node* right;
    node(int value){             // constructor
        this->value = value;
        this->left = NULL;
        this->right = NULL;
    }
};
struct node* insertBST(node* root, int value)
{
    if (root == NULL) 
        return new node(value);                       // return newly created node

    if (value < root->value)                         // value should be inserted in the left subtree
        root->left  = insertBST(root->left, value);
    else if (value > root->value)                    // value should be inserted in the right subtree
        root->right = insertBST(root->right, value);   
    return root;
}

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


int main(){
    node *root = NULL;
    root = insertBST(root, 10);     //make the first created node as root
    insertBST(root, 5);
    insertBST(root, 4);
    insertBST(root, 16);
    insertBST(root, 2);
    insertBST(root, 12);
    insertBST(root, 17);

    inorder(root);
}

जावा कार्यक्रम

class Node { 
    int value; 
    Node left, right; 
  
    public Node(int v) { //constructor
        value = v; 
        left = null;
        right = null; 
    } 
};
class Main { 
    public static Node insertBST(Node root, int value) { 
        if (root == null) { 
            return new Node(value);                            // return newly created node
        }
        if (value < root.value)                               // value should be inserted in the left subtree
            root.left = insertBST(root.left, value); 
        else if (value > root.value)                         // value should be inserted in the right subtree
            root.right = insertBST(root.right, value); 
        return root; 
    } 
    public static void inorder(Node root) { 
        if (root != null) { 
            inorder(root.left); 
            System.out.print(root.value+"-> "); 
            inorder(root.right); 
        } 
    } 
    public static void main(String[] args) { 
        Node root = null; 
        
        root = insertBST(root, 10); //make the first created node as root 
        insertBST(root, 5); 
        insertBST(root, 4); 
        insertBST(root, 16); 
        insertBST(root, 2); 
        insertBST(root, 12); 
        insertBST(root, 17); 
        
        inorder(root);
    } 
}
2-> 4-> 5-> 10-> 12-> 16-> 17-> 

निर्मित वृक्ष की संरचना

संदर्भ