डेटा संरचना खोज: Difference between revisions

From Vigyanwiki
No edit summary
 
(9 intermediate revisions by 5 users not shown)
Line 1: Line 1:
[[कंप्यूटर विज्ञान]] में, सर्च डाटा स्ट्रक्चर एक ऐसा [[डेटा संरचना|डाटा स्ट्रक्चर]] है जो आइटम के [[सेट (गणित)|समूह]] से विशिष्ट आइटम की डेटा रीट्रीवल, उदाहरण के लिए किसी [[डेटाबेस]] से विशिष्ट [[रिकॉर्ड (कंप्यूटर विज्ञान)|रिकॉर्ड]] के रीट्रीवल की अनुमति प्रदान करता है।
[[कंप्यूटर विज्ञान]] में, '''सर्च डाटा स्ट्रक्चर''' एक ऐसा [[डेटा संरचना|डाटा स्ट्रक्चर]] है जो आइटम के [[सेट (गणित)|समूह]] से विशिष्ट आइटम के डेटा रीट्रीवल, उदाहरण के लिए किसी [[डेटाबेस]] से विशिष्ट [[रिकॉर्ड (कंप्यूटर विज्ञान)|रिकॉर्ड]] के रीट्रीवल की अनुमति प्रदान करता है।


सबसे सरल, सबसे सामान्य और सबसे कम कुशल खोज संरचना सभी वस्तुओं की एक अव्यवस्थित अनुक्रमिक [[सूची (कंप्यूटिंग)]] मात्र है। ऐसी सूची में वांछित वस्तु का पता लगाने के लिए, [[रैखिक खोज]] विधि द्वारा, अनिवार्य रूप से सबसे खराब स्थिति की जटिलता के साथ-साथ [[औसत मामले की जटिलता]] में, वस्तुओं की संख्या n के अनुपात में कई ऑपरेशनों की आवश्यकता होती है। उपयोगी सर्च डाटा स्ट्रक्चरएं तेजी से पुनर्प्राप्ति की अनुमति देती हैं; हालाँकि, वे कुछ विशिष्ट प्रकार के प्रश्नों तक ही सीमित हैं। इसके अलावा, चूंकि ऐसी संरचनाओं के निर्माण की लागत कम से कम n के समानुपाती होती है, वे केवल तभी भुगतान करते हैं जब एक ही डेटाबेस (या ऐसे डेटाबेस पर जो प्रश्नों के बीच थोड़ा बदलता है) पर कई प्रश्न निष्पादित किए जाने होते हैं।
सबसे सरल, सबसे सामान्य और सबसे कम कुशल सर्च स्ट्रक्चर सभी आइटमों के समूह की एक अव्यवस्थित अनुक्रमिक [[सूची (कंप्यूटिंग)|सूची]] मात्र है। ऐसी सूची में वांछित आइटम का पता लगाने के लिए, [[रैखिक खोज|लिनीअर सर्च]] विधि द्वारा, अनिवार्य रूप से सबसे वर्स्ट केस की कम्प्लेक्सिटी के साथ-साथ [[औसत मामले की जटिलता|एवरेज केस कम्प्लेक्सिटी]] में, आइटमों की संख्या n के अनुपात में कई ऑपरेशनों की आवश्यकता होती है। उपयोगी सर्च डाटा स्ट्रक्चर तेजी से रीट्रीवल की अनुमति देती हैं; यद्यपि, वे कुछ विशिष्ट प्रकार के क्वेरी तक ही सीमित हैं। इसके अतिरिक्त, चूंकि ऐसी स्ट्रक्चरों के निर्माण की लागत कम से कम n के समानुपाती होती है, वे केवल तभी सफल हैं जब एक ही डेटाबेस पर कई क्वेरी को निष्पादित किया जाना होता हैं।


