टैंगो ट्री

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

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

संरचना

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

संदर्भ वृक्ष

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

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

पसंदीदा पथ

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

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

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

सहायक वृक्ष

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

एल्गोरिदम

खोज रहा हूँ

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

अद्यतन हो रहा है

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

जुड़ें

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

काटो

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

विश्लेषण

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

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

Main article: Interleave lower bound

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

टैंगो पेड़

इसे टैंगो पेड़ों से जोड़ने के लिए, हम दिए गए एक्सेस अनुक्रम के लिए टैंगो पेड़ द्वारा किए गए कार्य पर एक ऊपरी सीमा पाएंगे। हमारी ऊपरी सीमा होगी $(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)$.

यह भी देखें

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