टैंगो ट्री

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

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

संरचना

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

संदर्भ ट्री

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

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

मुख्य पथ

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

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

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

सहायक ट्री

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

एल्गोरिदम

अन्वेषण

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

अद्यतीकरण

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

जोड़ना

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

कमी

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

विश्लेषण

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

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

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

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

टैंगो ट्री

इसे टैंगो ट्रीज से जोड़ने के लिए, हम दिए गए एक्सेस अनुक्रम के लिए टैंगो ट्री द्वारा किए गए कार्य पर ऊपरी सीमा पाएंगे। इस प्रकार हमारी ऊपरी सीमा होगी $(k+1)O(\log \log n)$, जहां k अंतःपत्रों की संख्या है।

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

खोजना

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

अद्यतीकरण

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

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

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

यह भी देखें

• छींटे का ट्री
• इष्टतम बाइनरी सर्च ट्री
• लाल-काला ट्री
• ट्री (डेटा संरचना)