| ऑपरेशन | औसत | सबसे बुरी स्थिति |
|---|
* परिशोधित: ऑपरेशनों की लंबी श्रृंखला पर औसत
डेटा संरचना विज़ुअलाइज़र
डेटा संरचना डेटा रखने का ऐसा तरीका है जिससे सबसे ज़्यादा पूछे जाने वाले सवालों का जवाब जल्दी मिल सके। स्टैक से लेकर रेड-ब्लैक ट्री तक, ग्यारह क्लासिक संरचनाओं में से एक चुनें, एक मान लिखें और कोई ऑपरेशन दबाएँ। हर चरण स्क्रीन पर दिखता है: किस नोड की तुलना हो रही है, कौन-सा लिंक बदल रहा है, ट्री क्यों घूमता है या कोई मान ऊपर क्यों उठता है, साथ में एक वाक्य जो बताता है कि क्या हो रहा है। टाइलें हर ऑपरेशन का काम गिनती हैं, और तालिका उसका रनिंग टाइम देती है। कोई संरचना चुनें, एक मान लिखें और कोई ऑपरेशन दबाएँ। हर ऑपरेशन चरण-दर-चरण चलता है: हाइलाइट किए गए नोड दिखाते हैं कि किसकी तुलना हो रही है, क्या खिसक रहा है या बदल रहा है, और चित्र के नीचे की पंक्ति बताती है कि क्या हो रहा है और क्यों। पीछे, चरण, चलाएँ और अंत से आप चरणों को फिर से देख सकते हैं। रैंडम भरें और खाली करें फिर से शुरू करते हैं, और पूर्ववत करें एक ऑपरेशन वापस लेता है। टाइलें आकार, ट्री की ऊँचाई, पिछले ऑपरेशन का काम (तुलनाएँ, प्रोब या पैरेंट लिंक पर चलना) और संरचना के लिए एक अहम संख्या दिखाती हैं; तालिका हर ऑपरेशन का रनिंग टाइम देती है।
यह कैसे काम करता है
- कोई संरचना चुनें, जैसे बाइनरी सर्च ट्री, हैश टेबल या ट्राई। यह रैंडम सामग्री के साथ शुरू होती है; रैंडम भरें और खाली करें फिर से शुरू करते हैं।
- एक मान लिखें और कोई ऑपरेशन दबाएँ: पुश, क्यू में डालें, डालें, हटाएँ, खोजें, कोई ट्रैवर्सल, union या find। चरण अपने-आप चलते हैं; पीछे, चरण, चलाएँ और अंत से उन्हें फिर देखें।
- चित्र के नीचे की पंक्ति में पढ़ें कि हर चरण क्या करता है, टाइलों में आकार, ऊँचाई और पिछले ऑपरेशन का काम देखें, और तालिका में रनिंग टाइम की तुलना करें।
लिस्ट, स्टैक और क्यू
सबसे सरल संरचनाएँ तत्वों को एक पंक्ति में रखती हैं। स्टैक केवल एक सिरे पर काम करता है, इसलिए आख़िर में रखा गया तत्व सबसे पहले निकलता है, जैसे प्लेटों का ढेर; क्यू पीछे जोड़ती है और आगे से निकालती है, जैसे काउंटर के सामने लगी कतार। यहाँ की क्यू एक सर्कुलर बफ़र में रहती है: आगे और पीछे के सिरे एक तय ऐरे में घूमते हैं और अंत के बाद फिर शुरुआत पर आ जाते हैं, और जब बफ़र भर जाता है तो तत्व दोगुने बड़े बफ़र में कॉपी किए जाते हैं। लिंक्ड लिस्ट नोडों को पॉइंटरों से जोड़ती है, इसलिए हेड पर डालना लगभग मुफ़्त है, पर टेल या कोई इंडेक्स खोजने के लिए लिंकों पर एक-एक करके चलना पड़ता है।
ट्री, हीप, हैश टेबल और समुच्चय
बाइनरी सर्च ट्री छोटे मान बाईं ओर और बड़े मान दाईं ओर रखता है, इसलिए जब तक ट्री घना रहता है, खोज हर चरण में उम्मीदवारों को आधा कर देती है। AVL और रेड-ब्लैक ट्री रोटेशन के ज़रिए यह सुनिश्चित करते हैं, जिन्हें आप देख सकते हैं और जिनके नाम उनकी स्थिति पर रखे गए हैं। हीप सबसे ऊपर केवल सबसे छोटा या सबसे बड़ा मान रखता है, और प्रायोरिटी क्यू को बस इतना ही चाहिए। हैश टेबल कुंजी से गणना किए गए बकेट पर सीधे कूदती है और उसे टकरावों से निपटना पड़ता है; ट्राई शब्दों के प्रीफ़िक्स साझा करता है; यूनियन-फ़ाइंड लगभग स्थिर समय में बता देता है कि दो तत्व एक ही समुच्चय में हैं या नहीं।
अक्सर पूछे जाने वाले प्रश्न
मुझे कौन-सी डेटा संरचना इस्तेमाल करनी चाहिए?
यह उन सवालों पर निर्भर करता है जो आप सबसे ज़्यादा पूछते हैं। जब तत्व आने के क्रम में या उल्टे क्रम में संभाले जाते हों तो स्टैक या क्यू; कोई कुंजी खोजने के लिए हैश टेबल; जब कुंजियाँ क्रम में या सबसे नज़दीकी कुंजी भी चाहिए तो AVL या रेड-ब्लैक जैसा संतुलित सर्च ट्री; जब हमेशा केवल सबसे छोटा या सबसे बड़ा तत्व चाहिए तो हीप; शब्दों और प्रीफ़िक्स के लिए ट्राई; आपस में मिलते समूहों पर नज़र रखने के लिए यूनियन-फ़ाइंड।
AVL ट्री और रेड-ब्लैक ट्री में क्या अंतर है?
दोनों बाइनरी सर्च ट्री को उथला रखते हैं, इसलिए हर खोज, इंसर्ट और डिलीट में log n के अनुपात में समय लगता है। AVL ट्री ज़्यादा सख़्ती से संतुलित होता है, हर नोड के दोनों ओर की ऊँचाई में अंतर एक से ज़्यादा नहीं होता, इसलिए खोज थोड़ी तेज़ होती है। रेड-ब्लैक ट्री ज़्यादा ढील देता है और बदलने पर कम रोटेशन माँगता है, इसीलिए कई स्टैंडर्ड लाइब्रेरी अपने क्रमबद्ध मैप और सेट के लिए इसका उपयोग करती हैं।
सबसे बुरी स्थिति में हैश टेबल धीमी क्यों हो सकती है?
अगर बहुत-सी कुंजियाँ एक ही बकेट में पहुँच जाएँ, तो खोज को उन्हें एक-एक करके जाँचना पड़ता है, बिल्कुल लिस्ट की तरह। अच्छा हैश फ़ंक्शन कुंजियों को बराबर फैलाता है और टेबल ज़्यादा भरने से पहले बड़ी हो जाती है, इसलिए खोज में औसतन स्थिर समय लगता है। 10 आकार की टेबल में एक ही अंक पर ख़त्म होने वाली संख्याएँ, या एक-दूसरे के एनाग्राम शब्द डालकर देखें कि टकराव कैसे जमा होते हैं।
AVL नोडों के पास की संख्याओं का क्या मतलब है?
ये बैलेंस फ़ैक्टर हैं: किसी नोड के बाएँ सबट्री की ऊँचाई में से दाएँ सबट्री की ऊँचाई घटाकर मिली संख्या। AVL ट्री में हर बैलेंस फ़ैक्टर −1, 0 या +1 होना चाहिए। जब कोई इंसर्ट या डिलीट किसी को +2 या −2 कर दे, तो ट्री उस नोड पर घूमता है; स्थिति (LL, RR, LR या RL) बताती है कि अतिरिक्त ऊँचाई किस ओर झुकी है और तय करती है कि एक रोटेशन चाहिए या दो।
क्या कुछ सर्वर पर भेजा जाता है?
नहीं। हर ऑपरेशन आपके ब्राउज़र में चलता है, और हर संरचना की सामग्री इसी ब्राउज़र के लोकल स्टोरेज में सहेजी जाती है।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