डेटा संरचनाएँ समझें

हर प्रोग्राम डेटा को कहीं रखता है, और वह उसे कैसे रखता है, इसी से तय होता है कि क्या तेज़ होगा और क्या धीमा। दस लाख नामों की सूची को नाम-दर-नाम देखा जा सकता है, या ऐसे सजाया जा सकता है कि बीस तुलनाओं में कोई भी नाम मिल जाए। डेटा संरचनाएँ ऐसी ही व्यवस्थाएँ हैं: मुट्ठी भर विचार, जिनमें से ज़्यादातर पर्सनल कंप्यूटर से भी पुराने हैं, और जो हर डेटाबेस, ऑपरेटिंग सिस्टम, ब्राउज़र और गेम के भीतर मौजूद हैं।

लाल-काले रंग वाला एक बाइनरी सर्च ट्री, डिब्बों का एक स्टैक, टकराने वाली कुंजियों की एक चेन के साथ हैश बकेटों की एक पंक्ति, और एक लिस्ट के नोडों को जोड़ते तीर
लाल-काले रंग वाला एक बाइनरी सर्च ट्री, डिब्बों का एक स्टैक, टकराने वाली कुंजियों की एक चेन के साथ हैश बकेटों की एक पंक्ति, और एक लिस्ट के नोडों को जोड़ते तीर

डेटा संरचना किस काम आती है

डेटा संरचना उन सवालों के हिसाब से चुनी जाती है जिनका उसे जवाब देना है। फ़ोन के कॉल लॉग को सबसे नई कॉल पहले चाहिए, प्रिंटर को सबसे पुराना काम पहले, शब्दकोश को एक लाख शब्दों में से एक का अर्थ, और रूट प्लानर को सबसे नज़दीकी अनदेखा चौराहा। हर संरचना कुछ ऑपरेशनों को तेज़ बनाती है और बदले में दूसरों को छोड़ देती है, और बिग O नोटेशन इसी सौदे का वर्णन करता है: O(1) का अर्थ है कि समय तत्वों की संख्या n के साथ नहीं बढ़ता, O(log n) कि n को दोगुना करने पर बस एक चरण बढ़ता है, और O(n) कि समय n के अनुपात में बढ़ता है।

स्टैक, क्यू और डेक

स्टैक एक ही सिरे पर जोड़ता और निकालता है: आख़िर में आया, पहले गया। अनडू इतिहास, बैक बटन और चलते प्रोग्राम की फ़ंक्शन कॉल स्टैक हैं। क्यू पीछे जोड़ती है और आगे से निकालती है: पहले आया, पहले गया, जैसे कीबोर्ड इनपुट या प्रिंट क्यू। डेक दोनों सिरों पर दोनों काम करने देता है। तीनों में हर ऑपरेशन स्थिर समय लेता है। क्यू को अक्सर सर्कुलर बफ़र में रखा जाता है, एक तय ऐरे जिसमें आगे और पीछे के सिरे आख़िरी स्लॉट के बाद फिर शुरुआत पर लौट आते हैं; भर जाने पर तत्व दोगुने बड़े ऐरे में कॉपी होते हैं। कॉपी करने में O(n) लगता है, पर यह इतना कम होता है कि हर ऑपरेशन औसतन फिर भी O(1) का पड़ता है, जिसे परिशोधित सीमा कहते हैं।

लिंक्ड लिस्ट

लिंक्ड लिस्ट हर मान को एक नोड में रखती है जिसमें अगले नोड का पॉइंटर होता है। इंसर्ट या डिलीट केवल एक-दो पॉइंटर बदलता है, कुछ भी खिसकाना नहीं पड़ता, पर दसवें नोड पर सीधे नहीं कूद सकते: हेड से लिंकों पर चलना पड़ता है। जो लिस्ट केवल अपना हेड जानती है, वह O(n) चरणों में टेल तक पहुँचती है; असली लिस्ट अक्सर एक टेल पॉइंटर भी रखती हैं, और डबली लिंक्ड लिस्ट पीछे का पॉइंटर भी, और इसी तरह ब्राउज़र का इतिहास या LRU कैश बनाया जाता है।

