यहां AVL ट्री क्लास का पूरा कार्यान्वयन है: उदाहरण class AVLTree { constructor() { // रूट एलिमेंट को नल से इनिशियलाइज़ करें। this.root = null; } getBalanceFactor(root) { return this.getHeight(root.left) - this.getHeight(root.right); } getHeight(root) {

ग्राफ वस्तुओं के एक समूह का चित्रात्मक प्रतिनिधित्व है जहां वस्तुओं के कुछ जोड़े लिंक द्वारा जुड़े होते हैं। परस्पर जुड़ी वस्तुओं को वर्टेक्स कहे जाने वाले बिंदुओं द्वारा दर्शाया जाता है, और वर्टेक्स को जोड़ने वाले लिंक को एज कहा जाता है। औपचारिक रूप से, ग्राफ सेट का एक जोड़ा (V, E) है, जहां V वर्ट

हम एक ग्राफ क्लास बनाएंगे जो वजन और डायरेक्टेड व अनडायरेक्टेड दोनों प्रकार को सपोर्ट करता है। इसे एडजेसेंसी लिस्ट का उपयोग करके लागू किया जाएगा। जैसे-जैसे हम अधिक एडवांस कॉन्सेप्ट्स की ओर बढ़ेंगे, ग्राफ की वजन और डायरेक्टेड प्रकृति दोनों काम आएंगी। एडजेसेंसी लिस्ट अलग-अलग लिस्ट का एक ऐरे A है। ऐरे

ग्राफ ट्रैवर्सल (जिसे ग्राफ सर्च भी कहा जाता है) ग्राफ में प्रत्येक वर्टेक्स को विजिट करने (चेक और/या अपडेट करने) की प्रक्रिया को संदर्भित करता है। ऐसे ट्रैवर्सल को वर्टेक्स के विजिट होने के क्रम द्वारा वर्गीकृत किया जाता है।

BFS चाइल्ड वर्टेक्स से पहले पड़ोसी वर्टेक्स को विजिट करता है, और सर्च प्रक्रिया में एक क्यू का उपयोग किया जाता है। BFS कैसे काम करता है: आसन्न अनविजिटेड वर्टेक्स को विजिट करें। इसे विजिटेड मार्क करें। इसे प्रदर्शित करें। इसे क्यू में डालें। यदि कोई आसन्न वर्टेक्स नहीं मिलता है, तो क्यू से पहले वर्

DFS सिबलिंग वर्टेक्स से पहले चाइल्ड वर्टेक्स को विजिट करता है; यानी, यह किसी विशेष पाथ की गहराई को उसकी चौड़ाई का पता लगाने से पहले ट्रैवर्स करता है। एल्गोरिदम को लागू करते समय आमतौर पर एक स्टैक (अक्सर रिकर्सन के माध्यम से प्रोग्राम का कॉल स्टैक) उपयोग किया जाता है। DFS ट्रैवर्सल कैसे काम करता है:

डायरेक्टेड ग्राफ का टोपोलॉजिकल सॉर्ट या टोपोलॉजिकल ऑर्डरिंग उसके वर्टेक्स का एक लीनियर ऑर्डरिंग है जैसे कि वर्टेक्स u से वर्टेक्स v तक के हर डायरेक्टेड एज UV के लिए, u ऑर्डरिंग में v से पहले आता है। यह केवल डायरेक्टेड ग्राफ में समझ में आता है। कई स्थान हैं जहां टोपोलॉजिकल सॉर्ट बहुत मायने रखता है।

ग्राफ थ्योरी में, शॉर्टेस्ट पाथ समस्या एक ग्राफ में दो वर्टेक्स (या नोड्स) के बीच एक पाथ खोजने की समस्या है जैसे कि इसके घटक एजेज के वजन का योग न्यूनतम हो। यहां हमें अपने add edge और add directed मेथड्स को संशोधित करने की आवश्यकता है ताकि एजेज को वजन जोड़ने की अनुमति मिल सके। आइए देखते हैं कि हम इस

डिज्क्स्ट्रा का एल्गोरिदम वेटेड ग्राफ में नोड्स के बीच सबसे छोटे पाथ खोजने का एक एल्गोरिदम है। हम नए addEdge और addDirectedEdge मेथड्स का उपयोग करके ग्राफ बनाते समय एजेज को वजन असाइन करेंगे। आइए देखते हैं कि यह एल्गोरिदम कैसे काम करता है: एक डिस्टेंस कलेक्शन बनाएं और सोर्स नोड को छोड़कर सभी वर्टेक

डिज्क्स्ट्रा का एल्गोरिदम एक नोड से अन्य सभी नोड्स तक के सबसे छोटे पाथ की दूरी/पाथ को खोजने के लिए उपयोग किया जाता है। ऐसे मामले होते हैं जहां हमें सभी नोड्स से अन्य सभी नोड्स तक के सबसे छोटे पाथ खोजने की आवश्यकता होती है। यहीं ऑल-पेयर्स शॉर्टेस्ट पाथ एल्गोरिदम काम आते हैं। सबसे अधिक उपयोग किया जान

ट्री ट्रैवर्सल ट्री डेटा संरचना में प्रत्येक नोड को विजिट करने की प्रक्रिया को संदर्भित करता है, ठीक एक बार। ऐसे ट्रैवर्सल को नोड्स के विजिट होने के क्रम द्वारा वर्गीकृत किया जाता है।

इस ट्रैवर्सल मेथड में, लेफ्ट सबट्री को पहले विजिट किया जाता है, फिर रूट और बाद में राइट सब-ट्री। हमें हमेशा याद रखना चाहिए कि प्रत्येक नोड स्वयं एक सबट्री का प्रतिनिधित्व कर सकता है। यदि बाइनरी ट्री को इन-ऑर्डर ट्रैवर्स किया जाता है, तो आउटपुट आरोही क्रम में सॉर्टेड की वैल्यूज़ उत्पन्न करेगा। हम A

इस ट्रैवर्सल मेथड में, रूट नोड को पहले विजिट किया जाता है, फिर लेफ्ट सबट्री और अंत में राइट सबट्री। हम A से शुरू करते हैं, और प्री-ऑर्डर ट्रैवर्सल का पालन करते हुए, हम पहले A को ही विजिट करते हैं और फिर इसके लेफ्ट सबट्री B पर जाते हैं। B को भी प्री-ऑर्डर में ट्रैवर्स किया जाता है। प्रक्रिया तब तक

इस ट्रैवर्सल मेथड में, रूट नोड को अंत में विजिट किया जाता है, इसलिए इसका नाम। पहले हम लेफ्ट सबट्री को ट्रैवर्स करते हैं, फिर राइट सबट्री को और अंत में रूट नोड को। हम A से शुरू करते हैं, और पोस्ट-ऑर्डर ट्रैवर्सल का पालन करते हुए, हम पहले लेफ्ट सबट्री B को विजिट करते हैं। B को भी पोस्ट-ऑर्डर में ट्र

ट्री से नोड हटाना दूर से देखने पर काफी जटिल लगता है। नोड हटाते समय 3 केस पर विचार करना होता है। ये निम्न फ़ंक्शन की टिप्पणी में उल्लिखित हैं। जैसा कि हम पहले करते रहे हैं, हम क्लास में एक मेथड और रिकर्सिव कॉल के लिए एक हेल्पर बनाएंगे। क्लास मेथड deleteNode(key) { // यदि नोड सफलतापूर्वक हटा दिया

यहां BinarySearchTree क्लास का पूरा कार्यान्वयन है: उदाहरण class BinarySearchTree { constructor() { // रूट एलिमेंट को नल से इनिशियलाइज़ करें। this.root = null; } insertIter(data) { let node = new this.Node(data); // जांचें कि ट्री खाली है या नहीं

AVL ट्री (आविष्कारकों एडेल्सन-वेल्स्की और लैंडिस के नाम पर) एक सेल्फ-बैलेंसिंग बाइनरी सर्च ट्री है। एक सेल्फ-बैलेंसिंग ट्री एक ऐसा ट्री है जो अपने सबट्रीज़ के भीतर कुछ रोटेशन करता है ताकि यह लेफ्ट और राइट दोनों तरफ से बैलेंस्ड हो सके। ये ट्रीज़ उन मामलों में विशेष रूप से सहायक होते हैं जहां इंसर्शन

AVL ट्री लेफ्ट और राइट सब-ट्रीज़ की ऊंचाई की जांच करता है और सुनिश्चित करता है कि अंतर 1 से अधिक न हो। इस अंतर को बैलेंस फैक्टर कहा जाता है। उदाहरण के लिए, निम्नलिखित ट्रीज़ में, पहला ट्री बैलेंस्ड है और अगले दो ट्री बैलेंस्ड नहीं हैं: दूसरे ट्री में, C के लेफ्ट सबट्री की ऊंचाई 2 है और राइट सबट्री

स्वयं को बैलेंस करने के लिए, एक AVL ट्री निम्नलिखित चार प्रकार के रोटेशन कर सकता है: लेफ्ट रोटेशन राइट रोटेशन लेफ्ट-राइट रोटेशन राइट-लेफ्ट रोटेशन पहले दो रोटेशन सिंगल रोटेशन हैं और अगले दो डबल रोटेशन हैं। एक अनबैलेंस्ड ट्री होने के लिए, हमें कम से कम ऊंचाई 2 के ट्री की आवश्यकता होती है। इस सरल ट्

हम सीख सकते हैं कि AVL ट्री में नोड कैसे इंसर्ट करते हैं। AVL ट्री में इंसर्शन BST के समान ही होते हैं, हमें बस इंसर्ट के दौरान ट्री को बैलेंस करने नामक एक अतिरिक्त चरण करने की आवश्यकता होती है जब भी हम ट्री में नीचे जाते हैं। इसके लिए बैलेंस फैक्टर की गणना करने की आवश्यकता होती है जिसे हम पहले ही