Computer Anudeshak Bharti | DSA Marathon Class | Complete Revision | Deepraj Sir

Pathshala IT Academy

6 chapters7 takeaways16 key terms6 questions

Overview

यह वीडियो बाइनरी सर्च ट्री (BST), डेप्थ-फर्स्ट सर्च (DFS), और ब्रेथ-फर्स्ट सर्च (BFS) जैसे डेटा स्ट्रक्चर्स और एल्गोरिदम पर केंद्रित है। इसमें इन अवधारणाओं की प्रॉपर्टीज, ट्रेवर्सिंग मेथड्स (जैसे इन-ऑर्डर, प्री-ऑर्डर, पोस्ट-ऑर्डर), और उनके उपयोग के बारे में विस्तार से बताया गया है। वीडियो में हिप्स, सॉर्टिंग, और एक्सप्रेशन ट्री जैसे संबंधित विषयों को भी कवर किया गया है, जिसमें विभिन्न प्रकार के प्रश्नों को हल करने के तरीके और उनकी जटिलताओं पर जोर दिया गया है। यह मुख्य रूप से कंप्यूटर विज्ञान के छात्रों के लिए एक रिवीजन क्लास के रूप में कार्य करता है, जिसमें परीक्षा-उन्मुख प्रश्नों पर विशेष ध्यान दिया गया है।

How was this?

Save this permanently with flashcards, quizzes, and AI chat

Chapters

BST एक ट्री डेटा स्ट्रक्चर है जिसमें प्रत्येक नोड के लिए एक प्रॉपर्टी होती है: लेफ्ट चाइल्ड हमेशा नोड से छोटा होता है और राइट चाइल्ड हमेशा नोड से बड़ा होता है।
ट्री ग्राफ का एक सबसेट है, और ट्री ट्रेवर्सिंग ग्राफ ट्रेवर्सिंग के समान ही है क्योंकि ट्री एक साइक्लिक ग्राफ है।
DFS (डेप्थ-फर्स्ट सर्च) और BFS (ब्रेथ-फर्स्ट सर्च) ग्राफ और ट्री ट्रेवर्सिंग के दो मुख्य तरीके हैं।
DFS के लिए स्टैक डेटा स्ट्रक्चर का उपयोग किया जाता है, जबकि BFS के लिए क्यू (Queue) डेटा स्ट्रक्चर का उपयोग किया जाता है।

BST डेटा को व्यवस्थित करने का एक कुशल तरीका प्रदान करता है, जिससे सर्चिंग और इंसर्शन जैसी ऑपरेशन्स तेज हो जाती हैं। DFS और BFS विभिन्न प्रकार की समस्याओं को हल करने के लिए मौलिक एल्गोरिदम हैं।

BST की प्रॉपर्टी का उदाहरण: यदि रूट 10 है, तो लेफ्ट चाइल्ड 5 (10 से छोटा) और राइट चाइल्ड 15 (10 से बड़ा) हो सकता है।

DFS (डेप्थ-फर्स्ट सर्च) का मतलब है पहले गहराई में जाना, और इसके लिए स्टैक का उपयोग होता है।
BFS (ब्रेथ-फर्स्ट सर्च) को लेवल-ऑर्डर ट्रेवर्सल भी कहा जाता है, और इसके लिए क्यू का उपयोग होता है।
BFS लेवल-बाय-लेवल चलता है, यानी एक लेवल के सभी नोड्स को विजिट करने के बाद ही अगले लेवल पर जाता है।
BFS का सबसे ज्यादा उपयोग हिप (Heap) डेटा स्ट्रक्चर में होता है, खासकर हिप सॉर्ट में।

DFS और BFS यह निर्धारित करते हैं कि ट्री या ग्राफ के नोड्स को किस क्रम में विजिट किया जाएगा, जो विभिन्न एल्गोरिदम के प्रदर्शन और व्यवहार को प्रभावित करता है।

एक ट्री में BFS: 10, फिर उसके चाइल्ड 8 और 12, फिर उनके चाइल्ड्स आदि को लेवल-बाय-लेवल विजिट करना।

हिप एक विशेष प्रकार का ट्री-आधारित डेटा स्ट्रक्चर है।
मैक्स-हिप में, पैरेंट नोड हमेशा अपने चाइल्ड नोड्स से बड़ा होता है।
मिन-हिप में, पैरेंट नोड हमेशा अपने चाइल्ड नोड्स से छोटा होता है।
BFS का उपयोग हिप में सबसे ज्यादा होता है, खासकर हिप सॉर्ट एल्गोरिथम में।

हिप डेटा स्ट्रक्चर प्रायोरिटी क्यू को कुशलतापूर्वक लागू करने के लिए महत्वपूर्ण है, जिसका उपयोग शेड्यूलिंग और सॉर्टिंग जैसे कार्यों में होता है।

मैक्स-हिप का उदाहरण: यदि रूट 10 है, तो उसके चाइल्ड 8 और 5 हो सकते हैं, जहाँ 10 दोनों से बड़ा है।

प्री-ऑर्डर ट्रेवर्सल: रूट -> लेफ्ट -> राइट।
इन-ऑर्डर ट्रेवर्सल: लेफ्ट -> रूट -> राइट। इन-ऑर्डर हमेशा सॉर्टेड (बढ़ते क्रम में) आउटपुट देता है।
पोस्ट-ऑर्डर ट्रेवर्सल: लेफ्ट -> राइट -> रूट।
इन-ऑर्डर ट्रेवर्सल का उपयोग करके BST को सॉर्टेड लिस्ट में बदला जा सकता है।

