सर्च ट्री: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(5 intermediate revisions by 4 users not shown)
Line 1: Line 1:
{{Short description|Data structure in tree form sorted for fast lookup}}
{{Short description|Data structure in tree form sorted for fast lookup}}
{{Distinguish|खोज वृक्ष}}
{{Distinguish|सर्च ट्री}}


[[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>
[[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|(ए,बी)-वृक्ष}}
{{Main|(ए,बी)-ट्री}}


एक (ए,बी)-वृक्ष एक खोज वृक्ष है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक ग्रंथिकि में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि रूट में कम से कम 2 बच्चे और अधिकतम बी बच्चे होते हैं।
एक (ए,बी)-ट्री एक सर्च ट्री है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक ग्रंथिकि में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि रूट में कम से कम 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|त्रयी खोज वृक्ष}}
{{Main|त्रयी सर्च ट्री}}


त्रयी खोज वृक्ष एक प्रकार का वृक्ष (आंकड़ा संरचना) है जिसमें 3 ग्रंथिकि हो सकते हैं: एक निम्न बच्चा, एक समान बच्चा और एक उच्च बच्चा। प्रत्येक ग्रंथिकि एक एकल वर्ण संग्रहीत करता है और संभावित तीसरे ग्रंथिकि के अपवाद के साथ, वृक्ष को उसी तरह से क्रमबद्ध किया जाता है जैसे द्विआधारी खोज वृक्ष होता है।
त्रयी सर्च ट्री एक प्रकार का ट्री (आंकड़ा संरचना) है जिसमें 3 ग्रंथिकि हो सकते हैं: एक निम्न बच्चा, एक समान बच्चा और एक उच्च बच्चा। प्रत्येक ग्रंथिकि एक एकल वर्ण संग्रहीत करता है और संभावित तीसरे ग्रंथिकि के अपवाद के साथ, ट्री को उसी तरह से क्रमबद्ध किया जाता है जैसे द्विआधारी सर्च ट्री होता है।


त्रयी खोज वृक्ष की खोज में यह जांचने के लिए एक [[Index.php?title=स्ट्रिंग (अभिकलित्र विज्ञान)|स्ट्रिंग (अभिकलित्र विज्ञान)]] को पार करना शामिल है कि क्या किसी पथ में यह शामिल है।
त्रयी सर्च ट्री की खोज में यह जांचने के लिए एक [[Index.php?title=स्ट्रिंग (अभिकलित्र विज्ञान)|स्ट्रिंग (अभिकलित्र विज्ञान)]] को पार करना शामिल है कि क्या किसी पथ में यह शामिल है।


एक संतुलित टर्नरी खोज वृक्ष की खोज के लिए समय जटिलता ओ(लॉग एन) है।
एक संतुलित टर्नरी सर्च ट्री की खोज के लिए समय जटिलता ओ(लॉग एन) है।


==कलनविधि खोजना==
==कलनविधि खोजना==


===किसी विशिष्ट कुंजी की खोज===
===किसी विशिष्ट कुंजी की खोज===
यह मानते हुए कि वृक्ष का ऑर्डर दिया गया है, हम एक चाबी ले सकते हैं और उसे वृक्ष के भीतर ढूंढने का प्रयास कर सकते हैं। निम्नलिखित कलनविधि को द्विआधारी खोज वृक्ष के लिए सामान्यीकृत किया गया है, लेकिन यही विचार अन्य प्रारूपों के वृक्ष पर भी लागू किया जा सकता है।
यह मानते हुए कि ट्री का ऑर्डर दिया गया है, हम एक चाबी ले सकते हैं और उसे ट्री के भीतर ढूंढने का प्रयास कर सकते हैं। निम्नलिखित कलनविधि को द्विआधारी सर्च ट्री के लिए सामान्यीकृत किया गया है, लेकिन यही विचार अन्य प्रारूपों के ट्री पर भी लागू किया जा सकता है।


====पुनरावर्ती====
====पुनरावर्ती====
  खोज-पुनरावर्ती(कुंजी, ग्रंथिकि)
  खोsearch-recursive(key, node)
     यदि ग्रंथिकि ''शून्य'' है
 
         वापसी '' EMPTY_TREE ''
     '''if''' node is ''NULL''
     यदि कुंजी <ग्रंथिकि.कुंजी
         '''return''' ''EMPTY_TREE''
         वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.बाएं)
     '''if''' key < node.key
     अन्यथा यदि कुंजी > ग्रंथिकि.कुंजी
         return search-recursive(key, node.left)
         वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.दायाँ)
     '''else if''' key > node.key
     अन्य
         return search-recursive(key, node.right)
         वापसी ग्रंथिकि
     '''else'''
 
        '''return''' node
          


