सर्च ट्री: Difference between revisions
(Created page with "{{Short description|Data structure in tree form sorted for fast lookup}} {{Distinguish|tree search}} कंप्यूटर विज्ञान में, एक ख...") |
No edit summary |
||
| Line 2: | Line 2: | ||
{{Distinguish|tree search}} | {{Distinguish|tree search}} | ||
[[ | [[Index.php?title=अभिकलित्र विज्ञान|अभिकलित्र विज्ञान]] में, एक '''खोज वृक्ष''' एक [[Index.php?title=वृक्ष आँकड़ा संरचना|वृक्ष आँकड़ा संरचना]] है जिसका उपयोग एक सेट के भीतर से विशिष्ट कुंजियों का पता लगाने के लिए किया जाता है। किसी वृक्ष को खोज वृक्ष के रूप में कार्य करने के लिए, प्रत्येक ग्रंथिकि की कुंजी बाईं ओर के उप-वृक्षों में किसी भी कुंजी से बड़ी होनी चाहिए, और दाईं ओर उप-वृक्षों में किसी भी कुंजी से कम होनी चाहिए।<ref>Black, Paul and Pieterse, Vreda (2005). [https://xlinux.nist.gov/dads/HTML/searchtree.html "search tree"]. [http://xlinux.nist.gov/dads// Dictionary of Algorithms and Data Structures]</ref> | ||
खोज वृक्षों का लाभ उनका कुशल खोज समय है, क्योंकि वृक्ष यथोचित रूप से संतुलित है, जिसका अर्थ है कि वृक्ष | खोज वृक्षों का लाभ उनका कुशल खोज समय है, क्योंकि वृक्ष यथोचित रूप से संतुलित है, जिसका अर्थ है कि वृक्ष आंकड़ा संरचना # दोनों छोर पर वृक्षों में उपयोग की जाने वाली शब्दावली तुलनीय गहराई की हैं। विभिन्न खोज-वृक्ष आंकड़ा संरचनाएं मौजूद हैं, जिनमें से कई तत्वों को कुशल रूप से सम्मिलित करने और हटाने की भी अनुमति देती हैं, जिसके संचालन के लिए वृक्ष संतुलन बनाए रखना होता है। | ||
खोज वृक्षों का उपयोग अक्सर सहयोगी सरणी को लागू करने के लिए किया जाता है। खोज | खोज वृक्षों का उपयोग अक्सर सहयोगी सरणी को लागू करने के लिए किया जाता है। खोज वृक्ष कलनविधि किसी स्थान को ढूंढने के लिए विशेषता कुंजी-मूल्य जोड़ी से कुंजी का उपयोग करता है, और फिर अनुप्रयोग उस विशेष स्थान पर संपूर्ण कुंजी-मूल्य जोड़ी को संग्रहीत करता है। | ||
== | ==वृक्षों के प्रकार== | ||
[[File:Binary search tree.svg|thumb|alt=Binary search tree| | [[File:Binary search tree.svg|thumb|alt=Binary search tree|द्विआधारी खोज वृक्ष]] | ||
=== | ===द्विआधारी '''खोज वृक्ष'''=== | ||
{{Main| | {{Main|द्विआधारी खोज वृक्ष}} | ||
द्विआधारी खोज वृक्ष एक ग्रंथिकि-आधारित आंकड़ा संरचना है जहां प्रत्येक ग्रंथिकि में एक कुंजी और दो उपवृक्ष, बाएँ और दाएँ होते हैं। सभी ग्रंथिकि के लिए, बाएं उपवृक्ष की कुंजी ग्रंथिकि की कुंजी से कम होनी चाहिए, और दाएं उपवृक्ष की कुंजी ग्रंथिकि की कुंजी से बड़ी होनी चाहिए। इन सभी उपवृक्षों को द्विआधारी खोज वृक्षों के रूप में योग्य होना चाहिए। | |||
द्विआधारी खोज वृक्ष को खोजने के लिए सबसे खराब स्थिति वाली समय जटिलता वृक्षों में प्रयुक्त वृक्ष (आंकड़ा संरचना)#शब्दावली है, जो एन तत्वों वाले वृक्ष के लिए ओ (लॉग एन) जितनी छोटी हो सकती है। | |||
===बी-वृक्ष=== | ===बी-वृक्ष=== | ||
{{Main| | {{Main|बी-वृक्ष}} | ||
बी- | |||
बी-वृक्ष द्विआधारी खोज वृक्ष का सामान्यीकरण है जिसमें प्रत्येक ग्रंथिकि पर उपवृक्ष की एक चर संख्या हो सकती है। जबकि अपत्य-ग्रंथिकि की एक पूर्व-निर्धारित सीमा होती है, वे आवश्यक रूप से आंकड़ा से भरे नहीं होंगे, जिसका अर्थ है कि बी-वृक्ष संभावित रूप से कुछ स्थान बर्बाद कर सकते हैं। फायदा यह है कि बी-वृक्ष को अन्य [[ स्व-संतुलन द्विआधारी खोज वृक्ष ]]की तरह बार-बार पुन: संतुलित करने की आवश्यकता नहीं होती है। | |||
उनकी ग्रंथिकि लंबाई की परिवर्तनशील सीमा के कारण, बी-वृक्ष को उन प्रणालियों के लिए अनुकूलित किया जाता है जो आंकड़े के बड़े ब्लॉक को पढ़ते हैं, इनका उपयोग आमतौर पर आंकड़ाबेस में भी किया जाता है। | |||
बी-वृक्ष खोजने के लिए समय जटिलता ओ(लॉग एन) है। | |||
बी- | ===(ए,बी)-वृक्ष=== | ||
{{Main|(ए,बी)-वृक्ष}} | |||
एक (ए,बी)-वृक्ष एक खोज वृक्ष है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक ग्रंथिकि में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि रूट में कम से कम 2 बच्चे और अधिकतम बी बच्चे होते हैं। | |||
एक (ए,बी)-वृक्ष एक खोज वृक्ष है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक | |||
ए और बी को निम्नलिखित सूत्र से तय किया जा सकता है:<ref>Toal, Ray. [http://cs.lmu.edu/~ray/notes/abtrees/ "(a,b) Trees"]</ref> | ए और बी को निम्नलिखित सूत्र से तय किया जा सकता है:<ref>Toal, Ray. [http://cs.lmu.edu/~ray/notes/abtrees/ "(a,b) Trees"]</ref> | ||
<math>2 \le a \le \frac{(b+1)}{2}</math> | <math>2 \le a \le \frac{(b+1)}{2}</math> | ||
(ए,बी)- | (ए,बी)-वृक्ष को खोजने के लिए समय जटिलता ओ(लॉग एन) है। | ||
===त्रयी खोज वृक्ष=== | |||
{{Main|त्रयी खोज वृक्ष}} | |||
त्रयी खोज वृक्ष एक प्रकार का वृक्ष (आंकड़ा संरचना) है जिसमें 3 ग्रंथिकि हो सकते हैं: एक निम्न बच्चा, एक समान बच्चा और एक उच्च बच्चा। प्रत्येक ग्रंथिकि एक एकल वर्ण संग्रहीत करता है और संभावित तीसरे ग्रंथिकि के अपवाद के साथ, वृक्ष को उसी तरह से क्रमबद्ध किया जाता है जैसे द्विआधारी खोज वृक्ष होता है। | |||
त्रयी खोज वृक्ष की खोज में यह जांचने के लिए एक [[Index.php?title=स्ट्रिंग (अभिकलित्र विज्ञान)|स्ट्रिंग (अभिकलित्र विज्ञान)]] को पार करना शामिल है कि क्या किसी पथ में यह शामिल है। | |||
एक संतुलित टर्नरी खोज वृक्ष की खोज के लिए समय जटिलता | एक संतुलित टर्नरी खोज वृक्ष की खोज के लिए समय जटिलता ओ(लॉग एन) है। | ||
== | ==कलनविधि खोजना== | ||
===किसी विशिष्ट कुंजी की खोज=== | ===किसी विशिष्ट कुंजी की खोज=== | ||
यह मानते हुए कि | यह मानते हुए कि वृक्ष का ऑर्डर दिया गया है, हम एक चाबी ले सकते हैं और उसे वृक्ष के भीतर ढूंढने का प्रयास कर सकते हैं। निम्नलिखित कलनविधि को द्विआधारी खोज वृक्ष के लिए सामान्यीकृत किया गया है, लेकिन यही विचार अन्य प्रारूपों के वृक्ष पर भी लागू किया जा सकता है। | ||
====पुनरावर्ती==== | ====पुनरावर्ती==== | ||
खोज-पुनरावर्ती(कुंजी, | खोज-पुनरावर्ती(कुंजी, ग्रंथिकि) | ||
यदि | यदि ग्रंथिकि ''शून्य'' है | ||
वापसी '' EMPTY_TREE '' | वापसी '' EMPTY_TREE '' | ||
यदि कुंजी < | यदि कुंजी <ग्रंथिकि.कुंजी | ||
वापसी खोज-पुनरावर्ती(कुंजी, | वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.बाएं) | ||
अन्यथा यदि कुंजी > | अन्यथा यदि कुंजी > ग्रंथिकि.कुंजी | ||
वापसी खोज-पुनरावर्ती(कुंजी, | वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.दायाँ) | ||
अन्य | अन्य | ||
वापसी | वापसी ग्रंथिकि | ||
====पुनरावृत्तीय==== | ====पुनरावृत्तीय==== | ||
searchIterative (कुंजी, | searchIterative (कुंजी, ग्रंथिकि) | ||
करंटग्रंथिकि:=ग्रंथिकि | |||
जबकि currentNode ''NULL'' नहीं है | जबकि currentNode ''NULL'' नहीं है | ||
यदि currentNode.key = key | यदि currentNode.key = key | ||
वर्तमानग्रंथिकि लौटाएँ | |||
अन्यथा यदि currentNode.key > कुंजी | अन्यथा यदि currentNode.key > कुंजी | ||
currentNodeN:= currentNode.left | |||
अन्य | अन्य | ||
currentNoden:= currentNode.right | |||
===न्यूनतम और अधिकतम=== | ==== न्यूनतम और अधिकतम की खोज ==== | ||
एक क्रमबद्ध | एक क्रमबद्ध वृक्ष में, न्यूनतम बाईं ओर के ग्रंथिकि पर स्थित होता है, जबकि अधिकतम दाईं ओर के ग्रंथिकि पर स्थित होता है।<ref>Gildea, Dan (2004). [http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf "Binary Search Tree"]</ref> | ||
====न्यूनतम==== | ====न्यूनतम==== | ||
न्यूनतम खोजें( | न्यूनतम खोजें(ग्रंथिकि) | ||
यदि | यदि ग्रंथिकि ''शून्य'' है | ||
वापसी '' EMPTY_TREE '' | वापसी '' EMPTY_TREE '' | ||
न्यूनतम:= | न्यूनतम:=ग्रंथिकि | ||
जबकि min.left ''शून्य'' नहीं है | जबकि min.left ''शून्य'' नहीं है | ||
मिनट�:= मिनट बाएँ | |||
वापसी min.key | वापसी min.key | ||
====अधिकतम==== | ====अधिकतम==== | ||
अधिकतम खोजें( | अधिकतम खोजें(ग्रंथिकि) | ||
यदि | यदि ग्रंथिकि ''शून्य'' है | ||
वापसी '' EMPTY_TREE '' | वापसी '' EMPTY_TREE '' | ||
अधिकतम�:= ग्रंथिकि | |||
जबकि max.right ''शून्य'' नहीं है | जबकि max.right ''शून्य'' नहीं है | ||
अधिकतम�:= अधिकतम.सही | |||
अधिकतम कुंजी लौटाएँ | अधिकतम कुंजी लौटाएँ | ||
==यह भी देखें== | ==यह भी देखें== | ||
* [[प्रयास करें]] | * [[प्रयास करें]] | ||
* [[ बाइनरी वृक्ष ]] | * [[ बाइनरी वृक्ष | द्विआधारी वृक्ष]] | ||
* [[गहराई-पहली खोज]] | * [[गहराई-पहली खोज]] | ||
Revision as of 18:45, 15 July 2023
अभिकलित्र विज्ञान में, एक खोज वृक्ष एक वृक्ष आँकड़ा संरचना है जिसका उपयोग एक सेट के भीतर से विशिष्ट कुंजियों का पता लगाने के लिए किया जाता है। किसी वृक्ष को खोज वृक्ष के रूप में कार्य करने के लिए, प्रत्येक ग्रंथिकि की कुंजी बाईं ओर के उप-वृक्षों में किसी भी कुंजी से बड़ी होनी चाहिए, और दाईं ओर उप-वृक्षों में किसी भी कुंजी से कम होनी चाहिए।[1] खोज वृक्षों का लाभ उनका कुशल खोज समय है, क्योंकि वृक्ष यथोचित रूप से संतुलित है, जिसका अर्थ है कि वृक्ष आंकड़ा संरचना # दोनों छोर पर वृक्षों में उपयोग की जाने वाली शब्दावली तुलनीय गहराई की हैं। विभिन्न खोज-वृक्ष आंकड़ा संरचनाएं मौजूद हैं, जिनमें से कई तत्वों को कुशल रूप से सम्मिलित करने और हटाने की भी अनुमति देती हैं, जिसके संचालन के लिए वृक्ष संतुलन बनाए रखना होता है।
खोज वृक्षों का उपयोग अक्सर सहयोगी सरणी को लागू करने के लिए किया जाता है। खोज वृक्ष कलनविधि किसी स्थान को ढूंढने के लिए विशेषता कुंजी-मूल्य जोड़ी से कुंजी का उपयोग करता है, और फिर अनुप्रयोग उस विशेष स्थान पर संपूर्ण कुंजी-मूल्य जोड़ी को संग्रहीत करता है।
वृक्षों के प्रकार
द्विआधारी खोज वृक्ष
द्विआधारी खोज वृक्ष एक ग्रंथिकि-आधारित आंकड़ा संरचना है जहां प्रत्येक ग्रंथिकि में एक कुंजी और दो उपवृक्ष, बाएँ और दाएँ होते हैं। सभी ग्रंथिकि के लिए, बाएं उपवृक्ष की कुंजी ग्रंथिकि की कुंजी से कम होनी चाहिए, और दाएं उपवृक्ष की कुंजी ग्रंथिकि की कुंजी से बड़ी होनी चाहिए। इन सभी उपवृक्षों को द्विआधारी खोज वृक्षों के रूप में योग्य होना चाहिए।
द्विआधारी खोज वृक्ष को खोजने के लिए सबसे खराब स्थिति वाली समय जटिलता वृक्षों में प्रयुक्त वृक्ष (आंकड़ा संरचना)#शब्दावली है, जो एन तत्वों वाले वृक्ष के लिए ओ (लॉग एन) जितनी छोटी हो सकती है।
बी-वृक्ष
बी-वृक्ष द्विआधारी खोज वृक्ष का सामान्यीकरण है जिसमें प्रत्येक ग्रंथिकि पर उपवृक्ष की एक चर संख्या हो सकती है। जबकि अपत्य-ग्रंथिकि की एक पूर्व-निर्धारित सीमा होती है, वे आवश्यक रूप से आंकड़ा से भरे नहीं होंगे, जिसका अर्थ है कि बी-वृक्ष संभावित रूप से कुछ स्थान बर्बाद कर सकते हैं। फायदा यह है कि बी-वृक्ष को अन्य स्व-संतुलन द्विआधारी खोज वृक्ष की तरह बार-बार पुन: संतुलित करने की आवश्यकता नहीं होती है।
उनकी ग्रंथिकि लंबाई की परिवर्तनशील सीमा के कारण, बी-वृक्ष को उन प्रणालियों के लिए अनुकूलित किया जाता है जो आंकड़े के बड़े ब्लॉक को पढ़ते हैं, इनका उपयोग आमतौर पर आंकड़ाबेस में भी किया जाता है।
बी-वृक्ष खोजने के लिए समय जटिलता ओ(लॉग एन) है।
(ए,बी)-वृक्ष
एक (ए,बी)-वृक्ष एक खोज वृक्ष है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक ग्रंथिकि में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि रूट में कम से कम 2 बच्चे और अधिकतम बी बच्चे होते हैं।
ए और बी को निम्नलिखित सूत्र से तय किया जा सकता है:[2]
(ए,बी)-वृक्ष को खोजने के लिए समय जटिलता ओ(लॉग एन) है।
त्रयी खोज वृक्ष
त्रयी खोज वृक्ष एक प्रकार का वृक्ष (आंकड़ा संरचना) है जिसमें 3 ग्रंथिकि हो सकते हैं: एक निम्न बच्चा, एक समान बच्चा और एक उच्च बच्चा। प्रत्येक ग्रंथिकि एक एकल वर्ण संग्रहीत करता है और संभावित तीसरे ग्रंथिकि के अपवाद के साथ, वृक्ष को उसी तरह से क्रमबद्ध किया जाता है जैसे द्विआधारी खोज वृक्ष होता है।
त्रयी खोज वृक्ष की खोज में यह जांचने के लिए एक स्ट्रिंग (अभिकलित्र विज्ञान) को पार करना शामिल है कि क्या किसी पथ में यह शामिल है।
एक संतुलित टर्नरी खोज वृक्ष की खोज के लिए समय जटिलता ओ(लॉग एन) है।
कलनविधि खोजना
किसी विशिष्ट कुंजी की खोज
यह मानते हुए कि वृक्ष का ऑर्डर दिया गया है, हम एक चाबी ले सकते हैं और उसे वृक्ष के भीतर ढूंढने का प्रयास कर सकते हैं। निम्नलिखित कलनविधि को द्विआधारी खोज वृक्ष के लिए सामान्यीकृत किया गया है, लेकिन यही विचार अन्य प्रारूपों के वृक्ष पर भी लागू किया जा सकता है।
पुनरावर्ती
खोज-पुनरावर्ती(कुंजी, ग्रंथिकि)
यदि ग्रंथिकि शून्य है
वापसी EMPTY_TREE
यदि कुंजी <ग्रंथिकि.कुंजी
वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.बाएं)
अन्यथा यदि कुंजी > ग्रंथिकि.कुंजी
वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.दायाँ)
अन्य
वापसी ग्रंथिकि
पुनरावृत्तीय
searchIterative (कुंजी, ग्रंथिकि)
करंटग्रंथिकि:=ग्रंथिकि
जबकि currentNode NULL नहीं है
यदि currentNode.key = key
वर्तमानग्रंथिकि लौटाएँ
अन्यथा यदि currentNode.key > कुंजी
currentNodeN:= currentNode.left
अन्य
currentNoden:= currentNode.right
न्यूनतम और अधिकतम की खोज
एक क्रमबद्ध वृक्ष में, न्यूनतम बाईं ओर के ग्रंथिकि पर स्थित होता है, जबकि अधिकतम दाईं ओर के ग्रंथिकि पर स्थित होता है।[3]
न्यूनतम
न्यूनतम खोजें(ग्रंथिकि)
यदि ग्रंथिकि शून्य है
वापसी EMPTY_TREE
न्यूनतम:=ग्रंथिकि
जबकि min.left शून्य नहीं है
मिनट�:= मिनट बाएँ
वापसी min.key
अधिकतम
अधिकतम खोजें(ग्रंथिकि)
यदि ग्रंथिकि शून्य है
वापसी EMPTY_TREE
अधिकतम�:= ग्रंथिकि
जबकि max.right शून्य नहीं है
अधिकतम�:= अधिकतम.सही
अधिकतम कुंजी लौटाएँ
यह भी देखें
संदर्भ
- ↑ Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures
- ↑ Toal, Ray. "(a,b) Trees"
- ↑ Gildea, Dan (2004). "Binary Search Tree"