बाइनरी सर्च ट्री

बाइनरी सर्च ट्री हर नोड पर छोटे मान बाएँ सबट्री में और बड़े मान दाएँ में रखता है। खोज तुलना करके बाएँ या दाएँ जाती है, और इन-ऑर्डर ट्रैवर्सल मानों को क्रम में पढ़ता है। पत्ती हटाना बस उसे निकाल देना है, एक बच्चे वाले नोड की जगह वह बच्चा ले लेता है, और दो बच्चों वाले नोड की जगह उसका इन-ऑर्डर उत्तराधिकारी, यानी दाएँ सबट्री का सबसे छोटा मान। इन सबमें ट्री की ऊँचाई के अनुपात में समय लगता है: घने ट्री में लगभग log n, पर जब मान क्रम से आते हैं और ट्री बिगड़कर लिस्ट बन जाता है तो n।

AVL और रेड-ब्लैक ट्री

स्व-संतुलित ट्री हर बदलाव के बाद अपना आकार ठीक करते हैं। 1962 में एडेलसन-वेल्स्की और लैंडिस द्वारा बनाया गया AVL ट्री हर नोड के दोनों सबट्री की ऊँचाई का अंतर एक से ज़्यादा नहीं होने देता; जब किसी नोड का बैलेंस फ़ैक्टर ±2 हो जाता है, तो एक रोटेशन (LL और RR स्थितियाँ) या दो (LR और RL) संतुलन लौटा देते हैं। रेड-ब्लैक ट्री अपने नोडों को ऐसे रंगता है कि रूट काला हो, किसी लाल नोड का लाल बच्चा न हो और नीचे जाने वाला हर रास्ता बराबर काले नोडों से गुज़रे, जिससे सबसे लंबा रास्ता सबसे छोटे के दोगुने से ज़्यादा नहीं होता। यह रंग बदलकर और ज़्यादा से ज़्यादा कुछ रोटेशन से ख़ुद को ठीक करता है, और Java के TreeMap, C++ के std::map और Linux शेड्यूलर के भीतर यही ट्री है।

हीप और प्रायोरिटी क्यू

बाइनरी हीप एक पूर्ण बाइनरी ट्री है जो बिना किसी पॉइंटर के ऐरे में रखा जाता है: स्थिति i के बच्चे 2i + 1 और 2i + 2 पर होते हैं। मिन-हीप में हर पैरेंट अपने बच्चों से बड़ा नहीं होता, इसलिए सबसे छोटा मान हमेशा रूट पर होता है। नया मान अंत में रखा जाता है और बड़े पैरेंटों को पार करते हुए ऊपर उठता है; रूट निकालने पर आख़िरी मान ऊपर लाया जाता है और नीचे खिसकता है। दोनों में O(log n) लगता है, और पूरे ऐरे को O(n) में हीप बनाया जा सकता है। हीप Dijkstra के सबसे छोटे रास्तों, इवेंट सिमुलेशन और ऑपरेटिंग सिस्टम शेड्यूलरों की प्रायोरिटी क्यू चलाते हैं, और हीप सॉर्ट भी इन्हीं से बनता है।

हैश टेबल

हैश टेबल हैश फ़ंक्शन से कुंजी को ऐरे इंडेक्स में बदलती है और सीधे वहाँ जाती है। अलग-अलग कुंजियाँ एक ही इंडेक्स पर पहुँच सकती हैं: यही टकराव है। चेनिंग हर बकेट में एक छोटी लिस्ट रखती है; लीनियर प्रोबिंग जैसी ओपन एड्रेसिंग अगले स्लॉट आज़माती जाती है जब तक ख़ाली स्लॉट न मिल जाए, और कुंजी हटाते समय उसे एक टॉम्बस्टोन छोड़ना पड़ता है ताकि बाद की खोज प्रोबिंग जारी रखे। अच्छे हैश फ़ंक्शन और टेबल बढ़ाकर कम रखे गए लोड फ़ैक्टर (प्रति बकेट कुंजियाँ) के साथ इंसर्ट, खोज और डिलीट औसतन O(1) के होते हैं। कमज़ोर फ़ंक्शन, जैसे शब्द के अक्षर कोड जोड़ना, एनाग्राम को एक ही बकेट में भेज देता है। Python के dict, JavaScript ऑब्जेक्ट और डेटाबेस इंडेक्स के पीछे हैश टेबल ही हैं।

