परिचय
बाइनरी सर्च ट्री (बीएसटी) एक प्रकार का बाइनरी ट्री है जहां प्रत्येक नोड में अधिकतम दो बच्चे होते हैं, जिन्हें बायां बच्चा और दायां बच्चा कहा जाता है। प्रत्येक नोड के लिए, बाएं उपट्री में केवल नोड के मान से कम मान वाले नोड्स होते हैं, और दाएं उपट्री में केवल नोड के मान से अधिक मान वाले नोड्स होते हैं। बीएसटी का उपयोग कुशल खोज, सम्मिलन और विलोपन कार्यों के लिए किया जाता है।

बाइनरी सर्च ट्री का उपयोग क्यों करें?
बीएसटी कई लाभ प्रदान करते हैं:

कुशल खोज: खोज, सम्मिलन और विलोपन के लिए औसत समय जटिलता O(लॉग एन) है।
वस्तुओं का गतिशील सेट: स्थिर सरणियों के विपरीत, गतिशील संचालन का समर्थन करता है।
क्रमबद्ध तत्व: BST के इन-ऑर्डर ट्रैवर्सल से क्रमबद्ध क्रम में तत्व प्राप्त होते हैं।
बीएसटी बनाने के लिए चरण-दर-चरण मार्गदर्शिका
चरण 1: नोड संरचना को परिभाषित करें
पहला कदम पेड़ में एक नोड की संरचना को परिभाषित करना है। प्रत्येक नोड में तीन विशेषताएँ होंगी: एक मान, बाएँ बच्चे का संदर्भ, और दाएँ बच्चे का संदर्भ।

public class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}

चरण 2: कंस्ट्रक्टर के साथ बीएसटी क्लास बनाएं
इसके बाद, हम BST क्लास बनाते हैं जिसमें पेड़ की जड़ और तत्वों को सम्मिलित करने के तरीकों का संदर्भ होता है।

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }
}

चरण 3: सम्मिलन विधि लागू करें
बीएसटी में एक तत्व सम्मिलित करने के लिए, हमें नए नोड के लिए सही स्थिति ढूंढनी होगी। सम्मिलन विधि आमतौर पर एक पुनरावर्ती फ़ंक्शन के रूप में कार्यान्वित की जाती है।

public void insert(int value) {
    root = insertRec(root, value);
}

private TreeNode insertRec(TreeNode root, int value) {
    // Base case: if the tree is empty, return a new node
    if (root == null) {
        root = new TreeNode(value);
        return root;
    }

    // Otherwise, recur down the tree
    if (value  root.value) {
        root.right = insertRec(root.right, value);
    }

    // Return the (unchanged) node pointer
    return root;
}

विज़ुअलाइज़ेशन
यह बेहतर ढंग से समझने के लिए कि प्रविष्टि कैसे काम करती है, आइए एक उदाहरण पर विचार करें। मान लीजिए कि हम बीएसटी में संख्याओं का निम्नलिखित क्रम सम्मिलित करना चाहते हैं: 50, 30, 70, 20, 40, 60, 80।

50

  50
 /
30

  50
 /  \
30  70

50
 /  \
30  70
/

40 डालें:

  50
 /  \
30  70
/ \

60 डालें

  50
 /  \
30  70
/ \  /

80 डालें:

  50
 /  \
30  70
/ \  / \

पूर्ण कोड
यहां BST बनाने और तत्व सम्मिलित करने का पूरा कोड है:

public class BinarySearchTree {
    TreeNode root;

    public BinarySearchTree() {
        this.root = null;
    }

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value  root.value) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }

    // Additional methods for traversal, search, and delete can be added here

    public static void main(String[] args) {
        BinarySearchTree bst = new BinarySearchTree();
        int[] values = {50, 30, 70, 20, 40, 60, 80};
        for (int value : values) {
            bst.insert(value);
        }

        // Add code to print or traverse the tree
    }
}

class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) {
        this.value = value;
        this.left = null;
        this.right = null;
    }
}