'स्थैतिक' खोज संरचनाएं एक निश्चित डेटाबेस पर कई सूचना पुनर्प्राप्ति का उत्तर देने के लिए डिज़ाइन की गई हैं; 'गतिशील' संरचनाएं क्रमिक प्रश्नों के बीच आइटमों को सम्मिलित करने, हटाने या [[ अद्यतन (एसक्यूएल) ]] की भी अनुमति देती हैं। गतिशील मामले में, किसी को डेटाबेस में परिवर्तनों को ध्यान में रखते हुए खोज संरचना को ठीक करने की लागत पर भी विचार करना चाहिए।
'स्टैटिक' सर्च स्ट्रक्चर, किसी निश्चित डेटाबेस पर कई सूचना रीट्रीवल के लिए डिज़ाइन की गई हैं; 'डाइनैमिक' स्ट्रक्चर सक्सेसिव क्वेरी के बीच आइटमों को इन्सर्ट करने, डिलीट या [[ अद्यतन (एसक्यूएल) |अपडेट करने]] की भी अनुमति देती हैं। डाइनैमिक केस में, हमें डेटाबेस में परिवर्तनों को ध्यान में रखते हुए सर्च स्ट्रक्चर को फिक्सिंग कॉस्ट पर भी विचार करना चाहिए।


==वर्गीकरण==
==वर्गीकरण==


सबसे सरल प्रकार की क्वेरी एक रिकॉर्ड का पता लगाना है जिसमें एक निर्दिष्ट मान के बराबर एक विशिष्ट फ़ील्ड (कुंजी) होती है। अन्य सामान्य प्रकार की क्वेरी में सबसे छोटी (या सबसे बड़ी) कुंजी मान वाला आइटम ढूंढें, सबसे बड़ी कुंजी वाला आइटम ढूंढें मान v से अधिक न हो, निर्दिष्ट सीमा v के बीच मुख्य मान वाले सभी आइटम ढूंढें<sub>min</sub> और वी<sub>max</sub>.
सबसे सरल प्रकार की क्वेरी किसी ऐसे रिकॉर्ड का पता लगाना है जिसमें एक निर्दिष्ट फ़ील्ड किसी निर्दिष्ट मान v के बराबर है। अन्य सामान्य प्रकार की क्वेरी "न्यूनतम (या अधिकतम) की वैल्यू वाले आइटम को सर्च करे", "v से अधिकतम की वैल्यू वाले आइटम सर्च करें ", "v<sub>min</sub> और v<sub>max</sub> के मध्य विशिष्ट बाउन्ड के की वैल्यू वाले सभी आइटम सर्च करें" आदि हैं।


कुछ डेटाबेस में मुख्य मान कुछ [[आयाम (गणित)]]|बहुआयामी स्थान में बिंदु हो सकते हैं। उदाहरण के लिए, कुंजी पृथ्वी पर भौगोलिक स्थिति ([[अक्षांश]] और देशांतर) हो सकती है। उस स्थिति में, सामान्य प्रकार की क्वेरीज़ किसी दिए गए बिंदु v के निकटतम कुंजी के साथ रिकॉर्ड ढूंढती हैं, या उन सभी वस्तुओं को ढूंढती हैं जिनकी कुंजी v से दी गई दूरी पर होती है, या अंतरिक्ष के एक निर्दिष्ट क्षेत्र आर के भीतर सभी वस्तुओं को ढूंढती हैं।
विशेष डेटाबेस में, 'की वैल्यू' बहुआयामी स्थान में कुछ बिंदु हो सकते हैं। उदाहरण के लिए, कोई 'की' पृथ्वी पर भौगोलिक स्थिति ([[अक्षांश]] और देशांतर) को प्रदर्शित कर सकती है। उस स्थिति में, सामान्य प्रकार की क्वेरी किसी दिए गए बिंदु v के निकटतम 'की' के साथ रिकॉर्ड खोजती हैं, या उन सभी आइटमों को खोजती हैं जिनकी 'की' v से दी गई दूरी पर होती है, या स्पेस के किसी निर्दिष्ट क्षेत्र आर के भीतर सभी आइटमों को खोजती हैं।


उत्तरार्द्ध का एक सामान्य विशेष मामला दो या दो से अधिक सरल कुंजियों पर एक साथ श्रेणी के प्रश्न हैं, जैसे कि 50,000 और 100,000 के बीच वेतन वाले और 1995 और 2007 के बीच काम पर रखे गए सभी कर्मचारी रिकॉर्ड ढूंढना।
इनके एक सामान्य विशेष परिप्रेक्ष्य का एक उदाहरण हैː दो या अधिक सरल 'की' पर साइमल्टैनीअस रेंज क्वेरी, जैसे "50,000 से 100,000 तक वेतन वाले और 1995 से 2007 तक भर्ती हुए सभी कर्मचारी रिकॉर्ड ढूंढें।"


