डेटा संरचना खोज: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कंप्यूटर विज्ञान]] में, सर्च डाटा स्ट्रक्चर एक ऐसा [[डेटा संरचना|डाटा स्ट्रक्चर]] है जो आइटम के [[सेट (गणित)|समूह]] से विशिष्ट आइटम | [[कंप्यूटर विज्ञान]] में, सर्च डाटा स्ट्रक्चर एक ऐसा [[डेटा संरचना|डाटा स्ट्रक्चर]] है जो आइटम के [[सेट (गणित)|समूह]] से विशिष्ट आइटम के डेटा रीट्रीवल, उदाहरण के लिए किसी [[डेटाबेस]] से विशिष्ट [[रिकॉर्ड (कंप्यूटर विज्ञान)|रिकॉर्ड]] के रीट्रीवल की अनुमति प्रदान करता है। | ||
सबसे सरल, सबसे सामान्य और सबसे कम कुशल | सबसे सरल, सबसे सामान्य और सबसे कम कुशल सर्च स्ट्रक्चर सभी आइटमों के समूह की एक अव्यवस्थित अनुक्रमिक [[सूची (कंप्यूटिंग)|सूची]] मात्र है। ऐसी सूची में वांछित आइटम का पता लगाने के लिए, [[रैखिक खोज|लिनीअर सर्च]] विधि द्वारा, अनिवार्य रूप से सबसे वर्स्ट केस की कम्प्लेक्सिटी के साथ-साथ [[औसत मामले की जटिलता|एवरेज केस कम्प्लेक्सिटी]] में, आइटमों की संख्या n के अनुपात में कई ऑपरेशनों की आवश्यकता होती है। उपयोगी सर्च डाटा स्ट्रक्चर तेजी से रीट्रीवल की अनुमति देती हैं; यद्यपि, वे कुछ विशिष्ट प्रकार के क्वेरी तक ही सीमित हैं। इसके अतिरिक्त, चूंकि ऐसी स्ट्रक्चरों के निर्माण की लागत कम से कम n के समानुपाती होती है, वे केवल तभी सफल हैं जब एक ही डेटाबेस पर कई क्वेरी को निष्पादित किया जाना होता हैं। | ||
' | 'स्टैटिक' सर्च स्ट्रक्चर, किसी निश्चित डेटाबेस पर कई सूचना रीट्रीवल के लिए डिज़ाइन की गई हैं; 'डाइनैमिक' स्ट्रक्चर सक्सेसिव क्वेरी के बीच आइटमों को इन्सर्ट करने, डिलीट या [[ अद्यतन (एसक्यूएल) |अपडेट करने]] की भी अनुमति देती हैं। डाइनैमिक केस में, हमें डेटाबेस में परिवर्तनों को ध्यान में रखते हुए सर्च स्ट्रक्चर को फिक्सिंग कॉस्ट पर भी विचार करना चाहिए। | ||
==वर्गीकरण== | ==वर्गीकरण== | ||
| Line 9: | Line 9: | ||
सबसे सरल प्रकार की क्वेरी एक रिकॉर्ड का पता लगाना है जिसमें एक निर्दिष्ट मान के बराबर एक विशिष्ट फ़ील्ड (कुंजी) होती है। अन्य सामान्य प्रकार की क्वेरी में सबसे छोटी (या सबसे बड़ी) कुंजी मान वाला आइटम ढूंढें, सबसे बड़ी कुंजी वाला आइटम ढूंढें मान v से अधिक न हो, निर्दिष्ट सीमा v के बीच मुख्य मान वाले सभी आइटम ढूंढें<sub>min</sub> और वी<sub>max</sub>. | सबसे सरल प्रकार की क्वेरी एक रिकॉर्ड का पता लगाना है जिसमें एक निर्दिष्ट मान के बराबर एक विशिष्ट फ़ील्ड (कुंजी) होती है। अन्य सामान्य प्रकार की क्वेरी में सबसे छोटी (या सबसे बड़ी) कुंजी मान वाला आइटम ढूंढें, सबसे बड़ी कुंजी वाला आइटम ढूंढें मान v से अधिक न हो, निर्दिष्ट सीमा v के बीच मुख्य मान वाले सभी आइटम ढूंढें<sub>min</sub> और वी<sub>max</sub>. | ||
कुछ डेटाबेस में मुख्य मान कुछ [[आयाम (गणित)]]|बहुआयामी स्थान में बिंदु हो सकते हैं। उदाहरण के लिए, कुंजी पृथ्वी पर भौगोलिक स्थिति ([[अक्षांश]] और देशांतर) हो सकती है। उस स्थिति में, सामान्य प्रकार की क्वेरीज़ किसी दिए गए बिंदु v के निकटतम कुंजी के साथ रिकॉर्ड ढूंढती हैं, या उन सभी | कुछ डेटाबेस में मुख्य मान कुछ [[आयाम (गणित)]]|बहुआयामी स्थान में बिंदु हो सकते हैं। उदाहरण के लिए, कुंजी पृथ्वी पर भौगोलिक स्थिति ([[अक्षांश]] और देशांतर) हो सकती है। उस स्थिति में, सामान्य प्रकार की क्वेरीज़ किसी दिए गए बिंदु v के निकटतम कुंजी के साथ रिकॉर्ड ढूंढती हैं, या उन सभी आइटमओं को ढूंढती हैं जिनकी कुंजी v से दी गई दूरी पर होती है, या अंतरिक्ष के एक निर्दिष्ट क्षेत्र आर के भीतर सभी आइटमओं को ढूंढती हैं। | ||
उत्तरार्द्ध का एक सामान्य विशेष मामला दो या दो से अधिक सरल कुंजियों पर एक साथ श्रेणी के प्रश्न हैं, जैसे कि 50,000 और 100,000 के बीच वेतन वाले और 1995 और 2007 के बीच काम पर रखे गए सभी कर्मचारी रिकॉर्ड ढूंढना। | उत्तरार्द्ध का एक सामान्य विशेष मामला दो या दो से अधिक सरल कुंजियों पर एक साथ श्रेणी के प्रश्न हैं, जैसे कि 50,000 और 100,000 के बीच वेतन वाले और 1995 और 2007 के बीच काम पर रखे गए सभी कर्मचारी रिकॉर्ड ढूंढना। | ||
Revision as of 21:35, 23 July 2023
कंप्यूटर विज्ञान में, सर्च डाटा स्ट्रक्चर एक ऐसा डाटा स्ट्रक्चर है जो आइटम के समूह से विशिष्ट आइटम के डेटा रीट्रीवल, उदाहरण के लिए किसी डेटाबेस से विशिष्ट रिकॉर्ड के रीट्रीवल की अनुमति प्रदान करता है।
सबसे सरल, सबसे सामान्य और सबसे कम कुशल सर्च स्ट्रक्चर सभी आइटमों के समूह की एक अव्यवस्थित अनुक्रमिक सूची मात्र है। ऐसी सूची में वांछित आइटम का पता लगाने के लिए, लिनीअर सर्च विधि द्वारा, अनिवार्य रूप से सबसे वर्स्ट केस की कम्प्लेक्सिटी के साथ-साथ एवरेज केस कम्प्लेक्सिटी में, आइटमों की संख्या n के अनुपात में कई ऑपरेशनों की आवश्यकता होती है। उपयोगी सर्च डाटा स्ट्रक्चर तेजी से रीट्रीवल की अनुमति देती हैं; यद्यपि, वे कुछ विशिष्ट प्रकार के क्वेरी तक ही सीमित हैं। इसके अतिरिक्त, चूंकि ऐसी स्ट्रक्चरों के निर्माण की लागत कम से कम n के समानुपाती होती है, वे केवल तभी सफल हैं जब एक ही डेटाबेस पर कई क्वेरी को निष्पादित किया जाना होता हैं।
'स्टैटिक' सर्च स्ट्रक्चर, किसी निश्चित डेटाबेस पर कई सूचना रीट्रीवल के लिए डिज़ाइन की गई हैं; 'डाइनैमिक' स्ट्रक्चर सक्सेसिव क्वेरी के बीच आइटमों को इन्सर्ट करने, डिलीट या अपडेट करने की भी अनुमति देती हैं। डाइनैमिक केस में, हमें डेटाबेस में परिवर्तनों को ध्यान में रखते हुए सर्च स्ट्रक्चर को फिक्सिंग कॉस्ट पर भी विचार करना चाहिए।
वर्गीकरण
सबसे सरल प्रकार की क्वेरी एक रिकॉर्ड का पता लगाना है जिसमें एक निर्दिष्ट मान के बराबर एक विशिष्ट फ़ील्ड (कुंजी) होती है। अन्य सामान्य प्रकार की क्वेरी में सबसे छोटी (या सबसे बड़ी) कुंजी मान वाला आइटम ढूंढें, सबसे बड़ी कुंजी वाला आइटम ढूंढें मान v से अधिक न हो, निर्दिष्ट सीमा v के बीच मुख्य मान वाले सभी आइटम ढूंढेंmin और वीmax.
कुछ डेटाबेस में मुख्य मान कुछ आयाम (गणित)|बहुआयामी स्थान में बिंदु हो सकते हैं। उदाहरण के लिए, कुंजी पृथ्वी पर भौगोलिक स्थिति (अक्षांश और देशांतर) हो सकती है। उस स्थिति में, सामान्य प्रकार की क्वेरीज़ किसी दिए गए बिंदु v के निकटतम कुंजी के साथ रिकॉर्ड ढूंढती हैं, या उन सभी आइटमओं को ढूंढती हैं जिनकी कुंजी v से दी गई दूरी पर होती है, या अंतरिक्ष के एक निर्दिष्ट क्षेत्र आर के भीतर सभी आइटमओं को ढूंढती हैं।
उत्तरार्द्ध का एक सामान्य विशेष मामला दो या दो से अधिक सरल कुंजियों पर एक साथ श्रेणी के प्रश्न हैं, जैसे कि 50,000 और 100,000 के बीच वेतन वाले और 1995 और 2007 के बीच काम पर रखे गए सभी कर्मचारी रिकॉर्ड ढूंढना।
एकल आदेशित कुंजियाँ
- यदि मुख्य मान मध्यम रूप से सघन अंतराल पर फैले हों तो डाटा स्ट्रक्चर को व्यवस्थित करें।
- प्राथमिकता क्रमबद्ध सूची; रैखिक खोज देखें
- कुंजी-क्रमबद्ध सरणी; बाइनरी खोज देखें
- स्व-संतुलन बाइनरी खोज वृक्ष
- हैश तालिका
सबसे छोटा तत्व ढूँढना
स्पर्शोन्मुख सबसे खराब स्थिति का विश्लेषण
इस तालिका में, एसिम्प्टोटिक विश्लेषण बिग-ओ नोटेशन|नोटेशन ओ(एफ(एन)) का अर्थ सबसे खराब स्थिति में एफ(एन) के कुछ निश्चित गुणज से अधिक नहीं है।
| Data Structure | Insert | Delete | Balance | Get at index | Search | Find minimum | Find maximum | Space usage |
|---|---|---|---|---|---|---|---|---|
| Unsorted array | O(1) (see note) |
O(1) (see note) |
N/A | O(1) | O(n) | O(n) | O(n) | O(n) |
| Sorted array | O(n) | O(n) | N/A | O(1) | O(log n) | O(1) | O(1) | O(n) |
| Stack | O(1) | O(1) | O(n) | O(n) | ||||
| Queue | O(1) | O(1) | O(n) | O(n) | ||||
| Unsorted linked list | O(1) | O(1)[1] | N/A | O(n) | O(n) | O(n) | O(n) | O(n) |
| Sorted linked list | O(n) | O(1)[1] | N/A | O(n) | O(n) | O(1) | O(1) | O(n) |
| Skip list | ||||||||
| Self-balancing binary search tree | O(log n) | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| Heap | O(log n) | O(log n) | O(log n) | N/A | O(n) | O(1) for a min-heap O(n) for a max-heap[2] |
O(1) for a max-heap O(n) for a min-heap[2] |
O(n) |
| Hash table | O(1) | O(1) | O(n) | N/A | O(1) | O(n) | O(n) | O(n) |
| Trie (k = average length of key) | O(k) | O(k) | N/A | O(k) | O(k) | O(k) | O(k) | O(k n) |
| Cartesian tree | ||||||||
| B-tree | O(log n) | O(log n) | O(log n) | N/A | O(log n) | O(log n) | O(log n) | O(n) |
| Red–black tree | O(log n) | O(log n) | O(log n) | O(n) | ||||
| Splay tree | ||||||||
| AVL tree | O(log n) | |||||||
| k-d tree |
ध्यान दें: किसी अवर्गीकृत सरणी पर इंसर्ट को कभी-कभी O(n) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि सम्मिलित किए जाने वाले तत्व को सरणी के एक विशेष स्थान पर डाला जाना चाहिए, जिसके लिए बाद के सभी तत्वों को एक स्थान से स्थानांतरित करने की आवश्यकता होगी। हालाँकि, एक क्लासिक सरणी में, सरणी का उपयोग मनमाने ढंग से अवर्गीकृत तत्वों को संग्रहीत करने के लिए किया जाता है, और इसलिए किसी भी दिए गए तत्व की सटीक स्थिति का कोई महत्व नहीं होता है, और सरणी आकार को 1 से बढ़ाकर और तत्व को अंत में संग्रहीत करके सम्मिलित किया जाता है। सरणी का, जो एक O(1) ऑपरेशन है।[3][4] इसी तरह, विलोपन ऑपरेशन को कभी-कभी ओ (एन) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि बाद के तत्वों को स्थानांतरित किया जाना चाहिए, लेकिन एक क्लासिक अवर्गीकृत सरणी में क्रम महत्वहीन है (हालांकि तत्वों को सम्मिलित रूप से समय-समय पर आदेश दिया जाता है), इसलिए विलोपन किया जा सकता है हटाए जाने वाले तत्व को सरणी में अंतिम तत्व के साथ स्वैप करके और फिर सरणी आकार को 1 से घटाकर किया जाना चाहिए, जो एक O(1) ऑपरेशन है।[5] यह तालिका केवल एक अनुमानित सारांश है; प्रत्येक डाटा स्ट्रक्चर के लिए विशेष परिस्थितियाँ और भिन्नताएँ होती हैं जिनके कारण अलग-अलग लागतें हो सकती हैं। साथ ही कम लागत प्राप्त करने के लिए दो या दो से अधिक डाटा स्ट्रक्चरओं को जोड़ा जा सकता है।
फ़ुटनोट
- ↑ 1.0 1.1 Cormen, Leiserson, Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 9780262530910.
LIST-DELETE runs in O(1) time, but if to delete an element with a given key, Θ(n) time is required in the worst case because we must first call LIST-SEARCH.
{{cite book}}: CS1 maint: uses authors parameter (link) - ↑ 2.0 2.1 Cormen, Leiserson, Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 9780262530910.
There are two kinds of binary heaps: max-heaps and min-heaps. In both kinds, the values in the nodes satisfy a heap property... the largest element in a max-heap is stored at the root... The smallest element in a min-heap is at the root... The operation HEAP-MAXIMUM returns the maximum heap element in Θ(1) time by simply returning the value A[1] in the heap.
{{cite book}}: CS1 maint: uses authors parameter (link) - ↑ Allen Sherrod (2007). गेम डेवलपर्स के लिए डेटा संरचनाएं और एल्गोरिदम. Cengage Learning. ISBN 9781584506638.
The insertion of an item into an unordered array does not depend on anything other than placing the new item at the end of the list. This gives the insertion into an unordered array of O(1).
- ↑ Cormen, Leiserson, Rivest (1990). Introduction to Algorithms. The College of Information Sciences and Technology at Penn State. ISBN 9780262530910.
{{cite book}}: CS1 maint: uses authors parameter (link) - ↑ "एल्गोरिथम - एक अवर्गीकृत सरणी में विलोपन की समय जटिलता".
Finding the element with a given value is linear. Since the array isn't sorted anyway, you can do the deletion itself in constant time. First swap the element you want to delete to the end of the array, then reduce the array size by one element.
यह भी देखें
श्रेणी:डाटा स्ट्रक्चरएँ
