Tree (ट्री)
Tree एक hierarchical data structure है, जिसमें data को parent–child relationship के रूप में organize किया जाता है। Tree कई nodes से मिलकर बनता है, और हर node एक या उससे अधिक child nodes रख सकता है। Nodes को आपस में edges जोड़ते हैं।
Key Points :
- Tree एक non-linear data structure है।
- इसमें एक root node होता है (सबसे शीर्ष node)।
- हर node में 0 या अधिक child nodes हो सकते हैं।
- Root node को छोड़कर हर node का एक parent होता है।
- Nodes केवल edges के द्वारा जुड़े होते हैं।
- Tree का उपयोग hierarchical structure दिखाने में किया जाता है।
उदाहरण : IRCTC train booking system
- Root Node : Train Booking System
- Child Nodes : User Details, Train Selection, Payment
- Sub-Child Nodes : Name, Age, Class Selection, Seat Preference, Payment Mode
यह structure hierarchical होने के कारण data को organized तरीके से access और manage करना आसान बनाता है।
Types of Tree (Tree के प्रकार)
1. General Tree (सामान्य ट्री)
- किसी node के कोई भी number of children हो सकते हैं।
- कोई restriction (प्रतिबंध) नहीं होती।
- Example : Company hierarchy, Flipkart category tree
- Use Case : जहां parent के multiple children हो सकते हैं, जैसे organization chart।
2. Binary Tree (बाइनरी ट्री)
- हर node के maximum 2 children होते हैं।
- Children : Left child और Right child
- Example : Expression Tree, जैसे : 5 + (3 × 2)
- Use Case : Arithmetic expression evaluation, binary decision-making
3. Binary Search Tree / BST (बाइनरी सर्च ट्री)
- Binary Tree का special type होता है|
- Left child < Parent < Right child
- Example : Student database में Roll Number के अनुसार search करना
- Use Case : Search, insert और delete operations में fast retrieval
4. AVL Tree / Balanced Binary Tree (संतुलित बाइनरी ट्री)
- Self-balancing Binary Search Tree है
- हर node के left और right subtree की height difference ≤ 1
- Example : Real-time database search optimization
- Use Case : जब fast search और update operations जरूरी हों
5. Complete Binary Tree (पूर्ण बाइनरी ट्री)
- Binary Tree जिसमें सभी levels except last completely filled हों और last level में nodes left to right भरें
- Example : Heap Data Structure
- Use Case : Priority Queue implementation
Tree Important Terminologies
1. Root Node
- Tree का Starting point root node होता है। और इसका कोई parent नहीं होता।
- Example : IRCTC booking system में main dashboard।
2. Leaf Node / Terminal Node
- Leaf nodes वे nodes होते हैं जिनके कोई children नहीं होते।
- Example : Train seat selection में specific seat।
3. Internal Node
- वह node जिसका कम से कम एक child हो, उसे internal node कहते हैं।
- Example : “Train Selection” जहां से class, timing और seat availability जैसे options खुलते हैं।
4. Parent Node And Child Node
- Parent node वह होता है जिसके child nodes होते हैं।
- Child node वही है जो किसी parent से जुड़ा हो।
5. Sibling Nodes
- Same parent वाले nodes Sibling Nodes कहलाते है
- Example : Class selection में AC और Sleeper — दोनों एक ही parent के Noeds हैं, इसलिए siblings।
6. Degree of a Node
- किसी node के child nodes की संख्या, उसकी degree कहलाती है।
- Example : अगर Train Selection के नीचे 3 choices हैं, तो उसकी degree = 3।
7. Degree of a Tree
- Tree में सबसे अधिक degree वाला node, tree की degree कहलाती है।
- Example : अगर सिर्फ एक node के 5 child हैं, तो tree की degree = 5।
8. Height of a Node
- Root से किसी node तक जाने वाला सबसे लंबा path — यह node की height होती है।
- Root की height को उसी tree की maximum height माना जाता है।
9. Depth of a Node
- Root node से node तक का path length (edges की संख्या)
- Root की depth हमेशा 0 होती है।
10. Level of a Node
- Level निकालना बहुत आसान है — depth में 1 जोड़ दो।
- Root का level = 1, उसके नीचे वाले nodes का level = 2, और आगे इसी तरह चलता है।
11. Edge
- Nodes को आपस में जोड़ने वाली line ही edge कहलाती है।
- Example : Train Selection → Train 1 के बीच की connecting लाइन खुद एक edge है।
12. Subtree
- किसी एक node और उसके नीचे आने वाले सभी nodes मिलकर जो छोटा structure बनाते हैं, वही subtree होता है।
- Example : “Train Selection” और उसके नीचे की सभी trains एक subtree बनाते हैं।
Applications of Tree (उपयोग)
- File System में folders और files को hierarchical तरीके से organize करने में Tree का उपयोग होता है।
- Database indexing (B-Tree, B+ Tree) में fast searching के लिए tree structures उपयोग होते हैं।
- AI / ML में Decision Tree algorithms predictions और classifications के लिए उपयोग किए जाते हैं।
- Compilers में Expression Tree का use expressions evaluate करने के लिए किया जाता है।
- Networking में Routing Tables को tree form में store किया जाता है।
- HTML / XML Document Object Model (DOM) को represent करने के लिए tree structure उपयोग किया जाता है।
- Operating System processes को manage करने के लिए process tree बनाया जाता है।
- Autocomplete और spell-checking के लिए Trie (Prefix Tree) का उपयोग किया जाता है।
- File compression algorithms (Huffman Tree) data को efficiently encode करने के लिए tree उपयोग करते हैं।
- Game development में Minimax Tree decisions और best move prediction के लिए उपयोग होता है।
Advantages (लाभ)
1. Easy to Organize Data in a Hierarchical Structure
- Tree data को parent – child relationship में arrange करता है, जिससे Large और complex data को भी आसानी से manage किया जा सकता है।
- Example : Windows / Linux का File Explorer → Folder के अंदर sub-folders, फिर files।
2. Faster Searching
- Balanced trees जैसे – AVL Tree, Red-Black Tree, B-Tree में search का time complexity सिर्फ O(log n) होता है।
- इससे बड़े dataset में भी fast searching मिलती है।
3. Efficient Insertion & Deletion
- Linked representation वाले trees में node को जोड़ना (insert) और हटाना (delete) आसान और efficient होता है, क्योंकि यह dynamic memory का उपयोग करते हैं।
4. Traversal methods allow access to data in different ways
- Tree में कई traversal techniques होती हैं :
- Inorder
- Preorder
- Postorder
- Level Order
- इनकी मदद से expression evaluation, sorting, searching आदि tasks आसानी से होते हैं।
5. Data can be maintained in a sorted form
- Binary Search Tree (BST) data को इस तरह store करता है कि left → smaller , right → larger।
- इससे ordered data आसानी से handle होता है।
limitations (सीमाएँ)
Tree useful है, लेकिन इसकी कुछ limitations भी हैं :
1. Implementation is Complex
- Complex trees (AVL, Red-Black Tree) में balancing rules होते हैं, जो implementation को कठिन बनाते हैं।
- Beginners को अक्सर pointer handling मुश्किल लगता है।
2. Extra Memory Required
- हर node के साथ child pointers भी store होते हैं, जैसे :
- Binary Tree → 2 pointers
- General Tree → multiple pointers
- इससे memory usage बढ़ जाता है।
3. Unbalanced Trees Decrease Performance
- यदि tree unbalanced हो जाए (जैसे skewed BST), तो search/insertion/deletion की time complexity O(n) हो जाती है।
- यह linked list जैसा behave करने लगता है।
4. Traversal Time Compulsory O(n)
- हर node को एक बार visit करना ही पड़ता है (DFS/BFS),
- इसलिए worst case में traversal cost हमेशा O(n) ही रहती है।
4. Large Trees Are Difficult to Manage
- Tree जितना बड़ा होता जाता है, height भी बढ़ती जाती है,
- और deep levels में operations धीमे हो सकते हैं।
