1:17:46
Tree Data Structure Explained | Nitin Sir | RKDEMY | SEM-II Engineering
RKDEMY ENGINEERING
Overview
यह वीडियो डेटा स्ट्रक्चर में ट्री डेटा स्ट्रक्चर की अवधारणाओं को समझाने पर केंद्रित है, विशेष रूप से बाइनरी ट्री ट्रेवर्सल, हाफमैन कोड, एक्सप्रेशन ट्री और बाइनरी सर्च ट्री पर जोर दिया गया है। यह परीक्षा की तैयारी के लिए महत्वपूर्ण प्रश्नों और तकनीकों पर मार्गदर्शन प्रदान करता है, जिसमें एल्गोरिदम और सैद्धांतिक स्पष्टीकरण पर ध्यान केंद्रित किया गया है, खासकर उन छात्रों के लिए जो कोडिंग में कम अनुभवी हो सकते हैं।
How was this?
Save this permanently with flashcards, quizzes, and AI chat
Chapters
- बाइनरी ट्री ट्रेवर्सल ट्री के नोड्स को एक विशिष्ट क्रम में विज़िट करने की प्रक्रिया है।
- तीन मुख्य प्रकार हैं: प्रीऑर्डर (रूट, लेफ्ट, राइट), इनऑर्डर (लेफ्ट, रूट, राइट), और पोस्टऑर्डर (लेफ्ट, राइट, रूट)।
- परीक्षा में दो मुख्य प्रकार के प्रश्न पूछे जाते हैं: एक दिया हुआ ट्री और उसके ट्रेवर्सल ऑर्डर बताने हों, या दिए हुए ऑर्डर से ट्री बनाना हो।
ट्री के डेटा को व्यवस्थित और एक्सेस करने के लिए विभिन्न ट्रेवर्सल विधियों को समझना महत्वपूर्ण है, जो विभिन्न एल्गोरिदम के लिए आधार प्रदान करता है।
एक उदाहरण ट्री (A रूट, B लेफ्ट चाइल्ड, C राइट चाइल्ड; B के लेफ्ट में D, राइट में E; C के राइट में F) का उपयोग करके प्रीऑर्डर (A, B, D, E, C, F), इनऑर्डर (D, B, E, A, C, F), और पोस्टऑर्डर (D, E, B, F, C, A) की गणना की गई।
- जब प्रीऑर्डर और इनऑर्डर ट्रेवर्सल दिए जाते हैं, तो बाइनरी ट्री का निर्माण किया जा सकता है।
- प्रीऑर्डर का पहला एलिमेंट हमेशा रूट नोड होता है।
- इनऑर्डर में रूट नोड के बाईं ओर के सभी एलिमेंट लेफ्ट सबट्री के होते हैं और दाईं ओर के राइट सबट्री के होते हैं।
यह क्षमता यह समझने में मदद करती है कि कैसे डेटा के विभिन्न प्रतिनिधित्व (जैसे ट्रेवर्सल ऑर्डर) एक ही संरचना (ट्री) को परिभाषित कर सकते हैं।
दिए गए प्रीऑर्डर (A, B, D, H, I, E, C, F, J, G, K) और इनऑर्डर (H, D, I, B, E, A, J, F, C, G, K) से एक बाइनरी ट्री का निर्माण किया गया।
- हाफमैन कोडिंग डेटा कम्प्रेशन के लिए एक एल्गोरिथम है जो फ्रीक्वेंसी के आधार पर वेरिएबल-लेंथ कोड असाइन करता है।
- प्रक्रिया में कैरेक्टर फ्रीक्वेंसी से एक बाइनरी ट्री बनाना शामिल है, जिसमें कम फ्रीक्वेंसी वाले नोड्स को मर्ज किया जाता है।
- ट्री के किनारों (एज) को 0 (बाएं) और 1 (दाएं) असाइन करके प्रत्येक कैरेक्टर के लिए एक यूनिक कोड उत्पन्न किया जाता है।
हाफमैन कोडिंग डेटा को कुशलतापूर्वक कंप्रेस करने का एक तरीका प्रदान करती है, जिससे ट्रांसमिशन और स्टोरेज की आवश्यकताएं कम हो जाती हैं।
दिए गए कैरेक्टर और उनकी फ्रीक्वेंसी (जैसे, C:1, E:1, S:2, T:2, R:2, U:2) से एक हाफमैन ट्री बनाया गया और फिर प्रत्येक कैरेक्टर के लिए कोड (जैसे, C:001, E:000, S:01, T:100, R:101, U:11) उत्पन्न किए गए।
- एक्सप्रेशन ट्री एक बाइनरी ट्री है जो एक एक्सप्रेशन का प्रतिनिधित्व करता है, जहां ऑपरेंड लीफ नोड्स होते हैं और ऑपरेटर आंतरिक नोड्स होते हैं।
- ट्री बनाने के लिए, ऑपरेटर प्रेसिडेंस (प्राथमिकता) के आधार पर एक्सप्रेशन को ग्रुप किया जाता है।
- ग्रुपिंग के बाद, ऑपरेटरों को निकाला जाता है और ट्री संरचना बनाने के लिए उल्टा किया जाता है।
एक्सप्रेशन ट्री एक्सप्रेशन के मूल्यांकन और हेरफेर को सरल बनाते हैं, जिससे कम्पाइलर और इंटरप्रेटर डिजाइन में उनका उपयोग होता है।
एक्सप्रेशन `a + b * c` के लिए, पहले `b * c` को ग्रुप किया गया, फिर `a` और `(b * c)` को ग्रुप किया गया, और अंत में ऑपरेटरों को उल्टा करके ट्री बनाया गया।
- बाइनरी सर्च ट्री (BST) एक बाइनरी ट्री है जिसमें प्रत्येक नोड के लिए एक विशेष गुण होता है।
- गुण यह है कि नोड के लेफ्ट सबट्री में सभी मान रूट नोड से छोटे होते हैं, और राइट सबट्री में सभी मान रूट नोड से बड़े होते हैं।
- सभी नोड की वैल्यू डिस्टिंक्ट (अद्वितीय) होनी चाहिए।
BST डेटा को कुशलतापूर्वक खोजने, डालने और हटाने की अनुमति देता है, जो इसे सर्चिंग और सॉर्टिंग एल्गोरिदम के लिए एक महत्वपूर्ण डेटा संरचना बनाता है।
संख्याओं 30, 70, 20, 90, 60, 10, 80, 40 को एक-एक करके इंसर्ट करके एक बाइनरी सर्च ट्री का निर्माण किया गया।
Key takeaways
- डेटा स्ट्रक्चर में पास होने के लिए स्टैक, क्यू और ट्री सबसे महत्वपूर्ण हैं।
- बाइनरी ट्री ट्रेवर्सल (प्रीऑर्डर, इनऑर्डर, पोस्टऑर्डर) ट्री के डेटा को एक्सेस करने के लिए आवश्यक हैं।
- हाफमैन कोडिंग डेटा कम्प्रेशन के लिए एक प्रभावी तकनीक है जो फ्रीक्वेंसी-आधारित कोडिंग का उपयोग करती है।
- एक्सप्रेशन ट्री गणितीय एक्सप्रेशंस को समझने और प्रोसेस करने का एक विज़ुअल तरीका प्रदान करते हैं।
- बाइनरी सर्च ट्री कुशल डेटा सर्चिंग और मैनिपुलेशन के लिए एक मौलिक संरचना है।
- परीक्षा में अक्सर ट्री बनाने या दिए गए ट्री के ट्रेवर्सल की गणना करने वाले प्रश्न आते हैं।
- एल्गोरिदम और सैद्धांतिक समझ कोडिंग से अधिक महत्वपूर्ण हो सकती है, खासकर यदि कोडिंग स्किल कमजोर हो।
Key terms
Binary TreeTraversal (Preorder, Inorder, Postorder)Root NodeLeft SubtreeRight SubtreeHuffman CodingFrequencyExpression TreeOperator PrecedenceBinary Search Tree (BST)NodeAlgorithm
Test your understanding
- बाइनरी ट्री में प्रीऑर्डर, इनऑर्डर और पोस्टऑर्डर ट्रेवर्सल के बीच मुख्य अंतर क्या हैं?
- हाफमैन कोडिंग का उपयोग करके डेटा को कैसे कंप्रेस किया जाता है और इसके लिए ट्री निर्माण प्रक्रिया क्या है?
- एक दिए गए एक्सप्रेशन से एक्सप्रेशन ट्री कैसे बनाया जाता है, और इसमें ऑपरेटर प्रेसिडेंस की क्या भूमिका है?
- बाइनरी सर्च ट्री की मुख्य प्रॉपर्टीज क्या हैं और यह सामान्य बाइनरी ट्री से कैसे भिन्न है?
- यदि आपको एक प्रीऑर्डर और इनऑर्डर ट्रेवर्सल दिया जाए, तो आप बाइनरी ट्री का निर्माण कैसे करेंगे?