सर्च ट्री
कंप्यूटर विज्ञान में, एक खोज वृक्ष एक वृक्ष डेटा संरचना है जिसका उपयोग एक सेट के भीतर से विशिष्ट कुंजियों का पता लगाने के लिए किया जाता है। किसी ट्री को खोज ट्री के रूप में कार्य करने के लिए, प्रत्येक नोड की कुंजी बाईं ओर के उप-वृक्षों में किसी भी कुंजी से बड़ी होनी चाहिए, और दाईं ओर उप-वृक्षों में किसी भी कुंजी से कम होनी चाहिए।[1] खोज वृक्षों का लाभ उनका कुशल खोज समय है, क्योंकि वृक्ष यथोचित रूप से संतुलित है, जिसका अर्थ है कि वृक्ष डेटा संरचना # दोनों छोर पर वृक्षों में उपयोग की जाने वाली शब्दावली तुलनीय गहराई की हैं। विभिन्न खोज-ट्री डेटा संरचनाएं मौजूद हैं, जिनमें से कई तत्वों को कुशल रूप से सम्मिलित करने और हटाने की भी अनुमति देती हैं, जिसके संचालन के लिए ट्री संतुलन बनाए रखना होता है।
खोज वृक्षों का उपयोग अक्सर सहयोगी सरणी को लागू करने के लिए किया जाता है। खोज ट्री एल्गोरिदम किसी स्थान को ढूंढने के लिए विशेषता-मूल्य जोड़ी | कुंजी-मूल्य जोड़ी से कुंजी का उपयोग करता है, और फिर एप्लिकेशन उस विशेष स्थान पर संपूर्ण कुंजी-मूल्य जोड़ी को संग्रहीत करता है।
पेड़ों के प्रकार
बाइनरी सर्च ट्री
बाइनरी सर्च ट्री एक नोड-आधारित डेटा संरचना है जहां प्रत्येक नोड में एक कुंजी और दो उपट्री, बाएँ और दाएँ होते हैं। सभी नोड्स के लिए, बाएं सबट्री की कुंजी नोड की कुंजी से कम होनी चाहिए, और दाएं सबट्री की कुंजी नोड की कुंजी से बड़ी होनी चाहिए। इन सभी उपवृक्षों को बाइनरी खोज वृक्षों के रूप में योग्य होना चाहिए।
बाइनरी सर्च ट्री को खोजने के लिए सबसे खराब स्थिति वाली समय जटिलता पेड़ों में प्रयुक्त ट्री (डेटा संरचना)#शब्दावली है, जो एन तत्वों वाले पेड़ के लिए ओ (लॉग एन) जितनी छोटी हो सकती है।
बी-वृक्ष
बी-ट्री बाइनरी सर्च ट्री का सामान्यीकरण है जिसमें प्रत्येक नोड पर उपट्री की एक चर संख्या हो सकती है। जबकि चाइल्ड-नोड्स की एक पूर्व-निर्धारित सीमा होती है, वे आवश्यक रूप से डेटा से भरे नहीं होंगे, जिसका अर्थ है कि बी-ट्री संभावित रूप से कुछ स्थान बर्बाद कर सकते हैं। फायदा यह है कि बी-पेड़ों को अन्य स्व-संतुलन द्विआधारी खोज वृक्ष |सेल्फ-बैलेंसिंग पेड़ों की तरह बार-बार पुन: संतुलित करने की आवश्यकता नहीं होती है।
उनकी नोड लंबाई की परिवर्तनशील सीमा के कारण, बी-ट्री को उन प्रणालियों के लिए अनुकूलित किया जाता है जो डेटा के बड़े ब्लॉक को पढ़ते हैं, इनका उपयोग आमतौर पर डेटाबेस में भी किया जाता है।
बी-ट्री खोजने के लिए समय जटिलता O(लॉग एन) है।
(ए,बी)-पेड़
एक (ए,बी)-वृक्ष एक खोज वृक्ष है जिसकी सभी पत्तियाँ समान गहराई की होती हैं। प्रत्येक नोड में कम से कम एक बच्चे और अधिकतम बी बच्चे होते हैं, जबकि रूट में कम से कम 2 बच्चे और अधिकतम बी बच्चे होते हैं।
ए और बी को निम्नलिखित सूत्र से तय किया जा सकता है:[2]
(ए,बी)-ट्री को खोजने के लिए समय जटिलता O(लॉग एन) है।
टर्नरी खोज वृक्ष
टर्नरी सर्च ट्री एक प्रकार का ट्री (डेटा संरचना) है जिसमें 3 नोड हो सकते हैं: एक निम्न बच्चा, एक समान बच्चा और एक उच्च बच्चा। प्रत्येक नोड एक एकल वर्ण संग्रहीत करता है और संभावित तीसरे नोड के अपवाद के साथ, पेड़ को उसी तरह से क्रमबद्ध किया जाता है जैसे बाइनरी खोज पेड़ होता है।
टर्नरी सर्च ट्री की खोज में यह जांचने के लिए एक स्ट्रिंग (कंप्यूटर विज्ञान) को पार करना शामिल है कि क्या किसी पथ में यह शामिल है।
एक संतुलित टर्नरी खोज वृक्ष की खोज के लिए समय जटिलता O(लॉग एन) है।
एल्गोरिदम खोजना
किसी विशिष्ट कुंजी की खोज
यह मानते हुए कि पेड़ का ऑर्डर दिया गया है, हम एक चाबी ले सकते हैं और उसे पेड़ के भीतर ढूंढने का प्रयास कर सकते हैं। निम्नलिखित एल्गोरिदम को बाइनरी सर्च ट्री के लिए सामान्यीकृत किया गया है, लेकिन यही विचार अन्य प्रारूपों के ट्री पर भी लागू किया जा सकता है।
पुनरावर्ती
खोज-पुनरावर्ती(कुंजी, नोड)
यदि नोड शून्य है
वापसी EMPTY_TREE
यदि कुंजी <नोड.कुंजी
वापसी खोज-पुनरावर्ती(कुंजी, नोड.बाएं)
अन्यथा यदि कुंजी > नोड.कुंजी
वापसी खोज-पुनरावर्ती(कुंजी, नोड.दायाँ)
अन्य
वापसी नोड
पुनरावृत्तीय
searchIterative (कुंजी, नोड)
करंटनोड:=नोड
जबकि currentNode NULL नहीं है
यदि currentNode.key = key
वर्तमाननोड लौटाएँ
अन्यथा यदि currentNode.key > कुंजी
currentNode := currentNode.left
अन्य
currentNode := 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"
