सर्च ट्री

Not to be confused with tree search.

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

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

वृक्षों के प्रकार

द्विआधारी खोज वृक्ष

द्विआधारी खोज वृक्ष

Main article: द्विआधारी खोज वृक्ष

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

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

बी-वृक्ष

Main article: बी-वृक्ष

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

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

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

(ए,बी)-वृक्ष

Main article: (ए,बी)-वृक्ष

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

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

$2\leq a\leq {\frac {(b+1)}{2}}$ (ए,बी)-वृक्ष को खोजने के लिए समय जटिलता ओ(लॉग एन) है।

त्रयी खोज वृक्ष

Main article: त्रयी खोज वृक्ष

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

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

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

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

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

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

पुनरावर्ती

खोज-पुनरावर्ती(कुंजी, ग्रंथिकि)
    यदि ग्रंथिकि शून्य है
        वापसी  EMPTY_TREE 
    यदि कुंजी <ग्रंथिकि.कुंजी
        वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.बाएं)
    अन्यथा यदि कुंजी > ग्रंथिकि.कुंजी
        वापसी खोज-पुनरावर्ती(कुंजी, ग्रंथिकि.दायाँ)
    अन्य
        वापसी ग्रंथिकि

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

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

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

एक क्रमबद्ध वृक्ष में, न्यूनतम बाईं ओर के ग्रंथिकि पर स्थित होता है, जबकि अधिकतम दाईं ओर के ग्रंथिकि पर स्थित होता है।

न्यूनतम

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

अधिकतम

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

यह भी देखें

• प्रयास करें
• द्विआधारी वृक्ष
• गहराई-पहली खोज