Height Balanced Tree in Hindi | हाइट बैलेंस्ड ट्री क्या है?
हाइट बैलेंस्ड ट्री क्या है? (Height Balanced Tree in Hindi)
हाइट बैलेंस्ड ट्री (Height Balanced Tree) एक बाइनरी ट्री (Binary Tree) है, जिसमें बाएं और दाएं सब-ट्री की ऊंचाई (Height) में अंतर 1 से अधिक नहीं होता। यह सुनिश्चित करता है कि ट्री हमेशा संतुलित (Balanced) रहे और संचालन (Operations) तेज़ी से किए जा सकें।
हाइट बैलेंस्ड ट्री के नियम (Rules of Height Balanced Tree)
- ट्री की ऊंचाई न्यूनतम होनी चाहिए।
- हर नोड के बाएं और दाएं सब-ट्री की ऊंचाई का अंतर 1 या उससे कम होना चाहिए।
- सभी ऑपरेशंस जैसे इन्सर्शन (Insertion), डिलीशन (Deletion) और सर्च (Search) को लॉगेरिथमिक समय में पूरा किया जाना चाहिए।
हाइट बैलेंस्ड ट्री के प्रकार (Types of Height Balanced Tree)
प्रकार | विवरण |
---|---|
AVL ट्री (AVL Tree) | बाइनरी ट्री जिसमें हर नोड का बैलेंस फैक्टर -1, 0 या 1 होता है। |
रेड-ब्लैक ट्री (Red-Black Tree) | स्वयं-संतुलन (Self-Balancing) बाइनरी ट्री जिसमें प्रत्येक नोड को लाल या काला रंग दिया जाता है। |
B-ट्री (B-Tree) | मल्टी-वे सर्च ट्री जिसका उपयोग डेटाबेस और फाइल सिस्टम में किया जाता है। |
Splay ट्री (Splay Tree) | स्वयं-संगठित (Self-Organizing) बाइनरी ट्री जो हाल ही में एक्सेस किए गए नोड्स को रूट के करीब ले आता है। |
हाइट बैलेंस्ड ट्री में बैलेंस फैक्टर (Balance Factor in Height Balanced Tree)
बैलेंस फैक्टर को निम्नलिखित सूत्र से गणना किया जाता है:
Balance Factor = Height(Left Subtree) - Height(Right Subtree)
बैलेंस फैक्टर की संभावित मान:
- -1: दायां सब-ट्री लंबा है।
- 0: ट्री संतुलित है।
- 1: बायां सब-ट्री लंबा है।
- |Balance Factor| > 1: ट्री असंतुलित (Unbalanced) है और इसे संतुलित करने की आवश्यकता है।
हाइट बैलेंस्ड ट्री की प्रक्रिया (Operations in Height Balanced Tree)
1. प्रत्येक नोड का बैलेंस फैक्टर निर्धारित करें। 2. यदि बैलेंस फैक्टर |1| से अधिक है, तो रोटेशन लागू करें। 3. निम्नलिखित चार प्रकार की रोटेशन का उपयोग किया जाता है: a. Left Rotation (LL Rotation) b. Right Rotation (RR Rotation) c. Left-Right Rotation (LR Rotation) d. Right-Left Rotation (RL Rotation) 4. नए नोड के लिए पुनः बैलेंस फैक्टर की गणना करें।
हाइट बैलेंस्ड ट्री का छद्मकोड (Pseudocode of Height Balanced Tree)
function insert(node, key): if node is NULL: return new Node(key) if key < node.key: node.left = insert(node.left, key) else: node.right = insert(node.right, key) update balance factor and height if balance factor > 1 and key < node.left.key: return rightRotate(node) if balance factor < -1 and key > node.right.key: return leftRotate(node) if balance factor > 1 and key > node.left.key: node.left = leftRotate(node.left) return rightRotate(node) if balance factor < -1 and key < node.right.key: node.right = rightRotate(node.right) return leftRotate(node) return node
हाइट बैलेंस्ड ट्री का उदाहरण (Example of Height Balanced Tree)
माना कि हम निम्नलिखित संख्याओं को एक खाली AVL ट्री में डालते हैं:
- Insertion Sequence: 10, 20, 30, 40, 50, 25
बैलेंस फैक्टर की गणना करने के बाद, LL रोटेशन और LR रोटेशन का उपयोग करके हमें संतुलित ट्री प्राप्त होता है।
हाइट बैलेंस्ड ट्री बनाम अनबैलेंस्ड ट्री (Balanced Tree vs Unbalanced Tree)
विशेषता | हाइट बैलेंस्ड ट्री | अनबैलेंस्ड ट्री |
---|---|---|
खोज समय (Search Time) | O(log n) | O(n) (Worst Case) |
इन्सर्शन / डिलीशन (Insertion/Deletion) | तेज़ (Fast) | धीमा (Slow) |
स्टोरेज (Storage) | संगठित (Organized) | अव्यवस्थित (Unorganized) |
हाइट बैलेंस्ड ट्री के अनुप्रयोग (Applications of Height Balanced Tree)
- डेटाबेस इंडेक्सिंग (Database Indexing) – B-ट्री का उपयोग।
- सर्च इंजन ऑप्टिमाइज़ेशन (Search Engine Optimization) – AVL ट्री।
- नेटवर्क रूटिंग टेबल (Network Routing Tables)।
- ऑपरेटिंग सिस्टम में प्रोसेस शेड्यूलिंग (Process Scheduling)।
निष्कर्ष
हाइट बैलेंस्ड ट्री एक महत्वपूर्ण डेटा संरचना है, जिसका उपयोग तेज़ और कुशल सर्च, इन्सर्शन और डिलीशन ऑपरेशंस के लिए किया जाता है। इसका उपयोग विभिन्न क्षेत्रों जैसे कि डेटाबेस, नेटवर्किंग और ऑपरेटिंग सिस्टम में किया जाता है।
Related Post
- एल्गोरिथम क्या है? (Algorithms in Hindi) | परिभाषा, प्रकार और महत्व
- Designing Algorithm in ADA | एल्गोरिथम डिज़ाइन की प्रक्रिया और सिद्धांत
- एल्गोरिथम एनालिसिस क्या है? (Algorithm Analysis in Hindi) | परिभाषा, प्रकार और महत्व
- Asymptotic Notation in Hindi | एसिम्प्टोटिक नोटेशन क्या है?
- Divide and Conquer Technique in Hindi | डिवाइड एंड कॉन्कर तकनीक क्या है?
- Binary Search Algorithm in Hindi | बाइनरी सर्च एल्गोरिदम क्या है?
- Merge Sort Algorithm in Hindi | मर्ज सॉर्ट एल्गोरिदम क्या है?
- Quick Sort Algorithm in Hindi | क्विक सॉर्ट एल्गोरिदम क्या है?
- Strassen's Matrix Multiplication Algorithm in Hindi | स्ट्रासेन का मैट्रिक्स गुणा एल्गोरिदम
- Greedy Algorithm in Hindi | ग्रीडी एल्गोरिदम क्या है?
- Optimal Merge Pattern in Hindi | ऑप्टिमल मर्ज पैटर्न क्या है?
- Huffman Coding in Hindi | हफ्मन कोडिंग क्या है?
- Minimum Spanning Tree in Hindi | मिनिमम स्पैनिंग ट्री क्या है?
- Knapsack Problem in Hindi | नैपसैक समस्या क्या है?
- Job Sequencing with Deadlines in Hindi | जॉब सीक्वेंसिंग विथ डेडलाइन्स क्या है?
- Single Source Shortest Path Algorithm in Hindi | सिंगल सोर्स शॉर्टेस्ट पाथ एल्गोरिदम क्या है?
- Dynamic Programming in Hindi | डायनेमिक प्रोग्रामिंग क्या है?
- 0/1 Knapsack Problem using Dynamic Programming in Hindi | 0/1 नैपसैक समस्या डायनेमिक प्रोग्रामिंग द्वारा
- Multistage Graph in Hindi | मल्टीस्टेज ग्राफ क्या है?
- Reliability Design in Hindi | विश्वसनीयता डिज़ाइन क्या है?
- Floyd Warshall Algorithm in Hindi | फ्लॉयड वार्शल एल्गोरिदम क्या है?
- 8 Queen’s Problem in Hindi | 8 क्वीन्स समस्या क्या है?
- Hamiltonian Cycle in Hindi | हैमिल्टोनियन साइकिल क्या है?
- Graph Coloring Problem in Hindi | ग्राफ कलरिंग समस्या क्या है?
- Branch and Bound Method in Hindi | ब्रांच एंड बाउंड विधि क्या है?
- Traveling Salesman Problem in Hindi | ट्रैवलिंग सेल्समैन समस्या क्या है?
- Lower Bound Theory in Hindi | लोअर बाउंड थ्योरी क्या है?
- Parallel Algorithm in Hindi | समानांतर एल्गोरिदम क्या है?
- Height Balanced Tree in Hindi | हाइट बैलेंस्ड ट्री क्या है?
- 2-3 Tree in Hindi | 2-3 ट्री क्या है?
- NP-Completeness in Hindi | एनपी-कम्प्लीटनेस क्या है?