खोज पेड़

Not to be confused with tree search.

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

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

पेड़ों के प्रकार

बाइनरी सर्च ट्री

बाइनरी सर्च ट्री

Main article: Binary search tree

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

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

बी-ट्री

Main article: B-tree

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

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

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

(ए, बी) - पेड़

Main article: (a,b)-tree

An (a,b)-ट्री एक सर्च ट्री है जहां इसकी सभी पत्तियाँ समान गहराई वाली होती हैं। प्रत्येक नोड में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि जड़ में कम से कम 2 बच्चे और अधिकतम बी बच्चे होते हैं।

a और b को निम्न सूत्र से तय किया जा सकता है:

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

त्रिगुट खोज वृक्ष

Main article: Ternary search tree

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

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

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

खोज एल्गोरिदम

एक विशिष्ट कुंजी के लिए खोज

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

रिकर्सिव

खोज-पुनरावर्ती (कुंजी, नोड)
    यदि नोड नल है
        वापसी EMPTY_TREE
    अगर कुंजी <नोड.की
        वापसी खोज-पुनरावर्ती (कुंजी, नोड.लेफ्ट)
    और अगर कुंजी> नोड.की
        वापसी खोज-पुनरावर्ती (कुंजी, नोड.राइट)
    अन्य
        वापसी नोड

पुनरावृत्त

searchIterative (कुंजी, नोड)
    वर्तमान नोड: = नोड
    जबकि वर्तमान नोड नल नहीं है
        अगर currentNode.key = key
            वर्तमान नोड लौटाएं
        वरना अगर currentNode.key > key
            वर्तमान नोड: = वर्तमान नोड। बाएं
        अन्य
            करेंटनोड := करेंटनोड.राइट

=== न्यूनतम और अधिकतम === के लिए खोज एक सॉर्ट किए गए पेड़ में, न्यूनतम नोड सबसे बाईं ओर स्थित होता है, जबकि अधिकतम नोड सबसे दाईं ओर स्थित होता है।

न्यूनतम

न्यूनतम खोजें (नोड)
    यदि नोड नल है
        वापसी EMPTY_TREE
    न्यूनतम: = नोड
    जबकि min.left NULL नहीं है
        मिन := मिन.लेफ्ट
    वापसी min.key

अधिकतम

अधिकतम खोजें (नोड)
    यदि नोड नल है
        वापसी EMPTY_TREE
    मैक्स: = नोड
    जबकि max.right NULL नहीं है
        मैक्स := मैक्स.राइट
    वापसी max.key

यह भी देखें

• ट्राई करें
• बाइनरी ट्री
• गहराई-पहली खोज