टैंगो ट्री: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
टैंगो ट्री प्रकार का [[बाइनरी सर्च ट्री]] है जिसे 2004 में एरिक डी. डेमाइन, डायोन हार्मन, [[जॉन इकोनो]] और मिहाई पेट्रोस्कु (कंप्यूटर वैज्ञानिक)|मिहाई पेट्रोस्कु द्वारा प्रस्तावित किया गया था।<ref name="DHIP">{{Cite journal | doi = 10.1137/S0097539705447347| url = http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf | title = Dynamic Optimality—Almost| journal = SIAM Journal on Computing| volume = 37|issue=1 |pages = 240| year = 2007| last1 = Demaine | first1 = E. D. | last2 = Harmon | first2 = D. | last3 = Iacono | first3 = J. | last4 = Pătraşcu | first4 = M. }}</ref> इसका नाम [[ब्यूनस आयर्स]] के नाम पर रखा गया है, जिसका [[निकालना]] प्रतीकात्मक है।
टैंगो ट्री प्रकार का [[बाइनरी सर्च ट्री]] है जिसे 2004 में एरिक डी. डेमाइन, डायोन हार्मन, [[जॉन इकोनो]] और मिहाई पेट्रोस्कु (कंप्यूटर वैज्ञानिक) या मिहाई पेट्रोस्कु द्वारा प्रस्तावित किया गया था।<ref name="DHIP">{{Cite journal | doi = 10.1137/S0097539705447347| url = http://erikdemaine.org/papers/Tango_SICOMP/paper.pdf | title = Dynamic Optimality—Almost| journal = SIAM Journal on Computing| volume = 37|issue=1 |pages = 240| year = 2007| last1 = Demaine | first1 = E. D. | last2 = Harmon | first2 = D. | last3 = Iacono | first3 = J. | last4 = Pătraşcu | first4 = M. }}</ref> इस प्रकार इसका नाम [[ब्यूनस आयर्स]] के नाम पर रखा गया है, जिसका [[निकालना|टैंगो]] प्रतीकात्मक है।


यह एक [[ ऑनलाइन एल्गोरिदम |ऑनलाइन एल्गोरिदम]] बाइनरी सर्च ट्री है जो लक्ष्य प्राप्त करता है <math>O(\log \log n)</math> [[ऑफ़लाइन एल्गोरिदम]] [[इष्टतम बाइनरी सर्च ट्री]] के सापेक्ष [[प्रतिस्पर्धी अनुपात]], केवल उपयोग करते समय <math>O(\log \log n)</math> प्रति नोड मेमोरी के अतिरिक्त बिट्स। इससे पिछले सर्वोत्तम ज्ञात प्रतिस्पर्धी अनुपात में सुधार हुआ, जो कि था <math>O(\log n)</math>.
यह एक [[ ऑनलाइन एल्गोरिदम |ऑनलाइन एल्गोरिदम]] बाइनरी सर्च ट्री है जो <math>O(\log \log n)</math> लक्ष्य प्राप्त करता है इस प्रकार [[ऑफ़लाइन एल्गोरिदम]] [[इष्टतम बाइनरी सर्च ट्री]] के सापेक्ष [[प्रतिस्पर्धी अनुपात]], केवल उपयोग करते समय <math>O(\log \log n)</math> प्रति नोड मेमोरी के अतिरिक्त बिट्स इससे पिछले सर्वोत्तम ज्ञात प्रतिस्पर्धी अनुपात में सुधार हुआ था, जो कि <math>O(\log n)</math> था


==संरचना==
==संरचना==
टैंगो पेड़ द्विआधारी खोज पेड़ को पसंदीदा पथों के सेट में विभाजित करके काम करते हैं, जो स्वयं सहायक पेड़ों में संग्रहीत होते हैं (इसलिए टैंगो पेड़ को पेड़ों के पेड़ के रूप में दर्शाया जाता है)।
टैंगो ट्री द्विआधारी खोज ट्री को मुख्य पथों के सेट में विभाजित करके कार्य करते हैं, जो स्वयं सहायक ट्रीज में संग्रहीत होते हैं (इसलिए टैंगो ट्री को ट्रीज के ट्री के रूप में दर्शाया जाता है)।


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


विशेष रूप से, संदर्भ वृक्ष की ऊंचाई है {{ceil|log<sub>2</sub>(''n''+1)}}. यह सबसे लंबे पथ की लंबाई के बराबर है, और इसलिए सबसे बड़े सहायक पेड़ के आकार के बराबर है। सहायक पेड़ों को उचित रूप से स्व-संतुलित बाइनरी सर्च ट्री रखकर, सहायक पेड़ों की ऊंचाई को सीमित किया जा सकता है {{nobr|''O''(log log ''n'').}} यह एल्गोरिथम की प्रदर्शन गारंटी का स्रोत है।
विशेष रूप से, संदर्भ ट्री की ऊंचाई {{ceil|log<sub>2</sub>(''n''+1)}} है यह सबसे लंबे पथ की लंबाई के सामान्य है, और इस प्रकार इसलिए सबसे बड़े सहायक ट्री के आकार के सामान्य है। सहायक ट्रीज को उचित रूप से स्व-संतुलित बाइनरी सर्च ट्री रखकर, सहायक ट्रीज की ऊंचाई {{nobr|''O''(log log ''n'').}} को सीमित किया जा सकता है  यह एल्गोरिथम की प्रदर्शन गारंटी का स्रोत है।


===पसंदीदा पथ===
===मुख्य पथ===
[[File:Preferred paths.png|right|thumb|किसी पेड़ के पसंदीदा पथ. प्रत्येक नोड का पसंदीदा बच्चा उसका सबसे हाल ही में देखा गया बच्चा है।]]सबसे पहले, हम प्रत्येक नोड के लिए उसके पसंदीदा बच्चे को परिभाषित करते हैं, जो अनौपचारिक रूप से पारंपरिक बाइनरी सर्च ट्री लुकअप द्वारा सबसे हाल ही में देखा गया बच्चा है। अधिक औपचारिक रूप से, [[उपवृक्ष]] टी पर विचार करें, जो पी पर आधारित है, जिसके बच्चे एल (बाएं) और आर (दाएं) हैं। हम r को p के पसंदीदा चाइल्ड के रूप में सेट करते हैं, यदि T में सबसे हाल ही में एक्सेस किया गया नोड r पर निहित सबट्री में है, और अन्यथा l को पसंदीदा चाइल्ड के रूप में सेट करते हैं। ध्यान दें कि यदि T का सबसे हाल ही में एक्सेस किया गया नोड p ही है, तो परिभाषा के अनुसार l पसंदीदा चाइल्ड है।
[[File:Preferred paths.png|right|thumb|किसी ट्री के मुख्य पथ. प्रत्येक नोड का मुख्य चाइल्ड उसका सबसे वर्तमान में देखा गया चाइल्ड है।]]सबसे पहले, हम प्रत्येक नोड के लिए उसके मुख्य चाइल्ड को परिभाषित करते हैं, जो अनौपचारिक रूप से पारंपरिक बाइनरी सर्च ट्री लुकअप द्वारा सबसे वर्तमान में देखा गया चाइल्ड है। अधिक औपचारिक रूप से, [[उपवृक्ष]] ट्री पर विचार करें, जो पी पर आधारित है, जिसके चाइल्ड एल (बाएं) और आर (दाएं) हैं। इस प्रकार हम r को p के मुख्य चाइल्ड के रूप में सेट करते हैं, यदि T में सबसे वर्तमान में एक्सेस किया गया नोड r पर निहित सबट्री में है, और अन्यथा को मुख्य चाइल्ड के रूप में सेट करते हैं। ध्यान दें कि यदि T का सबसे वर्तमान में एक्सेस किया गया नोड p ही है, तो परिभाषा के अनुसार मुख्य चाइल्ड है।


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


===सहायक वृक्ष===
===सहायक ट्री===
पसंदीदा पथ का प्रतिनिधित्व करने के लिए, हम इसके नोड्स को [[संतुलित बाइनरी खोज वृक्ष]] ट्री, विशेष रूप से लाल-काले पेड़ में संग्रहीत करते हैं। पसंदीदा पथ P में प्रत्येक गैर-पत्ती नोड n के लिए, इसमें गैर-पसंदीदा बच्चा c है, जो नए सहायक पेड़ की जड़ है। हम इस अन्य सहायक पेड़ की जड़ (सी) को पी में एन से जोड़ते हैं, इस प्रकार सहायक पेड़ों को साथ जोड़ते हैं। हम प्रत्येक नोड पर उस नोड के अंतर्गत उपट्री में नोड्स की न्यूनतम और अधिकतम गहराई (संदर्भ वृक्ष में गहराई, यानी) को संग्रहीत करके सहायक वृक्ष को भी बढ़ाते हैं।
मुख्य पथ का प्रतिनिधित्व करने के लिए, हम इसके नोड्स को [[संतुलित बाइनरी खोज वृक्ष|संतुलित बाइनरी खोज ट्री]] ट्री, विशेष रूप से लाल-काले ट्री में संग्रहीत करते हैं। इस प्रकार मुख्य पथ P में प्रत्येक गैर-पत्ती नोड n के लिए, इसमें गैर-मुख्य चाइल्ड c है, जो नए सहायक ट्री की जड़ है। हम इस अन्य सहायक ट्री की जड़ (सी) को पी में एन से जोड़ते हैं, इस प्रकार सहायक ट्रीज को साथ जोड़ते हैं। हम प्रत्येक नोड पर उस नोड के अंतर्गत उपट्री में नोड्स की न्यूनतम और अधिकतम गहराई (संदर्भ ट्री में गहराई, अर्थात) को संग्रहीत करके सहायक ट्री को भी बढ़ाते हैं।


==एल्गोरिदम==
==एल्गोरिदम==


===खोज रहा हूँ===
===अन्वेषण===
टैंगो ट्री में तत्व की खोज करने के लिए, हम बस संदर्भ ट्री की खोज का अनुकरण करते हैं। हम रूट से जुड़े पसंदीदा पथ की खोज से शुरू करते हैं, जो उस पसंदीदा पथ के अनुरूप सहायक पेड़ की खोज करके अनुकरण किया जाता है। यदि सहायक वृक्ष में वांछित तत्व नहीं है, तो खोज वांछित तत्व वाले उप-वृक्ष के मूल के पैरेंट पर समाप्त हो जाती है (दूसरे पसंदीदा पथ की शुरुआत), इसलिए हम बस उस पसंदीदा पथ के लिए सहायक वृक्ष की खोज करके आगे बढ़ते हैं। , इत्यादि।
टैंगो ट्री में तत्व की खोज करने के लिए, हम बस संदर्भ ट्री की खोज का अनुकरण करते हैं। हम रूट से जुड़े मुख्य पथ की खोज से प्रारंभ करते हैं, जो उस मुख्य पथ के अनुरूप सहायक ट्री की खोज करके अनुकरण किया जाता है। यदि सहायक ट्री में वांछित तत्व नहीं है, जिससे खोज वांछित तत्व वाले उप-ट्री के मूल के पैरेंट पर समाप्त हो जाती है (दूसरे मुख्य पथ की प्रारंभ), इसलिए हम बस उस मुख्य पथ के लिए सहायक ट्री की खोज करके आगे बढ़ते हैं।


===अद्यतन हो रहा है===
===अद्यतीकरण===
टैंगो ट्री (सहायक पेड़ पसंदीदा पथों के अनुरूप हैं) की संरचना को बनाए रखने के लिए, जब भी खोज के परिणामस्वरूप पसंदीदा बच्चे बदलते हैं तो हमें कुछ अद्यतन कार्य करना चाहिए। जब कोई पसंदीदा बच्चा बदलता है, तो पसंदीदा पथ का शीर्ष हिस्सा निचले हिस्से से अलग हो जाता है (जो उसका अपना पसंदीदा पथ बन जाता है) और दूसरे पसंदीदा पथ से जुड़ जाता है (जो नया निचला हिस्सा बन जाता है)। इसे कुशलता से करने के लिए, हम अपने सहायक पेड़ों पर कट और जॉइनिंग ऑपरेशन को परिभाषित करेंगे।
टैंगो ट्री (सहायक ट्री मुख्य पथों के अनुरूप हैं) की संरचना को बनाए रखने के लिए, जब भी खोज के परिणामस्वरूप मुख्य चाइल्ड बदलते हैं इस प्रकार हमें कुछ अद्यतन कार्य करना चाहिए। जब कोई मुख्य चाइल्ड बदलता है, तो मुख्य पथ का शीर्ष भाग निचले भाग से अलग हो जाता है (जो उसका अपना मुख्य पथ बन जाता है) और दूसरे मुख्य पथ से जुड़ जाता है (जो नया निचला भाग बन जाता है)। इसे कुशलता से करने के लिए, हम अपने सहायक ट्रीज पर कट और जॉइनिंग ऑपरेशन को परिभाषित करते है।


====जुड़ें====
====जोड़ना====
हमारा जॉइन ऑपरेशन दो सहायक पेड़ों को तब तक संयोजित करेगा जब तक उनके पास यह गुण है कि का शीर्ष नोड (संदर्भ पेड़ में) दूसरे के निचले नोड का बच्चा है (अनिवार्य रूप से, संबंधित पसंदीदा पथों को संयोजित किया जा सकता है)। यह लाल-काले पेड़ों के संयोजित संचालन के आधार पर काम करेगा, जो दो पेड़ों को तब तक जोड़ता है जब तक उनमें यह गुण होता है कि के सभी तत्व दूसरे के सभी तत्वों से कम होते हैं, और विभाजित होते हैं, जो विपरीत होता है। संदर्भ वृक्ष में, ध्यान दें कि शीर्ष पथ में दो नोड मौजूद हैं जैसे कि नोड नीचे के पथ में है और केवल तभी जब इसका कुंजी-मान उनके बीच है। अब, नीचे के पथ को शीर्ष पथ से जोड़ने के लिए, हम बस शीर्ष पथ को उन दो नोड्स के बीच विभाजित करते हैं, फिर दो परिणामी सहायक पेड़ों को नीचे के पथ के सहायक पेड़ के दोनों ओर जोड़ते हैं, और हमारे पास हमारा अंतिम, जुड़ा हुआ सहायक पेड़ होता है।
हमारा जॉइन ऑपरेशन दो सहायक ट्रीज को तब तक संयोजित करेगा जब तक उनके पास यह गुण है कि का शीर्ष नोड (संदर्भ ट्री में) दूसरे के निचले नोड का चाइल्ड है (अनिवार्य रूप से, संबंधित मुख्य पथों को संयोजित किया जा सकता है)। यह लाल-काले ट्रीज के संयोजित संचालन के आधार पर कार्य करेगा, इस प्रकार जो दो ट्रीज को तब तक जोड़ता है जब तक उनमें यह गुण होता है कि के सभी तत्व दूसरे के सभी तत्वों से कम होते हैं, और विभाजित होते हैं, जो विपरीत होता है। संदर्भ ट्री में, ध्यान दें कि शीर्ष पथ में दो नोड उपस्थित हैं जैसे कि नोड नीचे के पथ में है और केवल तभी जब इसका कुंजी-मान उनके बीच है। अब, नीचे के पथ को शीर्ष पथ से जोड़ने के लिए, हम बस शीर्ष पथ को उन दो नोड्स के बीच विभाजित करते हैं, फिर दो परिणामी सहायक ट्रीज को नीचे के पथ के सहायक ट्री के दोनों ओर जोड़ते हैं, और हमारे पास हमारा अंतिम, जुड़ा हुआ सहायक ट्री होता है।


====काटो====
====कमी====
हमारा कट ऑपरेशन किसी दिए गए नोड पर पसंदीदा पथ को दो भागों में तोड़ देगा, शीर्ष भाग और निचला भाग। अधिक औपचारिक रूप से, यह सहायक वृक्ष को दो सहायक वृक्षों में विभाजित करेगा, जैसे कि में संदर्भ वृक्ष में निश्चित गहराई पर या उससे ऊपर के सभी नोड शामिल हों, और दूसरे में उस गहराई के नीचे के सभी नोड हों। जैसे कि जोड़ में, ध्यान दें कि शीर्ष भाग में दो नोड हैं जो निचले भाग को ब्रैकेट करते हैं। इस प्रकार, हम पथ को तीन भागों में विभाजित करने के लिए इन दो नोड्स में से प्रत्येक पर आसानी से विभाजित कर सकते हैं, फिर दो बाहरी हिस्सों को जोड़ सकते हैं ताकि हम इच्छानुसार दो भागों, ऊपर और नीचे, के साथ समाप्त हो सकें।
हमारा कट ऑपरेशन किसी दिए गए नोड पर मुख्य पथ को दो भागों में तोड़ देगा, शीर्ष भाग और निचला भाग अधिक औपचारिक रूप से, यह सहायक ट्री को दो सहायक वृक्षों में विभाजित करता है, इस प्रकार जैसे कि में संदर्भ ट्री में निश्चित गहराई पर या उससे ऊपर के सभी नोड सम्मिलित होंता है, और दूसरे में उस गहराई के नीचे के सभी नोड होंता है। जैसे कि जोड़ में, ध्यान दें कि शीर्ष भाग में दो नोड हैं जो निचले भाग को ब्रैकेट करते हैं। इस प्रकार, हम पथ को तीन भागों में विभाजित करने के लिए इन दो नोड्स में से प्रत्येक पर सरलता से विभाजित कर सकते हैं, फिर दो बाहरी भागो को जोड़ सकते हैं जिससे हम इच्छानुसार दो भागों, ऊपर और नीचे, के साथ समाप्त हो सकते है।


==विश्लेषण==
==विश्लेषण==
टैंगो पेड़ों के लिए प्रतिस्पर्धी अनुपात को सीमित करने के लिए, हमें इष्टतम ऑफ़लाइन पेड़ के प्रदर्शन पर निचली सीमा ढूंढनी होगी जिसे हम बेंचमार्क के रूप में उपयोग करते हैं। बार जब हमें टैंगो ट्री के प्रदर्शन की ऊपरी सीमा मिल जाती है, तो हम उन्हें प्रतिस्पर्धी अनुपात में विभाजित कर सकते हैं।
टैंगो ट्रीज के लिए प्रतिस्पर्धी अनुपात को सीमित करने के लिए, हमें इष्टतम ऑफ़लाइन ट्री के प्रदर्शन पर निचली सीमा खोजनी होगी जिसे हम बेंचमार्क के रूप में उपयोग करते हैं। इस प्रकार जब हमें टैंगो ट्री के प्रदर्शन की ऊपरी सीमा मिल जाती है, तो हम उन्हें प्रतिस्पर्धी अनुपात में विभाजित कर सकते हैं।


===इंटरलीव बाउंड===
===इंटरलीव बाउंड===
{{Main|Interleave lower bound}}
{{Main|निचली सीमा को इंटरलीव करें}}
इष्टतम ऑफ़लाइन बाइनरी सर्च ट्री द्वारा किए गए कार्य की निचली सीमा का पता लगाने के लिए, हम फिर से पसंदीदा बच्चों की धारणा का उपयोग करते हैं। एक्सेस अनुक्रम (खोजों का अनुक्रम) पर विचार करते समय, हम इस बात पर नज़र रखते हैं कि संदर्भ ट्री नोड का पसंदीदा चाइल्ड कितनी बार स्विच करता है। स्विचों की कुल संख्या (सभी नोड्स पर संक्षेपित) दिए गए एक्सेस अनुक्रम पर किसी भी बाइनरी सर्च ट्री एल्गोरिदम द्वारा किए गए कार्य पर असम्बद्ध विश्लेषण देती है। इसे इंटरलीव लोअर बाउंड कहा जाता है।{{r|DHIP}}


===टैंगो पेड़===
इष्टतम ऑफ़लाइन बाइनरी सर्च ट्री द्वारा किए गए कार्य की निचली सीमा का पता लगाने के लिए, हम फिर से मुख्य चाइल्ड की धारणा का उपयोग करते हैं। इस प्रकार एक्सेस अनुक्रम (खोजों का अनुक्रम) पर विचार करते समय, हम इस बात पर द्रष्टि रखते हैं कि संदर्भ ट्री नोड का मुख्य चाइल्ड कितनी बार स्विच करता है। स्विचों की कुल संख्या (सभी नोड्स पर संक्षेपित) दिए गए एक्सेस अनुक्रम पर किसी भी बाइनरी सर्च ट्री एल्गोरिदम द्वारा किए गए कार्य पर असम्बद्ध विश्लेषण देती है। इसे इंटरलीव लोअर बाउंड कहा जाता है।{{r|DHIP}}
इसे टैंगो पेड़ों से जोड़ने के लिए, हम दिए गए एक्सेस अनुक्रम के लिए टैंगो पेड़ द्वारा किए गए कार्य पर ऊपरी सीमा पाएंगे। हमारी ऊपरी सीमा होगी <math>(k+1) O(\log \log n)</math>, जहां k अंतःपत्रों की संख्या है।


कुल लागत को दो भागों में विभाजित किया गया है, तत्व की खोज करना, और उचित अपरिवर्तनीयता बनाए रखने के लिए टैंगो पेड़ की संरचना को अद्यतन करना (पसंदीदा बच्चों को बदलना और पसंदीदा पथों को फिर से व्यवस्थित करना)।
===टैंगो ट्री===
इसे टैंगो ट्रीज से जोड़ने के लिए, हम दिए गए एक्सेस अनुक्रम के लिए टैंगो ट्री द्वारा किए गए कार्य पर ऊपरी सीमा पाएंगे। इस प्रकार हमारी ऊपरी सीमा होगी <math>(k+1) O(\log \log n)</math>, जहां k अंतःपत्रों की संख्या है।


====खोज रहा हूँ====
कुल निवेश को दो भागों में विभाजित किया गया है, तत्व की खोज करना, और उचित अपरिवर्तनीयता बनाए रखने के लिए टैंगो ट्री की संरचना को अद्यतन करना (मुख्य चाइल्ड को बदलना और मुख्य पथों को फिर से व्यवस्थित करना)।
यह देखने के लिए कि खोज (अद्यतन नहीं) इस सीमा में फिट बैठती है, बस ध्यान दें कि हर बार सहायक पेड़ की खोज असफल होती है और हमें अगले सहायक पेड़ पर जाना पड़ता है, जिसके परिणामस्वरूप पसंदीदा बच्चा स्विच होता है (क्योंकि अब मूल पसंदीदा पथ बच्चे के पसंदीदा पथ से जुड़ने के लिए दिशा-निर्देश बदलता है)। चूँकि अंतिम को छोड़कर सभी सहायक वृक्ष खोजें असफल होती हैं (स्वाभाविक रूप से, खोज सफल होने पर हम रुक जाते हैं), हम खोज करते हैं <math>k+1</math> सहायक वृक्ष. प्रत्येक खोज लेता है <math>O(\log \log n)</math>, क्योंकि सहायक वृक्ष का आकार इससे घिरा होता है <math>\log n</math>, संदर्भ वृक्ष की ऊंचाई।


====अद्यतन हो रहा है====
====खोजना====
अद्यतन लागत इस सीमा के भीतर भी फिट बैठती है, क्योंकि हमें प्रत्येक विज़िट किए गए सहायक पेड़ के लिए केवल कट और जॉइन करना होगा। एकल कट या जॉइन ऑपरेशन में केवल निरंतर खोज, विभाजन और संयोजन की आवश्यकता होती है, जिनमें से प्रत्येक सहायक पेड़ के आकार में लघुगणकीय समय लेता है, इसलिए हमारी अद्यतन लागत है <math>(k+1) O(\log \log n)</math>.
यह देखने के लिए कि खोज (अद्यतन नहीं) इस सीमा में फिट बैठती है, ध्यान दें कि हर बार सहायक ट्री की खोज असफल होती है और हमें अगले सहायक ट्री पर जाना पड़ता है, इस प्रकार जिसके परिणामस्वरूप मुख्य चाइल्ड स्विच होता है (क्योंकि अब मूल मुख्य पथ चाइल्ड के मुख्य पथ से जुड़ने के लिए दिशा-निर्देश बदलता है)। चूँकि अंतिम को छोड़कर सभी सहायक ट्री खोजें असफल होती हैं (स्वाभाविक रूप से, खोज सफल होने पर हम रुक जाते हैं), हम खोज <math>k+1</math> करते हैं  सहायक ट्री. प्रत्येक <math>O(\log \log n)</math> खोज लेता है , क्योंकि सहायक ट्री का आकार <math>\log n</math> इससे घिरा होता है।
 
====अद्यतीकरण====
अद्यतन निवेश इस सीमा के अन्दर भी फिट बैठती है, क्योंकि हमें प्रत्येक विज़िट किए गए सहायक ट्री के लिए केवल कट और जॉइन करना होता है। इस प्रकार एकल कट या जॉइन ऑपरेशन में केवल निरंतर खोज, विभाजन और संयोजन की आवश्यकता होती है, जिनमें से प्रत्येक सहायक ट्री के आकार में लघुगणकीय समय लेता है, इसलिए हमारी अद्यतन निवेश <math>(k+1) O(\log \log n)</math> है .


===प्रतिस्पर्धी अनुपात===
===प्रतिस्पर्धी अनुपात===
टैंगो के पेड़ हैं <math>O(\log \log n)</math>-प्रतिस्पर्धी, क्योंकि इष्टतम ऑफ़लाइन बाइनरी सर्च ट्री द्वारा किया गया कार्य कम से कम k (पसंदीदा चाइल्ड स्विच की कुल संख्या) में रैखिक है, और टैंगो ट्री द्वारा किया गया कार्य अधिकतम है <math>(k+1) O(\log \log n)</math>.
टैंगो के ट्री <math>O(\log \log n)</math> हैं  इस प्रकार प्रतिस्पर्धी, क्योंकि इष्टतम ऑफ़लाइन बाइनरी सर्च ट्री द्वारा किया गया कार्य कम से कम k (मुख्य चाइल्ड स्विच की कुल संख्या) में रैखिक है, और टैंगो ट्री <math>(k+1) O(\log \log n)</math> द्वारा किया गया कार्य अधिकतम है .


==यह भी देखें==
==यह भी देखें==
* [[छींटे का पेड़]]
* [[छींटे का पेड़|छींटे का ट्री]]
* इष्टतम बाइनरी सर्च ट्री
* इष्टतम बाइनरी सर्च ट्री
* लाल-काला पेड़
* लाल-काला ट्री
* [[वृक्ष (डेटा संरचना)]]
* [[वृक्ष (डेटा संरचना)|ट्री (डेटा संरचना)]]


==संदर्भ==
==संदर्भ==

Revision as of 11:34, 17 July 2023

टैंगो ट्री प्रकार का बाइनरी सर्च ट्री है जिसे 2004 में एरिक डी. डेमाइन, डायोन हार्मन, जॉन इकोनो और मिहाई पेट्रोस्कु (कंप्यूटर वैज्ञानिक) या मिहाई पेट्रोस्कु द्वारा प्रस्तावित किया गया था।[1] इस प्रकार इसका नाम ब्यूनस आयर्स के नाम पर रखा गया है, जिसका टैंगो प्रतीकात्मक है।

यह एक ऑनलाइन एल्गोरिदम बाइनरी सर्च ट्री है जो लक्ष्य प्राप्त करता है इस प्रकार ऑफ़लाइन एल्गोरिदम इष्टतम बाइनरी सर्च ट्री के सापेक्ष प्रतिस्पर्धी अनुपात, केवल उपयोग करते समय प्रति नोड मेमोरी के अतिरिक्त बिट्स इससे पिछले सर्वोत्तम ज्ञात प्रतिस्पर्धी अनुपात में सुधार हुआ था, जो कि था

संरचना

टैंगो ट्री द्विआधारी खोज ट्री को मुख्य पथों के सेट में विभाजित करके कार्य करते हैं, जो स्वयं सहायक ट्रीज में संग्रहीत होते हैं (इसलिए टैंगो ट्री को ट्रीज के ट्री के रूप में दर्शाया जाता है)।

संदर्भ ट्री

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

विशेष रूप से, संदर्भ ट्री की ऊंचाई ⌈log2(n+1)⌉ है यह सबसे लंबे पथ की लंबाई के सामान्य है, और इस प्रकार इसलिए सबसे बड़े सहायक ट्री के आकार के सामान्य है। सहायक ट्रीज को उचित रूप से स्व-संतुलित बाइनरी सर्च ट्री रखकर, सहायक ट्रीज की ऊंचाई O(log log n). को सीमित किया जा सकता है यह एल्गोरिथम की प्रदर्शन गारंटी का स्रोत है।

मुख्य पथ

किसी ट्री के मुख्य पथ. प्रत्येक नोड का मुख्य चाइल्ड उसका सबसे वर्तमान में देखा गया चाइल्ड है।

सबसे पहले, हम प्रत्येक नोड के लिए उसके मुख्य चाइल्ड को परिभाषित करते हैं, जो अनौपचारिक रूप से पारंपरिक बाइनरी सर्च ट्री लुकअप द्वारा सबसे वर्तमान में देखा गया चाइल्ड है। अधिक औपचारिक रूप से, उपवृक्ष ट्री पर विचार करें, जो पी पर आधारित है, जिसके चाइल्ड एल (बाएं) और आर (दाएं) हैं। इस प्रकार हम r को p के मुख्य चाइल्ड के रूप में सेट करते हैं, यदि T में सबसे वर्तमान में एक्सेस किया गया नोड r पर निहित सबट्री में है, और अन्यथा को मुख्य चाइल्ड के रूप में सेट करते हैं। ध्यान दें कि यदि T का सबसे वर्तमान में एक्सेस किया गया नोड p ही है, तो परिभाषा के अनुसार मुख्य चाइल्ड है।

एक मुख्य पथ को जड़ से प्रारंभ करके और पत्ती नोड तक पहुंचने तक मुख्य चाइल्ड का अनुसरण करके परिभाषित किया जाता है। इस पथ पर नोड्स को हटाने से ट्री के शेष भाग को कई उप-वृक्षों में विभाजित किया जाता है, और हम प्रत्येक उप-ट्री पर पुनरावृत्ति करते हैं (इसके मूल से मुख्य पथ बनाते हैं, जो उप-ट्री को अधिक उप-वृक्षों में विभाजित करता है)।

सहायक ट्री

मुख्य पथ का प्रतिनिधित्व करने के लिए, हम इसके नोड्स को संतुलित बाइनरी खोज ट्री ट्री, विशेष रूप से लाल-काले ट्री में संग्रहीत करते हैं। इस प्रकार मुख्य पथ P में प्रत्येक गैर-पत्ती नोड n के लिए, इसमें गैर-मुख्य चाइल्ड c है, जो नए सहायक ट्री की जड़ है। हम इस अन्य सहायक ट्री की जड़ (सी) को पी में एन से जोड़ते हैं, इस प्रकार सहायक ट्रीज को साथ जोड़ते हैं। हम प्रत्येक नोड पर उस नोड के अंतर्गत उपट्री में नोड्स की न्यूनतम और अधिकतम गहराई (संदर्भ ट्री में गहराई, अर्थात) को संग्रहीत करके सहायक ट्री को भी बढ़ाते हैं।

एल्गोरिदम

अन्वेषण

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

अद्यतीकरण

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

जोड़ना

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

कमी

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

विश्लेषण

टैंगो ट्रीज के लिए प्रतिस्पर्धी अनुपात को सीमित करने के लिए, हमें इष्टतम ऑफ़लाइन ट्री के प्रदर्शन पर निचली सीमा खोजनी होगी जिसे हम बेंचमार्क के रूप में उपयोग करते हैं। इस प्रकार जब हमें टैंगो ट्री के प्रदर्शन की ऊपरी सीमा मिल जाती है, तो हम उन्हें प्रतिस्पर्धी अनुपात में विभाजित कर सकते हैं।

इंटरलीव बाउंड

Main article: निचली सीमा को इंटरलीव करें

इष्टतम ऑफ़लाइन बाइनरी सर्च ट्री द्वारा किए गए कार्य की निचली सीमा का पता लगाने के लिए, हम फिर से मुख्य चाइल्ड की धारणा का उपयोग करते हैं। इस प्रकार एक्सेस अनुक्रम (खोजों का अनुक्रम) पर विचार करते समय, हम इस बात पर द्रष्टि रखते हैं कि संदर्भ ट्री नोड का मुख्य चाइल्ड कितनी बार स्विच करता है। स्विचों की कुल संख्या (सभी नोड्स पर संक्षेपित) दिए गए एक्सेस अनुक्रम पर किसी भी बाइनरी सर्च ट्री एल्गोरिदम द्वारा किए गए कार्य पर असम्बद्ध विश्लेषण देती है। इसे इंटरलीव लोअर बाउंड कहा जाता है।[1]

टैंगो ट्री

इसे टैंगो ट्रीज से जोड़ने के लिए, हम दिए गए एक्सेस अनुक्रम के लिए टैंगो ट्री द्वारा किए गए कार्य पर ऊपरी सीमा पाएंगे। इस प्रकार हमारी ऊपरी सीमा होगी , जहां k अंतःपत्रों की संख्या है।

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

खोजना

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

अद्यतीकरण

अद्यतन निवेश इस सीमा के अन्दर भी फिट बैठती है, क्योंकि हमें प्रत्येक विज़िट किए गए सहायक ट्री के लिए केवल कट और जॉइन करना होता है। इस प्रकार एकल कट या जॉइन ऑपरेशन में केवल निरंतर खोज, विभाजन और संयोजन की आवश्यकता होती है, जिनमें से प्रत्येक सहायक ट्री के आकार में लघुगणकीय समय लेता है, इसलिए हमारी अद्यतन निवेश है .

प्रतिस्पर्धी अनुपात

टैंगो के ट्री हैं इस प्रकार प्रतिस्पर्धी, क्योंकि इष्टतम ऑफ़लाइन बाइनरी सर्च ट्री द्वारा किया गया कार्य कम से कम k (मुख्य चाइल्ड स्विच की कुल संख्या) में रैखिक है, और टैंगो ट्री द्वारा किया गया कार्य अधिकतम है .

यह भी देखें

संदर्भ

  1. ↑ 1.0 1.1 Demaine, E. D.; Harmon, D.; Iacono, J.; Pătraşcu, M. (2007). "Dynamic Optimality—Almost" (PDF). SIAM Journal on Computing. 37 (1): 240. doi:10.1137/S0097539705447347.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=टैंगो_ट्री&oldid=227972’