====पुनरावृत्तीय====
====पुनरावृत्तीय====
  searchIterative (कुंजी, ग्रंथिकि)
  searchIterative(key, node)
     करंटग्रंथिकि:=ग्रंथिकि
     currentNode := node
     जबकि currentNode ''NULL'' नहीं है
     '''while''' currentNode is not ''NULL''
         यदि currentNode.key = key
         '''if''' currentNode.key = key
             वर्तमानग्रंथिकि लौटाएँ
             '''return''' currentNode
         अन्यथा यदि currentNode.key > कुंजी
         '''else if''' currentNode.key > key
             currentNodeN:= currentNode.left
             currentNode := currentNode.left
         अन्य
         '''else'''
             currentNoden:= currentNode.right
 
             currentNode := currentNode.right


==== न्यूनतम और अधिकतम की खोज ====
==== न्यूनतम और अधिकतम की खोज ====
एक क्रमबद्ध वृक्ष में, न्यूनतम बाईं ओर के ग्रंथिकि पर स्थित होता है, जबकि अधिकतम दाईं ओर के ग्रंथिकि पर स्थित होता है।<ref>Gildea, Dan (2004). [http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf "Binary Search Tree"]</ref>
एक क्रमबद्ध ट्री में, न्यूनतम बाईं ओर के ग्रंथिकि पर स्थित होता है, जबकि अधिकतम दाईं ओर के ग्रंथिकि पर स्थित होता है।<ref>Gildea, Dan (2004). [http://www.cs.rochester.edu/~gildea/csc282/slides/C12-bst.pdf "Binary Search Tree"]</ref>




====न्यूनतम====
====न्यूनतम====
  न्यूनतम खोजें(ग्रंथिकि)
  findMinimum(node)
     यदि ग्रंथिकि ''शून्य'' है
     '''if''' node is ''NULL''
         वापसी '' EMPTY_TREE ''
         '''return''' ''EMPTY_TREE''
     न्यूनतम:=ग्रंथिकि
     min := node
     जबकि min.left ''शून्य'' नहीं है
     '''while''' min.left is not ''NULL''
         मिनट�:= मिनट बाएँ
         min := min.left
     वापसी min.key
 
     '''return''' min.key


====अधिकतम====
====अधिकतम====
  अधिकतम खोजें(ग्रंथिकि)
  findMaximum(node)
     यदि ग्रंथिकि ''शून्य'' है
     '''if''' node is ''NULL''
         वापसी '' EMPTY_TREE ''
         '''return''' ''EMPTY_TREE''
     अधिकतम�:= ग्रंथिकि
     max := node
     जबकि max.right ''शून्य'' नहीं है
     '''while''' max.right is not ''NULL''
         अधिकतम�:= अधिकतम.सही
         max := max.right
     अधिकतम कुंजी लौटाएँ
 
     '''return''' max.key


==यह भी देखें==
==यह भी देखें==
* [[प्रयास करें]]
* [[प्रयास करें]]
* [[ बाइनरी वृक्ष | द्विआधारी वृक्ष]]
* [[ बाइनरी वृक्ष | द्विआधारी ट्री]]
* [[गहराई-पहली खोज]]
* [[गहराई-पहली खोज]]


Line 106: Line 112:
{{Authority control}}
{{Authority control}}


{{DEFAULTSORT:Search Tree}}[[Category: पेड़ खोजें]] [[Category: एल्गोरिदम खोजें]]
{{DEFAULTSORT:Search Tree}}
 
 


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Search Tree]]
[[Category:Created On 10/07/2023]]
[[Category:Collapse templates|Search Tree]]
[[Category:Created On 10/07/2023|Search Tree]]
[[Category:Lua-based templates|Search Tree]]
[[Category:Machine Translated Page|Search Tree]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Search Tree]]
[[Category:Pages with script errors|Search Tree]]
[[Category:Sidebars with styles needing conversion|Search Tree]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Search Tree]]
[[Category:Templates generating microformats|Search Tree]]
[[Category:Templates that add a tracking category|Search Tree]]
[[Category:Templates that are not mobile friendly|Search Tree]]
[[Category:Templates that generate short descriptions|Search Tree]]
[[Category:Templates using TemplateData|Search Tree]]
[[Category:Wikipedia metatemplates|Search Tree]]
[[Category:एल्गोरिदम खोजें|Search Tree]]
[[Category:पेड़ खोजें|Search Tree]]

Latest revision as of 13:54, 28 July 2023

Not to be confused with सर्च ट्री.

अभिकलित्र विज्ञान में, एक सर्च ट्री एक ट्री आँकड़ा संरचना है जिसका उपयोग एक सेट के भीतर से विशिष्ट कुंजियों का पता लगाने के लिए किया जाता है। किसी ट्री को सर्च ट्री के रूप में कार्य करने के लिए, प्रत्येक ग्रंथिकि की कुंजी बाईं ओर के उप-ट्री में किसी भी कुंजी से बड़ी होनी चाहिए, और दाईं ओर उप-ट्री में किसी भी कुंजी से कम होनी चाहिए।[1] सर्च ट्री का लाभ उनका कुशल खोज समय है, क्योंकि ट्री यथोचित रूप से संतुलित है, जिसका अर्थ है कि ट्री आंकड़ा संरचना # दोनों छोर पर ट्री में उपयोग की जाने वाली शब्दावली तुलनीय गहराई की हैं। विभिन्न खोज-ट्री आंकड़ा संरचनाएं मौजूद हैं, जिनमें से कई तत्वों को कुशल रूप से सम्मिलित करने और हटाने की भी अनुमति देती हैं, जिसके संचालन के लिए ट्री संतुलन बनाए रखना होता है।

