Binary Search Tree (BST)
BST Model और Invariant
Binary search tree में हर node की left subtree की सभी keys छोटी और right subtree की सभी keys बड़ी होती हैं। Rule हर subtree पर recursively लागू होता है। इस program में duplicate key ignore होती है।
50
/ \
30 70
/ \ / \
20 40 60 80Insertion order tree shape बदलता है; हर BST balanced नहीं होता।
Node Ownership
struct Node {
int key;
std::unique_ptr<Node> left, right;
explicit Node(int value) : key(value) {}
};Node अपने children को exclusively own करता है। Root destroy होने पर पूरा tree automatic release होता है; manual delete की जरूरत नहीं। Smart pointers पढ़ें।
Insert और Search
Key छोटी हो तो left, बड़ी हो तो right path लें। Null link पर new node बनता है। Search भी एक root-to-leaf path follow करता है और null मिलने पर false देता है। Owning pointer reference insert को empty child replace करने देता है।
Tree Traversals
| Traversal | Order | Use |
|---|---|---|
| Inorder | Left, node, right | BST की ascending keys |
| Preorder | Node, left, right | Root first |
| Postorder | Left, right, node | Children first |
| Level order | Depth-wise | Tree shape |
Full traversal Θ(n) time और recursive O(h) stack लेता है।
Deletion के तीन Cases
- Leaf: owning link null करें।
- One child: child ownership target link में move करें।
- Two children: right subtree की minimum key (successor) copy कर उसके original node को delete करें।
unique_ptr move ownership सुरक्षित transfer करता है।
Height और Complexity
| Operation | Cost |
|---|---|
| Search/Insert/Delete | O(h) |
| Balanced height | Θ(log n) |
| Skewed height | Θ(n) |
| Traversal | Θ(n) |
| Storage | Θ(n) |
Sorted insertion chain बना सकता है। Height guarantee के लिए AVL/red-black concept और practical ordered data के लिए std::set/std::map देखें।
Complete Modern C++ Lab
std::unique_ptr<Node> root;
for (int key : {50,30,70,20,40,60,80}) insert(root,key);
std::cout << "Inorder:"; inorder(root);
std::cout << std::boolalpha << contains(root,60);
erase(root,30);English section का full compile-ready program insert, search, inorder और three-case deletion implement करता है। 30 के successor 40 से replacement होता है।
Mistakes, Tests और Practice
- Ordering केवल direct child पर नहीं, whole subtree पर लागू है।
- Duplicate policy document करें।
- Delete में child ownership न खोएं।
- Actual height analyze करें; BST को automatic balanced न कहें।
- Null base case पहले रखें।
Empty, leaf, one-child, two-child, root, absent और skewed cases test करें। Height और BST validator practice करें।
Authoritative संदर्भ
Definitions और ordering invariant authoritative sources से verify हैं।
