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