===एकल आदेशित कुंजियाँ===
===सिंगल ऑर्डर की===
* यदि मुख्य मान मध्यम रूप से सघन अंतराल पर फैले हों तो डाटा स्ट्रक्चर को व्यवस्थित करें।
* यदि की वैल्यू मॉडरेटली कम्पैक्ट इंटरवल पर स्पैन हों तो डाटा स्ट्रक्चर को ऐरे के रूप में व्यवस्थित करें।
*प्राथमिकता क्रमबद्ध सूची; रैखिक खोज देखें
*प्राइऑरटी-सॉर्टिड लिस्ट; लिनीअर सर्च देखें
*कुंजी-क्रमबद्ध सरणी; बाइनरी खोज देखें
*की-सॉर्टिड ऐरे; बाइनरी सर्च देखें
*स्व-संतुलन बाइनरी खोज वृक्ष
*सेल्फ-बैलेन्सिग बाइनरी सर्च ट्री
*[[हैश तालिका]]
*[[हैश तालिका|हैश टेबल]]


===सबसे छोटा तत्व ढूँढना===
===सबसे छोटे एलेमेन्ट का पता लगाना===
*[[ढेर (डेटा संरचना)|ढेर (डाटा स्ट्रक्चर)]]
*[[ढेर (डेटा संरचना)|हीप]]


==स्पर्शोन्मुख सबसे खराब स्थिति का विश्लेषण==
==असिम्प्टोटिक वर्स्ट-केस विश्लेषण==


