😛 💰 🤲🏽 कार्टेशियन ट्री: भाग 1. विवरण, संचालन, अनुप्रयोग 🦃 🤠 🧓🏻

सामग्री की तालिका (वर्तमान में)

भाग 1. विवरण, संचालन, अनुप्रयोग।

भाग 2. पेड़ में मूल्यवान जानकारी और इसके साथ कई ऑपरेशन।

भाग 3. निहित कुंजी द्वारा कार्टेशियन पेड़।

जारी रखने के लिए ...

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

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

परिचय

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

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

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

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

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

समस्याओं

जब पेड़ों की खोज करने की बात आती है (आप पहले से ही अनुशंसित लेख पढ़ते हैं, तो ठीक है?), संरचना के समक्ष रखा गया मुख्य प्रश्न संचालन की गति है, इसमें संग्रहीत डेटा और उनके आगमन के क्रम की परवाह किए बिना। तो, बाइनरी सर्च ट्री इस बात की गारंटी देता है कि इस पेड़ की एक विशिष्ट कुंजी की खोज O (H) में की जाएगी, जहां H पेड़ की ऊंचाई है। लेकिन यह क्या ऊंचाई हो सकती है - शैतान उसे जानता है। प्रतिकूल परिस्थितियों में, पेड़ की ऊंचाई आसानी से एन (इसमें तत्वों की संख्या) हो सकती है, और फिर खोज पेड़ एक नियमित सूची में बदल जाता है - और फिर इसकी आवश्यकता क्यों है? इस स्थिति को प्राप्त करने के लिए, खोज ट्री में आरोही कतार में 1 से N तक तत्वों को जोड़ना पर्याप्त है - पेड़ में जोड़ने के लिए मानक एल्गोरिथ्म के साथ, हमें निम्नलिखित चित्र मिलता है:

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

परिभाषा

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

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

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

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

और दूसरी बात, अब अपनी प्राथमिकताओं को यादृच्छिक बनाएं। यही है, हम बस प्रत्येक कुंजी के साथ पर्याप्त रूप से बड़ी रेंज से एक यादृच्छिक संख्या को जोड़ते हैं, और यह संबंधित खिलाड़ी के रूप में काम करेगा। फिर 100% के लिए प्रवृत्त होने वाले बहुत अधिक संभावना वाले परिणामी कार्टिसियन वृक्ष की ऊंचाई 4 लॉग ₂ एन से अधिक नहीं होगी (मैं इस तथ्य को प्रमाण के बिना छोड़ दूंगा।) इसलिए, हालांकि यह पूरी तरह से संतुलित नहीं हो सकता है, कुंजी खोज समय। ऐसा पेड़ अभी भी ऑर्डर O (लॉग ₂ एन) का होगा, जो कि वास्तव में हम मांग रहे हैं।

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

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

संचालन के बारे में कहानी शुरू करने से पहले, मैं आपको C # वर्ग का एक रिक्त स्थान दूंगा, जो हमारे कार्टेशियन वृक्ष को लागू करेगा।