ये ट्रेवर्सल मेथड्स ट्री के नोड्स को एक विशिष्ट क्रम में एक्सेस करने की अनुमति देते हैं, जो ट्री को प्रिंट करने, कॉपी करने या उसका विश्लेषण करने के लिए आवश्यक है।

एक BST के लिए प्री-ऑर्डर 30, 10, 5, 15, 40, 35, 45 हो सकता है, जबकि इन-ऑर्डर 5, 10, 15, 30, 35, 40, 45 होगा।

प्री-ऑर्डर और पोस्ट-ऑर्डर सीक्वेंस से BST बनाया जा सकता है, लेकिन इसके लिए इन-ऑर्डर सीक्वेंस की भी आवश्यकता होती है।
प्री-ऑर्डर से नोड (रूट) पहले मिलता है, और इन-ऑर्डर से लेफ्ट और राइट सबट्री का विभाजन पता चलता है।
किसी दिए गए सीक्वेंस की वैधता जांचने के लिए, BST प्रॉपर्टीज (जैसे लेफ्ट < रूट < राइट) का उपयोग करके उसे काटा (split) जा सकता है।
पोस्ट-ऑर्डर में, रूट सबसे अंत में मिलता है।

यह समझना कि विभिन्न ट्रेवर्सल सीक्वेंस से BST कैसे बनाया जा सकता है, रिकंस्ट्रक्शन और वैलिडेशन समस्याओं को हल करने के लिए महत्वपूर्ण है।

प्री-ऑर्डर (30, 10, 5, 15, 40, 35, 45) और इन-ऑर्डर (5, 10, 15, 30, 35, 40, 45) से BST का पुनर्निर्माण करना।

AVL ट्री एक सेल्फ-बैलेंसिंग BST है जिसमें बैलेंस फैक्टर (लेफ्ट सबट्री की ऊंचाई - राइट सबट्री की ऊंचाई) -1, 0, या 1 होता है।
यदि बैलेंस फैक्टर 1 से अधिक या -1 से कम हो जाता है, तो ट्री को बैलेंस करने की आवश्यकता होती है।
एक्सप्रेशन ट्री एक बाइनरी ट्री है जो गणितीय एक्सप्रेशन को दर्शाता है, जहाँ लीफ नोड्स ऑपरेंड होते हैं और इंटरनल नोड्स ऑपरेटर्स होते हैं।

AVL ट्री सर्चिंग ऑपरेशन्स की एफिशिएंसी सुनिश्चित करता है, जबकि एक्सप्रेशन ट्री एक्सप्रेशन का मूल्यांकन और मैनिपुलेशन करने में मदद करता है।

एक्सप्रेशन ट्री का उदाहरण: a + b * c के लिए, '*' नोड के नीचे 'b' और 'c' लीफ होंगे, और '*' नोड 'a' के साथ '+' नोड का चाइल्ड होगा।

Key takeaways

1BST डेटा को कुशलतापूर्वक स्टोर और सर्च करने के लिए एक मौलिक डेटा स्ट्रक्चर है।
2DFS और BFS ट्री और ग्राफ को ट्रेवर्स करने के लिए आवश्यक एल्गोरिदम हैं, जिनके लिए क्रमशः स्टैक और क्यू का उपयोग होता है।
3इन-ऑर्डर ट्रेवर्सल हमेशा BST के एलिमेंट्स को सॉर्टेड ऑर्डर में देता है।
4हिप डेटा स्ट्रक्चर (मैक्स-हिप और मिन-हिप) प्रायोरिटी क्यू को लागू करने के लिए महत्वपूर्ण हैं।
5AVL ट्री सेल्फ-बैलेंसिंग BST हैं जो सर्च टाइम को ऑप्टिमाइज़ करते हैं।
6एक्सप्रेशन ट्री गणितीय एक्सप्रेशंस को दर्शाने और उनका मूल्यांकन करने का एक तरीका है।
7किसी दिए गए ट्रेवर्सल सीक्वेंस से BST का पुनर्निर्माण करना एक सामान्य समस्या है।

Key terms

Binary Search Tree (BST)Depth-First Search (DFS)Breadth-First Search (BFS)StackQueueHeapMax-HeapMin-HeapIn-order TraversalPre-order TraversalPost-order TraversalAVL TreeExpression TreeBalance FactorLeaf NodeRoot Node

Test your understanding

1BST की मुख्य प्रॉपर्टी क्या है और यह डेटा को कैसे व्यवस्थित करती है?
2DFS और BFS में क्या अंतर है, और प्रत्येक के लिए कौन सा डेटा स्ट्रक्चर उपयोग किया जाता है?
3इन-ऑर्डर ट्रेवर्सल का उपयोग करके BST से सॉर्टेड लिस्ट कैसे प्राप्त की जा सकती है?
4मैक्स-हिप और मिन-हिप के बीच क्या अंतर है, और उनका उपयोग कहाँ होता है?
5एक AVL ट्री को बैलेंस करने की आवश्यकता कब पड़ती है, और बैलेंस फैक्टर क्या होता है?
6एक्सप्रेशन ट्री का उपयोग करके गणितीय एक्सप्रेशन का मूल्यांकन कैसे किया जाता है?