ट्राई और यूनियन-फ़ाइंड

ट्राई, यानी प्रीफ़िक्स ट्री, स्ट्रिंग को हर स्तर पर एक अक्षर के हिसाब से रखता है, इसलिए एक जैसी शुरुआत वाले शब्द एक रास्ता साझा करते हैं और एक नोड बताता है कि शब्द कहाँ ख़त्म होता है। L लंबाई का शब्द खोजने में L चरण लगते हैं, चाहे कितने भी शब्द रखे हों, और किसी प्रीफ़िक्स वाले सभी शब्द एक ही सबट्री में होते हैं; ऑटो-कम्प्लीट और स्पेल-चेकर ऐसे ही काम करते हैं। यूनियन-फ़ाइंड तत्वों को असंयुक्त समुच्चयों में रखता है, हर समुच्चय एक ट्री होता है जिसका रूट समुच्चय का नाम है। Find पैरेंट लिंकों पर रूट तक चलता है; union एक रूट को दूसरे के नीचे टाँग देता है। रैंक के अनुसार यूनियन और पाथ कम्प्रेशन के साथ, ऑपरेशनों की लंबी श्रृंखला में हर ऑपरेशन लगभग स्थिर समय लेता है, यानी व्युत्क्रम एकरमैन फ़ंक्शन α(n), जो किसी भी व्यावहारिक n के लिए 4 से ज़्यादा नहीं होता। न्यूनतम स्पैनिंग ट्री के लिए क्रुस्कल का एल्गोरिद्म इसी पर टिका है।

अक्सर पूछे जाने वाले प्रश्न

ऐरे और लिंक्ड लिस्ट में क्या अंतर है?

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

परिशोधित समय का क्या अर्थ है?

लंबी श्रृंखला में प्रति ऑपरेशन औसत लागत, भले ही कोई एक ऑपरेशन कभी-कभी महँगा हो। भरने पर दोगुना होने वाला सर्कुलर बफ़र कभी-कभी सभी n तत्व कॉपी करता है, पर जैसे-जैसे बफ़र बड़ा होता है कॉपी कम होती जाती हैं, इसलिए n जोड़ की कुल लागत O(n) होती है, यानी औसतन हर एक की O(1)।

क्या हीप और बाइनरी सर्च ट्री एक ही चीज़ हैं?

नहीं। बाइनरी सर्च ट्री हर बाएँ सबट्री को अपने नोड से पहले और हर दाएँ सबट्री को बाद में रखता है, इसलिए वह सभी मानों को क्रम में सूचीबद्ध कर सकता है और कोई भी मान जल्दी खोज सकता है। हीप केवल यह वादा करता है कि हर पैरेंट अपने बच्चों से पहले आता है, जो न्यूनतम या अधिकतम तुरंत खोजने के लिए काफ़ी है, पर किसी भी मान को खोजने के लिए नहीं।

यूनियन-फ़ाइंड कैसे जानता है कि दो तत्व जुड़े हैं?

वह हर तत्व से पैरेंट लिंकों पर उसके ट्री के रूट तक चलता है। अगर दोनों एक ही रूट पर पहुँचें, तो वे एक ही समुच्चय में हैं। इसके बाद पाथ कम्प्रेशन रास्ते के हर नोड को सीधे रूट की ओर इशारा करवा देता है, इसलिए उनके बारे में अगला सवाल एक ही चरण में हल हो जाता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

डेटा संरचना विज़ुअलाइज़र खोलें