public class Treap { public int x; public int y; public Treap Left; public Treap Right; private Treap(int x, int y, Treap left = null, Treap right = null) { this.x = x; this.y = y; this.Left = left; this.Right = right; } //   ... }

सादगी के लिए, मैंने एक x और y प्रकार का int

, लेकिन यह स्पष्ट है कि उनके स्थान पर कोई भी प्रकार हो सकता है जिसके उदाहरण हम एक-दूसरे के साथ तुलना कर सकते हैं - अर्थात, कोई भी व्यक्ति C के संदर्भ में IComparable

या IComparable<T>

को लागू कर सकता है। हास्केल में, यह Ord

वर्ग से किसी भी प्रकार का हो सकता है, एफ # में किसी भी तुलना ऑपरेटर पर प्रतिबंधों के साथ, जावा में यह Comparable<T1>

इंटरफ़ेस को लागू करता है, और इसी तरह।

गोंद और कैंची का जादू

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

कार्तीय वृक्ष के साथ काम करने वाले सभी इन्स और बहिष्कार में दो मुख्य ऑपरेशन होते हैं: मर्ज और स्प्लिट । उनकी मदद से, अन्य सभी लोकप्रिय ऑपरेशनों को प्राथमिक रूप से व्यक्त किया जाता है, इसलिए आइए मूल बातें शुरू करें।

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

मर्ज का वर्कफ़्लो बहुत सरल है। भविष्य के पेड़ की जड़ कौन सा तत्व होगा? जाहिर है सर्वोच्च प्राथमिकता के साथ। हमारे पास अधिकतम प्राथमिकता के लिए दो उम्मीदवार हैं - केवल दो स्रोत पेड़ों की जड़ें। उनकी प्राथमिकताओं की तुलना करें; विशिष्टता के लिए, बाएं रूट की प्राथमिकता y को अधिक होने दें, और इसमें कुंजी x के बराबर है। एक नई जड़ को परिभाषित किया गया है, अब यह विचार करने योग्य है कि कौन से तत्व इसके सही उप-भाग में दिखाई देंगे और कौन से बाएँ में।

यह समझना आसान है कि पूरे पेड़ आर नई जड़ के सही उपप्रकार में होगा, क्योंकि इसमें स्थिति से x की तुलना में अधिक कुंजी है। उसी तरह, पुरानी L.eft रूट की बाईं सबट्री में x की तुलना में सभी कीज़ छोटी होती हैं और लेफ्ट सबट्री रहनी चाहिए, और राइट सबट्री L.Right ... लेकिन राइट सबट्री एक ही कारणों के लिए दाईं ओर होनी चाहिए, हालाँकि, यह स्पष्ट नहीं है कि इसके एलिमेंट्स को कहाँ रखा जाए, और पेड़ R के तत्व कहां हैं?

बंद करो, यह अस्पष्ट क्यों है? हमारे पास दो पेड़ हैं, एक में चाबियां दूसरे में कुंजियों से कम हैं, और हमें किसी तरह उन्हें गठबंधन करने और परिणाम को सही उपप्रकार के रूप में नई जड़ में संलग्न करने की आवश्यकता है। बस पुन: L.Right और R ट्री के लिए मर्ज को कॉल करें, और नए राइट सबट्री के रूप में उसके द्वारा लौटे ट्री का उपयोग करें। परिणाम स्पष्ट है।

नीले रंग में आकृति मर्ज ऑपरेशन के बाद परिणामी पेड़ के सही उपप्रकार और नई जड़ से इस उपप्रकार के कनेक्शन को दर्शाती है।

सममित मामला - जब पेड़ की जड़ में प्राथमिकता आर अधिक है - समान रूप से disassembled है। और, ज़ाहिर है, हमें पुनरावृत्ति के आधार के बारे में नहीं भूलना चाहिए, जो कि हमारे मामले में होता है यदि पेड़ एल और आर में से एक, या दोनों, खाली हैं।

डाउनलोड स्रोत पैकेज मर्ज:

 public static Treap Merge(Treap L, Treap R) { if (L == null) return R; if (R == null) return L; if (Ly > Ry) { var newR = Merge(L.Right, R); return new Treap(Lx, Ly, L.Left, newR); } else { var newL = Merge(L, R.Left); return new Treap(Rx, Ry, newL, R.Right); } }

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

हम इसी तरह से तर्क देते हैं। पेड़ की जड़ T कहाँ होगी? यदि इसकी कुंजी x ₀ से कम है, तो L में, अन्यथा R में। फिर, स्पष्टता के लिए, मान लें कि मूल कुंजी x ₀ से कम है।

तब हम तुरंत कह सकते हैं कि बाएं सबट्री टी के सभी तत्व एल में भी होंगे - उनकी चाबियाँ भी x ₀ से कम होंगी। इसके अलावा, टी की जड़ भी एल की जड़ होगी, क्योंकि इसकी प्राथमिकता पूरे पेड़ में सबसे बड़ी है। रूट की बाईं सबट्री पूरी तरह से अपरिवर्तित रखी जाएगी, लेकिन राइट सबट्री कम हो जाएगी - आपको एक्स ₀ से अधिक कीज़ वाले तत्वों को निकालना होगा और इसे पेड़ आर में डाल दिया जाएगा और बाकी कीज़ को बचाएंगे क्योंकि नई सबट्री एल के रूप में फिर से हम समान कार्य देखते हैं, पुन: पुन: जुड़ना शुरू होता है!

सही सबट्री लें और उसी कुंजी x ₀ का उपयोग करके इसे दो पेड़ों L 'और R' में काट लें। तब यह स्पष्ट हो जाता है कि L 'L वृक्ष का नया सही उप-प्रकार बन जाएगा, और R' वृक्ष R स्वयं है - इसमें वे और केवल वे तत्व शामिल हैं जो x ₀ से अधिक हैं।

सममित मामला जिसमें मूल कुंजी x ₀ से अधिक है, पूरी तरह से समान है। यहाँ पुनरावृत्ति का आधार तब होता है जब कुछ उपप्रकार खाली होते हैं। खैर, फ़ंक्शन का स्रोत कोड:

 public void Split(int x, out Treap L, out Treap R) { Treap newTree = null; if (this.x <= x) { if (Right == null) R = null; else Right.Split(x, out newTree, out R); L = new Treap(this.x, y, Left, newTree); } else { if (Left == null) L = null; else Left.Split(x, out L, out newTree); R = new Treap(this.x, y, newTree, Right); } }

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

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

वृक्षों का संचालन

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

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

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

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

समस्या को ठीक किया जा सकता है। स्प्लिट / मर्ज संचालन की बहुमुखी प्रतिभा को याद करते हुए, समाधान खुद को लगभग तुरंत सुझाता है:

हम पेड़ को कुंजी X द्वारा पेड़ L में विभाजित करते हैं, X की तुलना में छोटी के साथ, और पेड़ R, बड़े वाले के साथ।
इस कुंजी को एक एकल शीर्ष (x, y) से एक पेड़ M बनाएँ, जहाँ y नव सृजित यादृच्छिक प्राथमिकता है।
कंघी (मर्ज) को बारी L में M के साथ करें, क्या हुआ - R के साथ।

एल्गोरिथ्म के सभी चरणों को चित्रित किया जा सकता है।

हमारे यहां 1 स्प्लिट एप्लिकेशन है, और 2 मर्ज एप्लिकेशन हैं - ओ का कुल परिचालन समय (लॉग ₂ एन)। शॉर्ट सोर्स कोड संलग्न

 public Treap Add(int x) { Treap l, r; Split(x, out l, out r); Treap m = new Treap(x, rand.Next()); return Merge(Merge(l, m), r); }

हटाने के साथ, कोई सवाल भी नहीं है। हमें कार्टेसियन पेड़ से कुंजी एक्स के साथ एक तत्व को हटाने के लिए कहा जाए। अब मैं मानता हूं कि आपने कुंजी की समानता का पता लगा लिया है, बाईं ओर वरीयता दे रहा है: कुंजी x के साथ शीर्ष के दाईं ओर उपप्रकार में, उसी कुंजी के साथ अन्य तत्व नहीं होते हैं, लेकिन बाईं ओर वे कर सकते हैं। तब हम क्रियाओं का निम्नलिखित क्रम करते हैं:

सबसे पहले, पेड़ को कुंजी x-1 से विभाजित करें। X-1 से कम या बराबर सभी तत्व बाएं परिणाम पर गए, जिसका अर्थ है कि वांछित तत्व दाईं ओर है।
हम सही परिणाम को कुंजी x से विभाजित करते हैं (यहां यह समानता के साथ सावधान रहने के लायक है!)। X से अधिक कुंजियों वाले सभी तत्व नए सही परिणाम पर गए, और "मध्य" (दाएं से बाएं) - सभी x से कम या बराबर। लेकिन चूंकि हर कोई पहला कदम समाप्त होने के बाद सख्ती से छोटा था, इसलिए बीच का पेड़ वांछित तत्व है।
अब बस बाएं पेड़ को दाहिने एक के साथ फिर से मिलाएं, बिना मध्य वाले के, और व्युत्पन्न एक्स कुंजियों के बिना छोड़ दिया गया है।

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

ऑपरेशन का समय अभी भी O (लॉग ₂ एन) है, क्योंकि हमने 2 बार स्प्लिट और 1 बार मर्ज लागू किया है।

स्रोत कोड:

 public Treap Remove(int x) { Treap l, m, r; Split(x - 1, out l, out r); r.Split(x, out m, out r); return Merge(l, r); }

सृजन का कार्य

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

दिलचस्प है, लेकिन क्या यह तेज हो सकता है?

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

हम लिंक को पेड़ में अंतिम जोड़े गए शीर्ष पर संग्रहीत करेंगे। अनुकूलता से, यह इसमें सबसे सही होगा - क्योंकि इसमें वर्तमान में निर्मित पेड़ की सभी कुंजियों की सबसे बड़ी कुंजी है। अब मान लीजिए कि अगली कुंजी x कुछ प्राथमिकता y के साथ आती है। इसे कहां रखा जाए?

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

मान लीजिए हम जड़ में आ गए। फिर यह पता चला कि पेड़ में सभी प्राथमिकताओं की तुलना में y अधिक है। हमारे पास (x, y) एक नई जड़ बनाने और उस पर हमारे पुराने बेटे के साथ एक पुराने पेड़ को लटकाने के अलावा कोई विकल्प नहीं है।

अगर हम जड़ में नहीं आए, तो स्थिति समान है। सही शाखा के कुछ शीर्ष पर (x ₀ , y ₀ ) हमारे पास y ₀ > y है । और उसके तत्काल दाहिने वंशज की प्राथमिकता y से कम है। कुंजी खोज ट्री की संरचना को संरक्षित करने और (x, y) को पेड़ में सबसे सही बनाने के लिए, हम इसे (x ₀ , y ₀ ) के नए दाहिने बेटे के रूप में निलंबित करते हैं, और संपूर्ण पुराना दाएँ दाएँ बाएँ बाएँ सबट्री (x, y) बन जाता है।

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

y = 4:

y = 16:

y = 11:

यह एल्गोरिथ्म O (N) के लिए क्यों काम करता है? ध्यान दें कि आप एक पेड़ के प्रत्येक जीवन में अधिकतम दो बार जाएंगे:

इसके प्रत्यक्ष जोड़ के साथ;
शायद सही शाखा में बने रहने के दौरान कुछ और जोड़ना। इसके तुरंत बाद, वह सही शाखा छोड़ देगी और अब और नहीं आएगी।

इस प्रकार, संक्रमणों की कुल संख्या 2N से अधिक नहीं है, और निर्माण का विषम व्यवहार O (N) है।

शुरुआत के लिए - कुंजी और प्राथमिकताओं के दिए गए सरणी पर निर्माण के लिए स्रोत कोड। यहां यह माना जाता है कि पेड़ के प्रत्येक शीर्ष पर भी Parent

संपत्ति होती है, और यह भी कि पहले से इस्तेमाल किए गए निजी शीर्ष निर्माण (एक पंक्ति में पांचवां) में इसी नाम के साथ वैकल्पिक पैरामीटर है।

 public static Treap Build(int[] xs, int[] ys) { Debug.Assert(xs.Length == ys.Length); var tree = new Treap(xs[0], ys[0]); var last = tree; for (int i = 1; i < xs.Length; ++i) { if (last.y > ys[i]) { last.Right = new Treap(xs[i], ys[i], parent: last); last = last.Right; } else { Treap cur = last; while (cur.Parent != null && cur.y <= ys[i]) cur = cur.Parent; if (cur.y <= ys[i]) last = new Treap(xs[i], ys[i], cur); else { last = new Treap(xs[i], ys[i], cur.Right, null, cur); cur.Right = last; } } } while (last.Parent != null) last = last.Parent; return last; }

सारांश

हमने निम्नलिखित गुणों के साथ एक पेड़ जैसी डेटा संरचना बनाई है:

अपने वर्टीकल की संख्या के संबंध में लगभग गारंटीशुदा लॉगरिदमिक ऊंचाई रखता है;
वृक्ष में किसी भी कुंजी की खोज करने के लिए लघुगणक समय की अनुमति देता है, इसे जोड़ें और इसे हटा दें;
इसके सभी तरीकों का स्रोत कोड 20 लाइनों से अधिक नहीं है, उन्हें आसानी से समझा जाता है और उनमें गलतियां करना बेहद मुश्किल है
स्मृति से कुछ ओवरहेड होता है, वास्तव में आत्म-संतुलन वाले पेड़ों की तुलना में, प्राथमिकताएं संग्रहीत करने के लिए।

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

निम्नलिखित भागों में:

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

सूत्रों का कहना है

मैं स्रोतों को एक बार और सभी के लिए इंगित करता हूं, वे सभी नियोजित लेखों के लिए समान हैं।

सबसे पहले, जब ये लेख लिखते हैं, तो मैं 2010 में एसीएम ICPC के प्रोग्रामिंग के लिए खार्कोव विंटर स्कूल में दिए गए विटाली गोल्डशेटिन के एक व्याख्यान पर आधारित हूं। इसे स्कूल की वीडियो गैलरी (वर्ष 2010, दिन 2) से डाउनलोड किया जा सकता है, जैसे ही यह फिर से काम करना शुरू करता है, क्योंकि हाल के दिनों में सर्वर भयावह रूप से रद्दी है।

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

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

डेरैड्स को पहले सीडेल, रायमुंड के एक लेख में प्रस्तावित किया गया था; आरागॉन, सेसिलिया आर (1996), यादृच्छिक खोज पेड़ । सिद्धांत रूप में, आप विषय पर पूरी जानकारी पा सकते हैं।

अभी के लिए बस इतना ही। मुझे आशा है कि आप रुचि रखते थे :)

कार्टेशियन ट्री: भाग 1. विवरण, संचालन, अनुप्रयोग