इस तालिका में, एसिम्प्टोटिक विश्लेषण बिग-ओ नोटेशन|नोटेशन ओ(एफ(एन)) का अर्थ सबसे खराब स्थिति में एफ(एन) के कुछ निश्चित गुणज से अधिक नहीं है।
इस तालिका में, एसिम्प्टोटिक विश्लेषण बिग-ओ नोटेशन (ओ(एफ(एन)) का अर्थ "वर्स्ट-केस में एफ(एन) के कुछ निश्चित गुणज से अधिक न होना" है।


{| class="wikitable"
{| class="wikitable"
|-
|-
! Data Structure
! डाटा स्ट्रक्चर
! Insert
! इन्सर्ट
! Delete
! डिलीट
! Balance
! बैलेंस
! Get at index
! गेट ऐन इंडेक्स
! Search
! सर्च
! Find minimum
! फाइन्ड मिनमम
! Find maximum
! फाइन्ड मैक्समम
! Space usage
! स्पेस उपयोग
|-
|-
| Unsorted [[Array data structure|array]]
| अनसॉर्टिड [[Array data structure|ऐरे]]
| [[Constant time|''O''(1)]]<br><sup>(see&nbsp;note)</sup>
| [[Constant time|''O''(1)]]<br><sup>(see&nbsp;note)</sup>
| ''O''(1)<br><sup>(see&nbsp;note)</sup>
| ''O''(1)<br><sup>(see&nbsp;note)</sup>
Line 49: Line 49:
| ''O''(''n'')
| ''O''(''n'')
|-
|-
| [[Sorted array]]
| [[Sorted array|सॉर्टिड]] [[Array data structure|ऐरे]]
| ''O''(''n'')
| ''O''(''n'')
| ''O''(''n'')
| ''O''(''n'')
Line 59: Line 59:
| ''O''(''n'')
| ''O''(''n'')
|-
|-
| [[Stack (abstract data type)|Stack]]
| [[Stack (abstract data type)|स्टैक]]
|''O''(1)
|''O''(1)
|''O''(1)
|''O''(1)
Line 69: Line 69:
|''O''(''n'')
|''O''(''n'')
|-
|-
| [[Queue (abstract data type)|Queue]]
| [[Queue (abstract data type)|क्यू]]
|''O''(1)
|''O''(1)
|''O''(1)
|''O''(1)
Line 79: Line 79:
|''O''(''n'')
|''O''(''n'')
|-
|-
| Unsorted [[linked list]]
| अनसॉर्टिड लिंक्ड लिस्ट
| ''O''(1)
| ''O''(1)
| ''O''(1)<ref name="listdelete">{{cite book |title=[[Introduction to Algorithms]] |publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|year=1990 |quote=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.}}</ref>
| ''O''(1)<ref name="listdelete">{{cite book |title=[[Introduction to Algorithms]] |publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|year=1990 |quote=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.}}</ref>
Line 89: Line 89:
| ''O''(''n'')
| ''O''(''n'')
|-
|-
| Sorted linked list
| सॉर्टिड लिंक्ड लिस्ट
| ''O''(''n'')
| ''O''(''n'')
| ''O''(1)<ref name="listdelete" />
| ''O''(1)<ref name="listdelete" />
Line 99: Line 99:
| ''O''(''n'')
| ''O''(''n'')
|-
|-
| [[Skip list]]
| [[Skip list|स्किप लिस्ट]]  
|
|
|
|
Line 109: Line 109:
|
|
|-
|-
| [[Self-balancing binary search tree]]
| [[Self-balancing binary search tree|सेल्फ-बैलेन्सिग बाइनरी सर्च ट्री]]  
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
Line 119: Line 119:
| ''O''(''n'')
| ''O''(''n'')
|-
|-
| [[Heap (data structure)|Heap]]
| [[Heap (data structure)|हीप]]
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
Line 129: Line 129:
| ''O''(''n'')
| ''O''(''n'')
|-
|-
| [[Hash table]]
| [[Hash table|हैश टेबल]]
| ''O''(1)
| ''O''(1)
| ''O''(1)
| ''O''(1)
Line 139: Line 139:
| ''O''(''n'')  
| ''O''(''n'')  
|-
|-
| [[Trie]] (''k'' = average length of key)
| [[Trie|ट्री]] (''k'' = 'की' की औसत लंबाई)
| ''O''(''k'')
| ''O''(''k'')
| ''O''(''k'')
| ''O''(''k'')
Line 149: Line 149:
| ''O''(''k'' ''n'')
| ''O''(''k'' ''n'')
|-
|-
| [[Cartesian tree]]
| [[Cartesian tree|करतेसियाँ ट्री]]
|
|
|
|
Line 159: Line 159:
|
|
|-
|-
| [[B-tree]]
| [[B-tree|बी-ट्री]]
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
| ''O''(log&nbsp;''n'')
Line 169: Line 169:
| ''O''(''n'')  
| ''O''(''n'')  
|-
|-
| [[Red–black tree]]
| [[Red–black tree|रेड-ब्लैक ट्री]]
|''O''(log&nbsp;''n'')
|''O''(log&nbsp;''n'')
|''O''(log&nbsp;''n'')
|''O''(log&nbsp;''n'')
Line 179: Line 179:
|''O''(''n'')
|''O''(''n'')
|-
|-
| [[Splay tree]]
| [[Splay tree|स्प्ले ट्री]]
|
|
|
|
Line 189: Line 189:
|
|
|-
|-
| [[AVL tree]]
| [[AVL tree|एवीएल ट्री]]
|
|
|
|
Line 199: Line 199:
|
|
|-
|-
| [[k-d tree]]
| [[k-d tree|के-डी ट्री]]
|
|
|
|
Line 209: Line 209:
|
|
|}
|}
ध्यान दें: किसी अवर्गीकृत सरणी पर इंसर्ट को कभी-कभी O(n) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि सम्मिलित किए जाने वाले तत्व को सरणी के एक विशेष स्थान पर डाला जाना चाहिए, जिसके लिए बाद के सभी तत्वों को एक स्थान से स्थानांतरित करने की आवश्यकता होगी। हालाँकि, एक क्लासिक सरणी में, सरणी का उपयोग मनमाने ढंग से अवर्गीकृत तत्वों को संग्रहीत करने के लिए किया जाता है, और इसलिए किसी भी दिए गए तत्व की सटीक स्थिति का कोई महत्व नहीं होता है, और सरणी आकार को 1 से बढ़ाकर और तत्व को अंत में संग्रहीत करके सम्मिलित किया जाता है। सरणी का, जो एक O(1) ऑपरेशन है।<ref name="games">{{cite book|isbn=9781584506638|title=गेम डेवलपर्स के लिए डेटा संरचनाएं और एल्गोरिदम|author=Allen Sherrod|publisher=Cengage Learning|year=2007|quote=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).}}</ref><ref>{{cite book |title=[[Introduction to Algorithms]]|publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|year=1990 }}</ref> इसी तरह, विलोपन ऑपरेशन को कभी-कभी ओ (एन) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि बाद के तत्वों को स्थानांतरित किया जाना चाहिए, लेकिन एक क्लासिक अवर्गीकृत सरणी में क्रम महत्वहीन है (हालांकि तत्वों को सम्मिलित रूप से समय-समय पर आदेश दिया जाता है), इसलिए विलोपन किया जा सकता है हटाए जाने वाले तत्व को सरणी में अंतिम तत्व के साथ स्वैप करके और फिर सरणी आकार को 1 से घटाकर किया जाना चाहिए, जो एक O(1) ऑपरेशन है।<ref>{{cite web|url=https://stackoverflow.com/questions/9358481/algorithm-the-time-complexity-of-deletion-in-a-unsorted-array#9358634|title=एल्गोरिथम - एक अवर्गीकृत सरणी में विलोपन की समय जटिलता|quote=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.}}</ref>
ध्यान दें: किसी अनसॉर्टिड ऐरे पर इंसर्ट को कभी-कभी O(n) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि इन्सर्ट किए जाने वाले एलेमेन्ट को ऐरे के एक विशेष स्थान पर इन्सर्ट किया जाना चाहिए, जिसके लिए बाद के सभी एलेमेन्टों को एक स्थान से शिफ्ट करने की आवश्यकता होगी। यद्यपि, एक क्लासिक ऐरे में, ऐरे का उपयोग यादृच्छिक ढंग से अनसॉर्टिड एलेमेन्टों को संग्रहीत करने के लिए किया जाता है, और इसलिए किसी भी दिए गए एलेमेन्ट की सटीक स्थिति का कोई महत्व नहीं होता है, और ऐरे आकार को 1 से बढ़ाकर और एलेमेन्ट को अंत में संग्रहीत करके इन्सर्ट किया जाता है जो एक O(1) ऑपरेशन है।<ref name="games">{{cite book|isbn=9781584506638|title=गेम डेवलपर्स के लिए डेटा संरचनाएं और एल्गोरिदम|author=Allen Sherrod|publisher=Cengage Learning|year=2007|quote=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).}}</ref><ref>{{cite book |title=[[Introduction to Algorithms]]|publisher=The College of Information Sciences and Technology at Penn State|isbn=9780262530910|authors=Cormen, Leiserson, Rivest|year=1990 }}</ref> इसी तरह, डिलीट ऑपरेशन को कभी-कभी ओ (एन) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि बाद के एलेमेन्टों को शिफ्ट किया जाना चाहिए, परंतु एक क्लासिक अनसॉर्टिड ऐरे में क्रम महत्वहीन है इसलिए इन्हे डिलीट किया जा सकता है। डिलीट किए  जाने वाले एलेमेन्ट को ऐरे में अंतिम एलेमेन्ट के साथ स्वैप करके और फिर ऐरे आकार को 1 से घटाकर किया जाना चाहिए, जो एक O(1) ऑपरेशन है।<ref>{{cite web|url=https://stackoverflow.com/questions/9358481/algorithm-the-time-complexity-of-deletion-in-a-unsorted-array#9358634|title=एल्गोरिथम - एक अवर्गीकृत सरणी में विलोपन की समय जटिलता|quote=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.}}</ref>
यह तालिका केवल एक अनुमानित सारांश है; प्रत्येक डाटा स्ट्रक्चर के लिए विशेष परिस्थितियाँ और भिन्नताएँ होती हैं जिनके कारण अलग-अलग लागतें हो सकती हैं। साथ ही कम लागत प्राप्त करने के लिए दो या दो से अधिक डाटा स्ट्रक्चरओं को जोड़ा जा सकता है।
 
यह तालिका केवल एक अनुमानित सारांश है; प्रत्येक डाटा स्ट्रक्चर के लिए विशेष परिस्थितियाँ और भिन्नताएँ होती हैं जिनके कारण अलग-अलग कॉस्ट हो सकतें हैं। साथ ही कम कॉस्ट प्राप्त करने के लिए दो या दो से अधिक डाटा स्ट्रक्चओ को जोड़ा जा सकता है।


== फ़ुटनोट ==
== फ़ुटनोट ==
Line 221: Line 222:
श्रेणी:डाटा स्ट्रक्चरएँ
श्रेणी:डाटा स्ट्रक्चरएँ


 
[[Category:CS1 maint]]
[[Category: Machine Translated Page]]
[[Category:Created On 10/07/2023]]
[[Category:Created On 10/07/2023]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Templates Vigyan Ready]]

Latest revision as of 13:16, 31 October 2023

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

सबसे सरल, सबसे सामान्य और सबसे कम कुशल सर्च स्ट्रक्चर सभी आइटमों के समूह की एक अव्यवस्थित अनुक्रमिक सूची मात्र है। ऐसी सूची में वांछित आइटम का पता लगाने के लिए, लिनीअर सर्च विधि द्वारा, अनिवार्य रूप से सबसे वर्स्ट केस की कम्प्लेक्सिटी के साथ-साथ एवरेज केस कम्प्लेक्सिटी में, आइटमों की संख्या n के अनुपात में कई ऑपरेशनों की आवश्यकता होती है। उपयोगी सर्च डाटा स्ट्रक्चर तेजी से रीट्रीवल की अनुमति देती हैं; यद्यपि, वे कुछ विशिष्ट प्रकार के क्वेरी तक ही सीमित हैं। इसके अतिरिक्त, चूंकि ऐसी स्ट्रक्चरों के निर्माण की लागत कम से कम n के समानुपाती होती है, वे केवल तभी सफल हैं जब एक ही डेटाबेस पर कई क्वेरी को निष्पादित किया जाना होता हैं।

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

वर्गीकरण

सबसे सरल प्रकार की क्वेरी किसी ऐसे रिकॉर्ड का पता लगाना है जिसमें एक निर्दिष्ट फ़ील्ड किसी निर्दिष्ट मान v के बराबर है। अन्य सामान्य प्रकार की क्वेरी "न्यूनतम (या अधिकतम) की वैल्यू वाले आइटम को सर्च करे", "v से अधिकतम की वैल्यू वाले आइटम सर्च करें ", "vmin और vmax के मध्य विशिष्ट बाउन्ड के की वैल्यू वाले सभी आइटम सर्च करें" आदि हैं।

विशेष डेटाबेस में, 'की वैल्यू' बहुआयामी स्थान में कुछ बिंदु हो सकते हैं। उदाहरण के लिए, कोई 'की' पृथ्वी पर भौगोलिक स्थिति (अक्षांश और देशांतर) को प्रदर्शित कर सकती है। उस स्थिति में, सामान्य प्रकार की क्वेरी किसी दिए गए बिंदु v के निकटतम 'की' के साथ रिकॉर्ड खोजती हैं, या उन सभी आइटमों को खोजती हैं जिनकी 'की' v से दी गई दूरी पर होती है, या स्पेस के किसी निर्दिष्ट क्षेत्र आर के भीतर सभी आइटमों को खोजती हैं।

इनके एक सामान्य विशेष परिप्रेक्ष्य का एक उदाहरण हैː दो या अधिक सरल 'की' पर साइमल्टैनीअस रेंज क्वेरी, जैसे "50,000 से 100,000 तक वेतन वाले और 1995 से 2007 तक भर्ती हुए सभी कर्मचारी रिकॉर्ड ढूंढें।"

सिंगल ऑर्डर की

  • यदि की वैल्यू मॉडरेटली कम्पैक्ट इंटरवल पर स्पैन हों तो डाटा स्ट्रक्चर को ऐरे के रूप में व्यवस्थित करें।
  • प्राइऑरटी-सॉर्टिड लिस्ट; लिनीअर सर्च देखें
  • की-सॉर्टिड ऐरे; बाइनरी सर्च देखें
  • सेल्फ-बैलेन्सिग बाइनरी सर्च ट्री
  • हैश टेबल

सबसे छोटे एलेमेन्ट का पता लगाना

असिम्प्टोटिक वर्स्ट-केस विश्लेषण

इस तालिका में, एसिम्प्टोटिक विश्लेषण बिग-ओ नोटेशन (ओ(एफ(एन)) का अर्थ "वर्स्ट-केस में एफ(एन) के कुछ निश्चित गुणज से अधिक न होना" है।

डाटा स्ट्रक्चर इन्सर्ट डिलीट बैलेंस गेट ऐन इंडेक्स सर्च फाइन्ड मिनमम फाइन्ड मैक्समम स्पेस उपयोग
अनसॉर्टिड ऐरे O(1)
(see note) 		O(1)
(see note) 		N/A O(1) O(n) O(n) O(n) O(n)
सॉर्टिड ऐरे O(n) O(n) N/A O(1) O(log n) O(1) O(1) O(n)
स्टैक O(1) O(1) O(n) O(n)
क्यू O(1) O(1) O(n) O(n)
अनसॉर्टिड लिंक्ड लिस्ट O(1) O(1)[1] N/A O(n) O(n) O(n) O(n) O(n)
सॉर्टिड लिंक्ड लिस्ट O(n) O(1)[1] N/A O(n) O(n) O(1) O(1) O(n)
स्किप लिस्ट
सेल्फ-बैलेन्सिग बाइनरी सर्च ट्री O(log n) O(log n) O(log n) N/A O(log n) O(log n) O(log n) O(n)
हीप 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)
हैश टेबल O(1) O(1) O(n) N/A O(1) O(n) O(n) O(n)
ट्री (k = 'की' की औसत लंबाई) O(k) O(k) N/A O(k) O(k) O(k) O(k) O(k n)
करतेसियाँ ट्री
बी-ट्री O(log n) O(log n) O(log n) N/A O(log n) O(log n) O(log n) O(n)
रेड-ब्लैक ट्री O(log n) O(log n) O(log n) O(n)
स्प्ले ट्री
एवीएल ट्री O(log n)
के-डी ट्री

ध्यान दें: किसी अनसॉर्टिड ऐरे पर इंसर्ट को कभी-कभी O(n) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि इन्सर्ट किए जाने वाले एलेमेन्ट को ऐरे के एक विशेष स्थान पर इन्सर्ट किया जाना चाहिए, जिसके लिए बाद के सभी एलेमेन्टों को एक स्थान से शिफ्ट करने की आवश्यकता होगी। यद्यपि, एक क्लासिक ऐरे में, ऐरे का उपयोग यादृच्छिक ढंग से अनसॉर्टिड एलेमेन्टों को संग्रहीत करने के लिए किया जाता है, और इसलिए किसी भी दिए गए एलेमेन्ट की सटीक स्थिति का कोई महत्व नहीं होता है, और ऐरे आकार को 1 से बढ़ाकर और एलेमेन्ट को अंत में संग्रहीत करके इन्सर्ट किया जाता है जो एक O(1) ऑपरेशन है।[3][4] इसी तरह, डिलीट ऑपरेशन को कभी-कभी ओ (एन) के रूप में उद्धृत किया जाता है, इस धारणा के कारण कि बाद के एलेमेन्टों को शिफ्ट किया जाना चाहिए, परंतु एक क्लासिक अनसॉर्टिड ऐरे में क्रम महत्वहीन है इसलिए इन्हे डिलीट किया जा सकता है। डिलीट किए जाने वाले एलेमेन्ट को ऐरे में अंतिम एलेमेन्ट के साथ स्वैप करके और फिर ऐरे आकार को 1 से घटाकर किया जाना चाहिए, जो एक O(1) ऑपरेशन है।[5]

यह तालिका केवल एक अनुमानित सारांश है; प्रत्येक डाटा स्ट्रक्चर के लिए विशेष परिस्थितियाँ और भिन्नताएँ होती हैं जिनके कारण अलग-अलग कॉस्ट हो सकतें हैं। साथ ही कम कॉस्ट प्राप्त करने के लिए दो या दो से अधिक डाटा स्ट्रक्चओ को जोड़ा जा सकता है।

फ़ुटनोट

  1. ↑ 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. ↑ 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)
  3. ↑ 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).
  4. ↑ 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)
  5. ↑ "एल्गोरिथम - एक अवर्गीकृत सरणी में विलोपन की समय जटिलता". 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.

यह भी देखें

श्रेणी:डाटा स्ट्रक्चरएँ

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=डेटा_संरचना_खोज&oldid=271851’