बाइनरी सर्च ट्री
कम्प्यूटर विज्ञान में बाइनरी सर्च ट्री (बीसटी) एक ऐसा बाइनरी ट्री है जो की रूटेड बाइनरी ट्री है और जिसके नोड की वैल्यू उसके लेफ्ट सुब्त्री से ज़्यादा होती है और राइट सुब्त्री से काम होती हैं। बाइनरी सर्च ट्री एक प्रकार का डाटा स्ट्रक्चर है, जिसे डाटा जैसे की नंबर्स स्टोर करने के लिए इस्तेमाल किया जाता हैं। बाइनरी सर्च ट्री बाइनरी सर्च को डेटा आइटमों को तेजी से देखने, जोड़ने और हटाने के लिए अनुमति देते हैं और इसका उपयोग डायनामिक सेट और लुकअप टेबल को लागू करने के लिए किया जाता है । एक बीएसटी में नोड्स के आदेश के वजह से प्रत्येक तुलना शेष पेड़ के लगभग आधे हिस्से में आती है, इसलिए पूरे लुकअप का समय बाइनरी लॉगरिदम के समानुपाती होता है । यह एक (अनसुलझी) सरणी में कुंजी द्वारा आइटम खोजने के लिए आवश्यक रैखिक समय से बहुत बेहतर हैं।
परिभाषा
एक द्विआधारी खोज पेड़ एक जड़ बाइनरी पेड़ है, जिसके प्रत्येक आंतरिक नोड्स एक कुंजी स्टोर करते हैं, और प्रत्येक नोड के दो अलग-अलग उप-वृक्ष हैं, जिन्हें आमतौर पर बाएं और दाएं दर्शाया जाता है। यह वृक्ष अतिरिक्त रूप से द्विआधारी खोज संपत्ति को पूरा करता है जो की कहता है, प्रत्येक नोड में कुंजी बाईं उप-ट्री में संग्रहीत किसी भी कुंजी से अधिक या बराबर होती है, और दाहिने उप-ट्री में संग्रहीत किसी भी कुंजी से कम या बराबर होती हैं।[१] यह पेड़ की पत्तियों (अंतिम नोड्स) में कोई कुंजी नहीं होती है और उन्हें एक दूसरे से अलग करने के लिए कोई संरचना नहीं होती है।
बाइनरी सर्च ट्री का अन्य डेटा संरचनाओं पर प्रमुख लाभ यह है कि संबंधित सॉर्टिंग एल्गोरिदम और खोज एल्गोरिदम जैसे कि इन-ऑर्डर ट्रैवर्सल बहुत तेज हो जाते हैं, उन्हें कोड करना भी आसान हो जाता है।
ऑपरेशन्स
द्विआधारी खोज पेड़ तीन मुख्य कार्य करते हैं, जो की हैं, तत्वों का सम्मिलन, विलोपन और लुकअप (यह देखना कि क्या कुंजी मौजूद है)।
खोज:
हम खोज शुरू करते हैं कि क्या पेड़ शून्य है, तो कुंजी पेड़ में मौजूद नहीं है। फिर अगर नहीं तोह, हम देखते हैं कि कुंजी रूट नोड के बराबर है, यदि हां तो हमारे पास रूट नोड के रूप में उत्तर है। यदि नहीं, तो हम बाएं और दाएं उपप्रकारों में खोज करते हैं [२]।यदि कुंजी का मान रूट नोड के मान से कम है, तो हम बाईं सबट्री में पुनरावर्ती खोज करते हैं और यदि यह इसके मूल्य से अधिक है, तो हम दाए उपप्रकार में खोज करते हैं।यह प्रक्रिया तब तक दोहराई जाती है जब तक कि कुंजी नहीं मिल जाती या पूरे पेड़ ख़तम नहीं हो जाता।
पाइथन में एक नमूना खोज कोड:
def search_recursively(key, node):
if node == None or node.key == key:
return node
if key < node.key:
return search_recursively(key, node.left)
if key > node.key:
return search_recursively(key, node.right)
इंसर्शन:
इंसर्शन शुरू होती है जैसे ही खोज शुरू होती हैं यदि कुंजी जड़ के बराबर नहीं है, तो हम पहले की तरह बाएं या दाएं सबट्री खोजते हैं। आखिरकार, हम एक बाहरी नोड तक पहुंच जाएंगे और नोड की कुंजी के आधार पर नए कुंजी-मूल्य जोड़ी को उसके दाएं या बाएं बच्चे के रूप में जोड़ देंगे।[३]
पाइथन में एक नमूना इंसर्शन कोड:
def binary_tree_insert(node, key, value):
if node == None:
return NodeTree(None, key, value, None)
if key == node.key:
return NodeTree(node.left, key, value, node.right)
if key < node.key:
return NodeTree(binary_tree_insert(node.left, key, value), node.key, node.value, node.right)
return NodeTree(node.left, node.key, node.value, binary_tree_insert(node.right, key, value))
ट्रेवेर्सल:
इनॉरडेर ट्रेवेर्सल बाइनरी सर्च ट्री के सारे नोड्स को सॉर्टेड आर्डर में देता है इससलए वह सबसे अच्छा ट्रेवेर्सल माना जाता ह। इसे पहले रूट के पूरे बाएँ उप-भाग के माध्यम से पुनरावृत्ति करते हुए और फिर पुन: रूट के माध्यम से दाईं सबट्री पर जाकर किया जा सकता है।
पाइथन में एक नमूना ट्रेवेर्सल का कोड:
def traverse_binary_tree(node, callback):
if node == None:
return
traverse_binary_tree(node.leftChild, callback)
callback(node.value)
traverse_binary_tree(node.rightChild, callback)