Binary Search Tree (BST) एक बहुत ही उपयोगी data structure है, जिसे fast search, insertion, और deletion operations के लिए इस्तेमाल किया जाता है। यह एक special kind of binary tree है जिसमें हर node की left subtree में मौजूद सभी elements उस node से छोटे होते हैं और right subtree में मौजूद सभी elements उस node से बड़े होते हैं। चलिए अब BST के operations, traversal methods, और search technique को detail में समझते हैं।

 

Binary Search Tree (BST) Properties

1. हर node के left subtree के elements छोटे होते हैं।

2. हर node के right subtree के elements बड़े होते हैं।

3. Left और Right subtree भी BST होते हैं।

 

Binary Search Tree Operations

 

1. Insertion

 

BST में insertion करते समय हमें हमेशा root से comparison शुरू करना होता है:

1. अगर new node की value current node से छोटी है, तो उसे left subtree में place करें।

2. अगर new node की value current node से बड़ी है, तो उसे right subtree में place करें।

3. ऐसा तब तक करते रहें जब तक हमें खाली स्थान (NULL) न मिल जाए, जहां हम नई node को insert कर सकें।

 

Example: यदि हमें 15, 10, 20, 8, 12, 18, और 25 values को BST में insert करना है, तो final tree कुछ इस प्रकार बनेगा:

        15

       /  \

     10    20

    / \        / \

   8  12  18 25

 

2. Deletion

BST में deletion एक थोड़ा tricky process हो सकता है। तीन conditions होती हैं जब हम किसी node को delete करते हैं:

1. Node is a leaf: Directly delete the node.

2. Node has one child: Delete the node and link its child to its parent.

3. Node has two children: Delete the node and replace it with its in-order successor (right subtree का सबसे छोटा element) या in-order predecessor (left subtree का सबसे बड़ा element) से।

3. Searching

Searching BST में बहुत efficient होता है क्योंकि हम एक comparison के बाद subtree को discard कर सकते हैं।

1. अगर key current node से छोटी है, तो हम left subtree में search करेंगे।

2. अगर key current node से बड़ी है, तो हम right subtree में search करेंगे।

3. अगर key current node के बराबर है, तो element found हो गया है।

Example: 12 को search करने के लिए हम 15 से start करेंगे। चूंकि 12, 15 से छोटा है, हम left subtree (10) पर जाएंगे। फिर, 12, 10 से बड़ा है, तो हम 12 पर पहुंचेंगे और इसे find कर लेंगे।

Binary Search Tree Traversal Methods

Traversal methods हमें tree के nodes को specific order में access करने की सुविधा देते हैं। तीन primary BST traversal methods होते हैं:

1. In-Order Traversal (L-N-R)

BST की एक खासियत है कि अगर हम In-order traversal का उपयोग करते हैं, तो हमें sorted order में elements मिलते हैं। Process:

1. Left subtree को traverse करें।

2. Node को visit करें।

3. Right subtree को traverse करें।

 

In-Order Traversal of above tree: 8, 10, 12, 15, 18, 20, 25

 

2. Pre-Order Traversal (N-L-R)

Pre-order traversal में हम पहले node को visit करते हैं, फिर left subtree और अंत में right subtree को traverse करते हैं। Process:

1. Node को visit करें।

2. Left subtree को traverse करें।

3. Right subtree को traverse करें।

 

Example:

Pre-Order Traversal of above tree: 15, 10, 8, 12, 20, 18, 25

 

3. Post-Order Traversal (L-R-N)

 

Post-order traversal में हम पहले left subtree और right subtree को traverse करते हैं, और अंत में node को visit करते हैं। Process:

1. Left subtree को traverse करें।

2. Right subtree को traverse करें।

3. Node को visit करें।

Post-Order Traversal of above tree: 8, 12, 10, 18, 25, 20, 15

 

BST Search Algorithm (Pseudo-Code)

 

BST में search करना recursive या iterative तरीके से किया जा सकता है। यहां हम recursive search algorithm का pseudo-code दिखा रहे हैं:

 

Node* searchBST(Node* root, int key) {

    // Base case: root is null or key is present at root

    if (root == NULL || root->data == key)

        return root;

 

    // Key is greater than root's key, search right subtree

    if (root->data < key)

        return searchBST(root->right, key);

 

    // Key is smaller than root's key, search left subtree

    return searchBST(root->left, key);

}

 

Conclusion

 

Binary Search Tree (BST) एक powerful data structure है जो insertion, deletion, और searching operations को efficient तरीके से handle करता है। इसकी properties और traversal methods इसे कई applications में ideal choice बनाती हैं, जैसे कि search algorithms, databases, और memory management systems में। Traversal methods जैसे in-order, pre-order, और post-order different use-cases के लिए उपयोगी हैं। BST का सही understanding आपको कई complex algorithms को आसानी से solve करने में मदद कर सकता है।