Binary Search Tree ( बाइनरी सर्च ट्री)
Binary Search Tree एक विशेष प्रकार का Binary Tree है, जिसमें हर node एक specific rule को follow करता है :
Key Point :
- Left Subtree के सभी nodes की value Root Node से छोटी होती है
(value < Root value) - Right Subtree के सभी nodes की value Root Node से बड़ी होती है
(value > Root value) - BST में ideally duplicate values नहीं रखी जाती
इस rule की वजह से BST searching, insertion, deletion जैसे operations बहुत तेजी से करता है।
उदाहरण (Simple Example)
मान लीजिए आपने values insert की : 50, 30, 70, 20, 40, 60, 80
तो Binary Search Tree का structure कुछ इस तरह होगा
इस structure की वजह से BST में किसी भी element को Search करना बहुत easy हो जाता है।
Features of Binary Search Tree (BST की विशेषताएँ)
1. Ordered Structure
- BST में हर node एक rule follow करता है :
Left Subtree के सभी nodes की value root से छोटी होती है।
Right Subtree के सभी nodes की value root से बड़ी होती है।
इस ordered structure की वजह से searching बहुत तेज़ होती है।
2. Fast Searching
- BST एक तरह से Binary Search Algorithm का tree version है।
इसमें किसी भी value को search करने में average time लगता है : O(log n)
इसलिए बड़े datasets के लिए बहुत उपयोगी है।
3. Unique or Non-duplicate Values
- Ideal BST में duplicate values allow नहीं की जातीं, जिससे tree का structure clean और predictable रहता है।
4. Dynamic Data Structure (Dynamic Memory Usage)
- BST run-time में grow या shrink हो सकता है, इसलिए memory का wastage नहीं होता।
Array की तरह fixed size define नहीं करना पड़ता।
5. Supports Efficient Operations
- BST में main operations — Insertion, Deletion, Searching तीनों average case में बड़ी efficiency से perform होते हैं।
6. Inorder Traversal Gives Sorted Output
- BST का सबसे powerful feature : Inorder Traversal → हमेशा sorted output देता है।
- यह property real-world systems में बहुत useful है (जैसे database indexing)।
7. Recursive Structure (Recursion Friendly)
- BST में लगभग हर operation recursion पर depend करता है।
- इससे code simple और readable बनता है।
8. Height-based Performance
- BST का performance tree की height पर depend करता है:
- Balanced BST → Fast (O(log n))
- Skewed BST → Slow (O(n))
- इसलिए AVL Tree, Red-Black Tree जैसे balanced BSTs exist करते हैं।
Operations on Binary Search Tree (BST ऑपरेशन्स)
BST पर मुख्यतः तीन major operations perform होते हैं :
- Insertion (नया node जोड़ना)
- Search (किसी element को ढूँढना)
- Deletion (node को हटाना)
1. BST Insertion Operation
BST में कोई नया element insert करने के लिए root से शुरुआत की जाती है, और comparison के आधार पर value को सही जगह रखा जाता है।
Insertion Rule
- अगर new value छोटी है → Left Subtree जाएँ
- अगर new value बड़ी है → Right Subtree जाएँ
- जहाँ NULL मिले, वहीं नया node insert कर दिया जाता है
Example :
Insert : 40
Tree में root = 50
40 < 50 → left
40 > 30 → right
40 insert हो जाएगा।
2. BST Search Operation
Searching BST का सबसे powerful operation है। BST की property searching को तेज (O(log n)) बनाती है।
Search Rule
- If key == root → Found
- If key < root → Left search
- If key > root → Right search
Example : Search – 60
50
/ \
30 70
/ \ / \
20 40 60 80
\
45
Step-by-Step Search Process :
Step 1 — Compare with Root
- Root = 50
- 45 < 50 → Left Subtree में जाएँ
Step 2 — Compare with 30
- Current node = 30
- 45 > 30 → Right Subtree में जाएँ
Step 3 — Compare with 40
- Current node = 40
- 45 > 40 → Right child चेक करें
Step 4 — Compare with 45
- Current node = 45
- 45 == 45 → Element Found
3. BST Deletion Operation
Case 1 : Leaf Node Delete करना
जिस node के कोई children नहीं हैं
→ simply node हटा दें।
Example : Delete 20
20 direct remove हो जाएगा।
Case 2 : Node with One Child
Node का एक ही child हो
→ उस node को bypass करके उसके child को parent से जोड़ दिया जाता है।
Case 3 : Node with Two Children (Most Important)
इसमें node को हटाने के जगह उसको Inorder Successor या Inorder Predecessor से replace करते हैं।
Steps :
- Node की जगह successor की value रखो
- Successor को delete करो
Example (उदाहरण)
Insert Elements – 50, 30, 70, 20, 40, 60, 80, 65
Insertions — step by step
1. Insert 50 (root)
50
2. Insert 30 (30 < 50 → left)
50
/
30
3. Insert 70 (70 > 50 → right)
50
/ \
30 70
4. Insert 20 (20 < 50 → left; 20 < 30 → left of 30)
50
/ \
30 70
/
20
5. Insert 40 (goes right of 30)
50
/ \
30 70
/ \
20 40
7. Insert 60 (left of 70)
50
/ \
30 70
/ \ /
20 40 60
7. Insert 80 (right of 70)
50
/ \
30 70
/ \ / \
20 40 60 80
8. Insert 65 (65 < 70 → left; 65 > 60 → right of 60)
50
/ \
30 70
/ \ / \
20 40 60 80
\
65
Final BST after all insertions is the tree above.
Advantages of BST (लाभ)
1. Fast Searching
- BST में searching बहुत तेज होती है, क्योंकि हर comparison पर search space आधा हो जाता है।
- Time : O(log n) (balanced tree में)
2. Fast Insertion & Deletion
- Insertion और deletion भी ordered structure के कारण efficient होते हैं।
- हर item सही position पर रखा जाता है।
3. Sorted Data Storage
- BST हमेशा data को sorted form में रखता है।
- इससे traversal करते समय data sorted order में मिल जाता है।
4. Inorder Traversal Gives Sorted Output
- BST की सबसे बड़ी Achievement : Inorder traversal → हमेशा sorted data देता है।
5. Dynamic Data Structure
- Memory dynamically allocate होती है (linked structure)।
- Size को पहले से fix करने की जरूरत नहीं।
6. Useful in Many Applications
- Symbol table, indexing, searching, ranking, expression tree आदि में BST का उपयोग होता है।
Disadvantages of BST (हानि)
1. Worst Case Time Complexity O(n)
- tree unbalanced हो जाए (skewed tree), तो searching, insertion, deletion सब slow हो जाते हैं।
2. Balance Maintain Hard
- Normal BST automatically balance नहीं करता।
- अगर data sorted order में insert किया जाए, tree unbalanced हो सकता है।
3. Extra Pointer Overhead
- हर node में दो pointers (left & right) होने के कारण memory usage बढ़ता है।
4. Not Suitable for Random Access
- Array की तरह index-based access (a[3]) संभव नहीं। किसी भी element तक पहुँचने के लिए tree traversal करना पड़ता है।
5. Performance Depends on Structure
- BST की performance पूरी तरह उसकी shape पर depend करती है।