सर्च ट्री का उपयोग अक्सर सहयोगी सरणी को लागू करने के लिए किया जाता है। सर्च ट्री कलनविधि किसी स्थान को ढूंढने के लिए विशेषता कुंजी-मूल्य जोड़ी से कुंजी का उपयोग करता है, और फिर अनुप्रयोग उस विशेष स्थान पर संपूर्ण कुंजी-मूल्य जोड़ी को संग्रहीत करता है।

ट्री के प्रकार

Binary search tree
द्विआधारी सर्च ट्री

द्विआधारी सर्च ट्री

Main article: द्विआधारी सर्च ट्री

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

द्विआधारी सर्च ट्री को खोजने के लिए सबसे खराब स्थिति वाली समय जटिलता ट्री में प्रयुक्त ट्री (आंकड़ा संरचना)#शब्दावली है, जो एन तत्वों वाले ट्री के लिए ओ (लॉग एन) जितनी छोटी हो सकती है।

बी-ट्री

Main article: बी-ट्री

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

उनकी ग्रंथिकि लंबाई की परिवर्तनशील सीमा के कारण, बी-ट्री को उन प्रणालियों के लिए अनुकूलित किया जाता है जो आंकड़े के बड़े ब्लॉक को पढ़ते हैं, इनका उपयोग आमतौर पर आंकड़ाबेस में भी किया जाता है।

बी-ट्री खोजने के लिए समय जटिलता ओ(लॉग एन) है।

(ए,बी)-ट्री

Main article: (ए,बी)-ट्री

एक (ए,बी)-ट्री एक सर्च ट्री है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक ग्रंथिकि में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि रूट में कम से कम 2 बच्चे और अधिकतम बी बच्चे होते हैं।

ए और बी को निम्नलिखित सूत्र से तय किया जा सकता है:[2]

(ए,बी)-ट्री को खोजने के लिए समय जटिलता ओ(लॉग एन) है।

त्रयी सर्च ट्री

Main article: त्रयी सर्च ट्री

त्रयी सर्च ट्री एक प्रकार का ट्री (आंकड़ा संरचना) है जिसमें 3 ग्रंथिकि हो सकते हैं: एक निम्न बच्चा, एक समान बच्चा और एक उच्च बच्चा। प्रत्येक ग्रंथिकि एक एकल वर्ण संग्रहीत करता है और संभावित तीसरे ग्रंथिकि के अपवाद के साथ, ट्री को उसी तरह से क्रमबद्ध किया जाता है जैसे द्विआधारी सर्च ट्री होता है।

त्रयी सर्च ट्री की खोज में यह जांचने के लिए एक स्ट्रिंग (अभिकलित्र विज्ञान) को पार करना शामिल है कि क्या किसी पथ में यह शामिल है।

एक संतुलित टर्नरी सर्च ट्री की खोज के लिए समय जटिलता ओ(लॉग एन) है।

कलनविधि खोजना

किसी विशिष्ट कुंजी की खोज

यह मानते हुए कि ट्री का ऑर्डर दिया गया है, हम एक चाबी ले सकते हैं और उसे ट्री के भीतर ढूंढने का प्रयास कर सकते हैं। निम्नलिखित कलनविधि को द्विआधारी सर्च ट्री के लिए सामान्यीकृत किया गया है, लेकिन यही विचार अन्य प्रारूपों के ट्री पर भी लागू किया जा सकता है।

पुनरावर्ती

खोsearch-recursive(key, node)

    if node is NULL
        return EMPTY_TREE
    if key < node.key
        return search-recursive(key, node.left)
    else if key > node.key
        return search-recursive(key, node.right)
    else

        return node

पुनरावृत्तीय

searchIterative(key, node)
    currentNode := node
    while currentNode is not NULL
        if currentNode.key = key
            return currentNode
        else if currentNode.key > key
            currentNode := currentNode.left
        else

            currentNode := currentNode.right

न्यूनतम और अधिकतम की खोज

एक क्रमबद्ध ट्री में, न्यूनतम बाईं ओर के ग्रंथिकि पर स्थित होता है, जबकि अधिकतम दाईं ओर के ग्रंथिकि पर स्थित होता है।[3]


न्यूनतम

findMinimum(node)
    if node is NULL
        return EMPTY_TREE
    min := node
    while min.left is not NULL
        min := min.left

    return min.key

अधिकतम

findMaximum(node)
    if node is NULL
        return EMPTY_TREE
    max := node
    while max.right is not NULL
        max := max.right

    return max.key

यह भी देखें

संदर्भ

  1. ↑ Black, Paul and Pieterse, Vreda (2005). "search tree". Dictionary of Algorithms and Data Structures
  2. ↑ Toal, Ray. "(a,b) Trees"
  3. ↑ Gildea, Dan (2004). "Binary Search Tree"
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=सर्च_ट्री&oldid=229219’