थ्रेडेड बाइनरी ट्री
कम्प्यूटिंग में, थ्रेडेड द्विआधारी वृक्ष बाइनरी ट्री वैरिएंट है जो विशेष क्रम में वृक्ष परिभ्रमण की सुविधा देता है (अक्सर वही क्रम जो पहले से ही ट्री के लिए परिभाषित है)।
एक संपूर्ण बाइनरी सर्च ट्री को मुख्य कुंजी के क्रम में आसानी से पार किया जा सकता है, लेकिन नोड (कंप्यूटर विज्ञान) को केवल पॉइंटर (कंप्यूटर प्रोग्रामिंग) दिया जाता है, अगले आने वाले नोड को ढूंढना धीमा या असंभव हो सकता है। उदाहरण के लिए, परिभाषा के अनुसार लीफ नोड्स का कोई वंशज नहीं होता है, इसलिए लीफ नोड के लिए केवल सूचक दिए जाने पर किसी अन्य नोड तक नहीं पहुंचा जा सकता है। थ्रेडेड ट्री कुछ या सभी नोड्स में अतिरिक्त जानकारी जोड़ता है, ताकि किसी भी एकल नोड के लिए अगला नोड जल्दी से पाया जा सके, जिससे रिकर्सन के बिना ट्री ट्रैवर्सल और रिकर्सन के लिए आवश्यक अतिरिक्त भंडारण (पेड़ की गहराई के आनुपातिक) की अनुमति मिलती है।
थ्रेडिंग
एक बाइनरी ट्री को सभी दाएं चाइल्ड पॉइंटर्स बनाकर पिरोया जाता है जो आम तौर पर नोड के इन-ऑर्डर उत्तराधिकारी के लिए शून्य बिंदु होंगे ('यदि' यह मौजूद है), और सभी बाएं चाइल्ड पॉइंटर्स जो सामान्य रूप से नोड के इन-ऑर्डर पूर्ववर्ती के लिए शून्य बिंदु होंगे।[1]
यह मानता है कि ट्रैवर्सल क्रम पेड़ के इन-ऑर्डर ट्रैवर्सल|इन-ऑर्डर ट्रैवर्सल के समान है। हालाँकि, पॉइंटर्स को प्रतिस्थापित करने के बजाय (या इसके अतिरिक्त) ट्री नोड्स में जोड़ा जा सकता है। इस प्रकार परिभाषित लिंक्ड सूचियों को आमतौर पर थ्रेड्स भी कहा जाता है, और इसका उपयोग किसी भी वांछित क्रम में ट्रैवर्सल को सक्षम करने के लिए किया जा सकता है। उदाहरण के लिए, पेड़ जिसके नोड्स लोगों के बारे में जानकारी का प्रतिनिधित्व करते हैं, उन्हें नाम के आधार पर क्रमबद्ध किया जा सकता है, लेकिन जन्म तिथि, वजन या किसी अन्य ज्ञात विशेषता के क्रम में त्वरित ट्रैवर्सल की अनुमति देने वाले अतिरिक्त धागे होते हैं।
प्रेरणा
बाइनरी सर्च ट्री सहित (लेकिन इन्हीं तक सीमित नहीं) पेड़ों का उपयोग वस्तुओं को विशेष क्रम में संग्रहीत करने के लिए किया जा सकता है, जैसे कि प्रत्येक नोड में संग्रहीत कुछ संपत्ति का मूल्य, जिसे अक्सर कुंजी मान कहा जाता है। ऐसे पेड़ पर उपयोगी ऑपरेशन ट्रैवर्सल है: कुंजी के क्रम में सभी वस्तुओं पर जाना।
एक सरल पुनरावर्ती ट्रैवर्सल एल्गोरिदम जो बाइनरी सर्च ट्री के प्रत्येक नोड पर जाता है वह निम्नलिखित है। मान लीजिए t नोड के लिए सूचक है, या nil. यात्रा पर जाने वाले t का अर्थ नोड पर कोई भी क्रिया करना हो सकता है t या इसकी सामग्री.
एल्गोरिथम ट्रैवर्स(t):
- इनपुट: एक सूचक t एक नोड के लिए (या nil)
- अगर t = nil, वापस करना।
- अन्य:
- ट्रैवर्स (बाएं-बच्चे (t))
- मिलने जाना t
- ट्रैवर्स (राइट-चाइल्ड (t))
इस एल्गोरिदम के साथ समस्या यह है कि, इसकी पुनरावृत्ति के कारण, यह पेड़ की ऊंचाई के अनुपात में स्टैक स्पेस का उपयोग करता है। यदि पेड़ काफी संतुलित है, तो यह काफी है O(log n) पेड़ के लिए जगह जिसमें शामिल है nतत्व. सबसे खराब स्थिति में, जब पेड़ पथ ग्राफ का रूप लेता है, तो पेड़ की ऊंचाई होती है n तो एल्गोरिथ्म लेता है O(n) अंतरिक्ष। दूसरी समस्या यह है कि सभी ट्रैवर्सल मूल से शुरू होने चाहिए जब नोड्स में केवल उनके बच्चों के लिए पॉइंटर्स हों। किसी विशेष नोड के लिए पॉइंटर होना आम बात है, लेकिन जब तक थ्रेड पॉइंटर्स जैसी अतिरिक्त जानकारी नहीं जोड़ी जाती, तब तक वह बाकी पेड़ पर वापस जाने के लिए पर्याप्त नहीं है।
इस दृष्टिकोण में, यह बताना संभव नहीं हो सकता है कि किसी दिए गए नोड में बाएँ और/या दाएँ पॉइंटर वास्तव में बच्चों को इंगित करते हैं, या थ्रेडिंग का परिणाम हैं। यदि अंतर आवश्यक है, तो प्रत्येक नोड में बिट जोड़ना इसे रिकॉर्ड करने के लिए पर्याप्त है।
1968 की पाठ्यपुस्तक में, डोनाल्ड नुथ ने पूछा कि क्या इन-ऑर्डर ट्रैवर्सल के लिए गैर-पुनरावर्ती एल्गोरिदम मौजूद है, जो किसी स्टैक का उपयोग नहीं करता है और पेड़ को अपरिवर्तित छोड़ देता है।[2] इस समस्या का समाधान ट्री थ्रेडिंग है, जिसे जोसेफ एम. मॉरिस ने 1979 में प्रस्तुत किया था।[3][4] 1969 के अनुवर्ती संस्करण में,[5] नुथ ने थ्रेडेड ट्री प्रतिनिधित्व का श्रेय एलन पर्लिस और थॉर्नटन (1960) को दिया।[6]
मूल सूचकों से संबंध
समान लक्ष्यों को प्राप्त करने का दूसरा तरीका प्रत्येक नोड में उस नोड के मूल नोड में पॉइंटर शामिल करना है। यह देखते हुए, अगले नोड तक हमेशा पहुंचा जा सकता है। जब भी कोई सही बच्चे नहीं होते हैं तब भी सही संकेतक शून्य होते हैं। उस नोड से अगला नोड ढूंढने के लिए जिसका दायां पॉइंटर शून्य है, मूल पॉइंटर्स के माध्यम से तब तक चलें जब तक कि उस नोड तक न पहुंच जाएं जिसका दायां पॉइंटर शून्य नहीं है, और यह वह बच्चा नहीं है जहां से आप अभी आए हैं। वह नोड अगला नोड है, और उसके बाद उसके वंशज दाईं ओर आते हैं।
पैरेंट पॉइंटर्स या स्टैक के स्पष्ट उपयोग के बिना, थ्रेडेड बाइनरी ट्री से नोड के पैरेंट की खोज करना भी संभव है, हालांकि यह धीमा है। इसे देखने के लिए, दाएं चाइल्ड r के साथ नोड k पर विचार करें। फिर r का बायां सूचक या तो चाइल्ड होना चाहिए या k पर वापस थ्रेड होना चाहिए। ऐसे मामले में जब r का बायाँ बच्चा है, तो उस बाएँ बच्चे के पास या तो अपना बायाँ बच्चा होना चाहिए या k की ओर धागा होना चाहिए, और इसी तरह सभी क्रमिक बाएँ बच्चों के लिए। तो r से बाएँ सूचकों की श्रृंखला का अनुसरण करके, हम अंततः k की ओर इंगित करने वाला धागा पाएंगे। स्थिति सममित रूप से समान है जब q, p का बायाँ बच्चा है - हम q के दाएँ बच्चे का अनुसरण p की ओर इंगित करने वाले धागे तक कर सकते हैं।
पायथन (प्रोग्रामिंग भाषा) में:
def parent(node):
if node is node.tree.root:
return None
x = node
y = node
while True:
if is_thread(y):
p = y.right
if p is None or p.left is not node:
p = x
while not is_thread(p.left):
p = p.left
p = p.left
return p
elif is_thread(x):
p = x.left
if p is None or p.right is not node:
p = y
while not is_thread(p.right):
p = p.right
p = p.right
return p
x = x.left
y = y.right
प्रकार
- एकल थ्रेडेड: प्रत्येक नोड को या तो इन-ऑर्डर पूर्ववर्ती या उत्तराधिकारी (बाएं या दाएं) की ओर पिरोया गया है।
- डबल थ्रेडेड: प्रत्येक नोड को इन-ऑर्डर पूर्ववर्ती और उत्तराधिकारी (बाएं और दाएं) दोनों की ओर पिरोया गया है।
इन-ऑर्डर ट्रैवर्सल की सरणी
क्रम में ट्रैवर्सल के अनुसार थ्रेड्स नोड के पूर्ववर्तियों और उत्तराधिकारियों के संदर्भ हैं।
इनऑर्डर|थ्रेडेड ट्री का इन-ऑर्डर ट्रैवर्सल है A,B,C,D,E,F,G,H,I, का पूर्ववर्ती E है D, का उत्तराधिकारी E है F.
उदाहरण
आइए सामान्य बाइनरी ट्री से थ्रेडेड बाइनरी ट्री बनाएं:
उपरोक्त पेड़ के लिए इनऑर्डर|इन-ऑर्डर ट्रैवर्सल है - D B A E C. तो, संबंधित थ्रेडेड बाइनरी ट्री होगा -
शून्य लिंक
n नोड्स वाले एम-वे थ्रेडेड बाइनरी ट्री में, 'n×m - (n−1)' शून्य लिंक होते हैं।
संदर्भ
- ↑ Van Wyk, Christopher J. Data Structures and C Programs, Addison-Wesley, 1988, p. 175. ISBN 978-0-201-16116-8.
- ↑ Knuth, D.E. (1968). मौलिक एल्गोरिदम. The Art of Computer Programming. Vol. 1 (1st ed.). Reading/MA: Addison Wesley.
- ↑ Morris, Joseph H. (1979). "बाइनरी पेड़ों को आसानी से और सस्ते में पार करना". Information Processing Letters. 9 (5). doi:10.1016/0020-0190(79)90068-1.
- ↑ Mateti, Prabhaker; Manghirmalani, Ravi (1988). "मॉरिस के ट्री ट्रैवर्सल एल्गोरिदम पर पुनर्विचार किया गया". Science of Computer Programming. 11: 29–43. doi:10.1016/0167-6423(88)90063-9.
- ↑ Knuth, D.E. (1969). मौलिक एल्गोरिदम. The Art of Computer Programming. Vol. 1 (2 ed.). Addison Wesley. Hre: Sect.2.3.1 "Traversing Binary Trees".
- ↑ Perlis, Alan Jay; Thornton, C. (Apr 1960). "थ्रेडेड सूचियों द्वारा प्रतीक हेरफेर". Communications of the ACM. 3 (4): 195–204. doi:10.1145/367177.367202.
