Tree Data Structure क्या है?
Tree एक Non-linear Data Structure है, जिसमें Data को Nodes के रूप में store किया जाता है। हर Tree में एक Root Node होती है और बाकी सभी Nodes को उस Root से जोड़ा जाता है।
मुख्य शब्दावली (Terminology of Tree) :
- Root Node : सबसे ऊपर की Node (मूल)।
- Parent Node : वह Node जिसके नीचे कोई Child Node जुड़ी हो।
- Child Node : Parent Node के नीचे की Node।
- Leaf Node : जिसके नीचे कोई Node न हो।
- Edge : दो Nodes को जोड़ने वाली line।
- Depth/Height : Tree की गहराई या ऊँचाई।
उदाहरण :
जैसे आप IRCTC की वेबसाइट पर Train Booking करते हैं — Root Node हो सकती है, Home Page, और उसके Child Nodes हो सकते हैं Login, Search Train, My Booking आदि।
Tree के प्रकार (Types of Trees)
1. Binary Tree
Binary Tree में हर Node के अधिकतम दो Child Nodes हो सकते हैं — एक Left और एक Right।
उदाहरण :
जैसे Flipkart या Amazon की product search में category filter — “Electronics” → “Mobile” → “Smartphone” → “Android” → “Samsung”।
Applications :
- Expression Evaluation (Compiler में)
- Decision-making processes
- Searching और Sorting Algorithms में
- Data Compression (जैसे Huffman Coding)
Features :
- Simple structure
- Easy traversal (Inorder, Preorder, Postorder)
- Used as a base for complex trees like BST, AVL
2. Binary Search Tree (BST)
Binary Search Tree एक ऐसा Binary Tree है, जिसमें Left Subtree के सभी Nodes की value Root से छोटी होती है, और Right Subtree की value Root से बड़ी होती है।
उदाहरण :
मान लीजिए आपके पास IRCTC या Paytm की Transaction History है — आप किसी particular date का record खोज रहे हैं। BST के जरिए यह बहुत तेज़ी से किया जा सकता है क्योंकि यह Data को sorted रूप में रखता है।
Applications :
- Searching और Sorting
- Map और Set implementation (C++ STL)
- Database indexing
- Symbol Table (Compiler में)
Advantages :
- Fast searching (O(log n))
- Memory efficient
- Easy to maintain sorted order
3. AVL Tree (Self Balancing Binary Search Tree)
AVL Tree एक Self-Balancing BST है। इसमें किसी भी Node के Left और Right Subtree की Height का अंतर अधिकतम 1 होता है।
उदाहरण :
किसी Bank Database में करोड़ों Transactions हैं। अगर Tree असंतुलित हो जाए, तो search करने में समय बढ़ जाएगा। AVL Tree इस समस्या को दूर करता है।
Applications :
- Database indexing systems
- Memory management
- Real-time processing systems
Advantages :
- Fast search, insertion, deletion
- Always balanced → better performance
4. Red-Black Tree
Red-Black Tree भी एक Self-Balancing BST है, लेकिन AVL से थोड़ा कम strict balancing रखता है। हर Node या तो Red होती है या Black।
Applications :
- Linux Kernel (Process Scheduling)
- Java TreeMap और TreeSet
- C++ STL (Map, Multimap)
- Compiler और OS Design में
Features :
- Balanced height
- Faster insertion and deletion than AVL
- Used where frequent modifications occur
5. B - Tree
B-Tree एक multiway search tree है, जो बड़े amount में Data को manage करने के लिए बनाया गया है। इसका उपयोग Hard Disk या Database में होता है।
उदाहरण :
जैसे IRCTC की Ticket Database में करोड़ों records store हैं। अगर search या update करना हो, तो B-Tree बहुत effective होता है क्योंकि यह Disk Read operations को minimize करता है।
Applications :
- Database indexing (MySQL, Oracle, PostgreSQL)
- File Systems (NTFS, HFS)
- Large-scale search engines
6. B+ Tree
B+ Tree, B-Tree का advanced version है, जिसमें सभी Data leaves में store होते हैं, और Internal Nodes केवल keys रखते हैं।
Applications :
- Database और File Systems (जैसे Oracle, MySQL)
- Range Queries (WHERE age > 25 AND < 40)
- Disk-based systems
7. Trie (Prefix Tree)
Trie का उपयोग String Searching में किया जाता है। इसमें हर Node एक Character को represent करती है।
उदाहरण :
Google Search Autocomplete में जब आप “Ind” टाइप करते हैं, तो यह instantly “India”, “Indian Railways”, “Indigo Airlines” सुझाता है — यह Trie से संभव होता है।
Applications :
- Spell Checkers
- Auto Suggestion tools
- IP Routing
- Search Engines
8. Heap Tree
Heap Tree एक Complete Binary Tree है, जो Priority Queue को implement करने में काम आता है। इसमें Parent Node हमेशा अपने Child से बड़ा या छोटा होता है (Max Heap या Min Heap)।
Applications :
- Dijkstra’s Algorithm (Shortest Path)
- Job Scheduling
- CPU task management
- Heap Sort Algorithm
Comparison of Various Types of Tree
Tree Type | Structure Type | Balancing | Applications | Advantage | Example |
Binary Tree | Simple | No | Basic storage | Easy implementation | Expression Tree |
BST | Ordered | No | Searching/Sorting | Fast Lookup | Student Records |
AVL Tree | Balanced BST | Yes | Database Indexing | High performance | Banking Systems |
Red-Black Tree | Balanced BST | Partial | OS, Compiler | Fast update | Linux Kernel |
B-Tree | Multiway | Yes | Databases | Efficient Disk Access | MySQL |
B+ Tree | Multiway | Yes | Range Queries | Sequential Access | Oracle |
Trie | String-based | Yes | Searching words | Fast lookup | Google Search |
Heap | Binary | Yes | Priority Queue | Efficient sorting | CPU Scheduling |
Tree Traversal Methods
Tree traversal का मतलब है — हर Node को किसी specific order में visit करना।
Types of Traversal :
- Inorder (Left → Root → Right) : Inorder traversal में सबसे पहले Left Subtree, फिर Root Node, और अंत में Right Subtree को visit किया जाता है।
Use : Binary Search Tree में इसका उपयोग sorted data प्राप्त करने के लिए किया जाता है।Example : Sorted Data प्राप्त करने के लिए।
- Preorder (Root → Left → Right) : Preorder traversal में traversal की शुरुआत Root Node से होती है, फिर Left Subtree और अंत में Right Subtree को visit किया जाता है।
Use : इसका उपयोग किसी tree की copy बनाने, tree को serialize करने और prefix notation expressions बनाने के लिए किया जाता है।
Example : Expression Tree Copy करने में। - Postorder (Left → Right → Root) : Postorder traversal में पहले Left Subtree, फिर Right Subtree, और सबसे अंत में Root Node को visit किया जाता है।
Use : Expression Tree को evaluate करने, यानी postfix expression का result निकालने में इसका प्रयोग होता है।
Example : Expression Evaluation में। - Level Order Traversal : Level order traversal में tree के nodes को level by level left से right दिशा में visit किया जाता है। यह traversal queue का उपयोग करके किया जाता है।
Use : BFS algorithm में, shortest path problems में, और tree के structure को level-wise print करने में उपयोग होता है।
Example : BFS Algorithm में उपयोग होता है।
Applications
- Artificial Intelligence :
Artificial Intelligence में trees का उपयोग decision-making problems को represent करने के लिए किया जाता है। Decision Trees और Game Trees (जैसे Chess, Tic-Tac-Toe) AI को best possible move चुनने, planning करने और logical decisions लेने में मदद करते हैं।
Ex. Decision Tree Learning, Game Tree (Chess, Tic-Tac-Toe) - Database Systems :
Database Systems में B-Tree और B+ Tree जैसी tree structures indexing के लिए उपयोग होती हैं, जिससे databases में data को बहुत तेज़ी से search, insert और retrieve किया जा सकता है। ये balanced trees बड़े data को efficiently manage करते हैं।
Ex. B-Tree, B+ Tree indexing - Compilers :
Compilers में program की structure को समझने और analyze करने के लिए Syntax Tree और Parse Tree का उपयोग किया जाता है। ये trees code के grammar, expressions और statements को hierarchical रूप में represent करते हैं।
Ex. Syntax Tree, Parse Tree - Networking :
Networking में trees का उपयोग routing tables, hierarchical addressing और network path selection को manage करने के लिए किया जाता है। इससे data packets के लिए efficient और shortest path निर्धारित होता है।
Ex. Routing Table representation - Operating Systems :
Operating Systems में processes और threads को manage करने के लिए process scheduling trees या hierarchical process trees का उपयोग किया जाता है। ये trees parent-child relationships और scheduling priorities को दर्शाते हैं।
Ex. Process Scheduling Trees - Machine Learning :
Machine Learning में decision-making और classification problems को solve करने के लिए Decision Trees, Classification Trees, और Random Forests का उपयोग किया जाता है। ये tree structures data को conditions के आधार पर split करके predictions बनाते हैं।
Ex. Random Forests, Decision Trees, Classification Trees
Real-Life Examples of Tree Applications
- IRCTC Booking System :
Railway Data Tree Structure में store होता है ताकि train searching तेज़ हो सके। - Google Search Engine :
Trie और B+ Tree का उपयोग Autocomplete और Indexing के लिए होता है। - Flipkart / Amazon :
Product Categories और Filters Tree की तरह structured होते हैं। - ISRO Satellite Control Systems :
Decision Trees का उपयोग launch sequence और risk analysis के लिए होता है। - Banking Systems :
AVL या Red-Black Trees का उपयोग transaction indexing में किया जाता है।
