🌭 🛰️ 🔮 कार्टेशियन ट्री: भाग 3. इम्प्लांट की द्वारा कार्टिजियन ट्री 👏🏽 👆🏽 👨🏿‍⚕️

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

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

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

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

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

बहुत मजबूत जादू टोना

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

एक बार फिर से डैमामाइड की संरचना को याद करें। इसमें कुंजी x होता है , जिसके द्वारा व्युत्पन्न एक खोज पेड़ है, यादृच्छिक कुंजी y , जिसके द्वारा व्युत्पन्न एक गुच्छा है, और संभवतः, कुछ उपयोगकर्ता जानकारी (लागत) के साथ भी है। चलो असंभव करते हैं और चाबी एक्स के बिना व्युत्पन्न ... पर विचार करें। यही है, हमारे पास एक पेड़ होगा जिसमें कुंजी x बिल्कुल नहीं है, और चाबियाँ y यादृच्छिक हैं। तदनुसार, इसकी आवश्यकता क्यों है आमतौर पर समझ से बाहर है :)

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

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

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

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

मुख्य अनुप्रयोग

अब यह इस बारे में बात करने लायक है कि आखिर इस तरह की व्याख्या की आवश्यकता क्यों है।

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

स्टॉप-स्टॉप-स्टॉप, लेकिन मर्ज एक स्पष्ट कार्टेशियन पेड़ के लिए लिखा गया था। तो उसके एल्गोरिथ्म यहाँ फिर से काम करना होगा? वास्तव में नहीं। उसके कोड को फिर से देखें।

 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); } }

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

यह पता चला है कि आप और मैं यहां सबसे अधिक अभिमानी तरीके से मर्ज ऑपरेशन को धोखा दे रहे हैं: वह उम्मीद करती है कि उसे आदेशित कुंजियों के साथ पेड़ दिए जाएंगे, और हम बिना चाबी के पेड़ों को ताड़ देंगे :) हालांकि, यह धारणा कि पेड़ों में स्पष्ट चाबियाँ हैं और उन्हें आदेश दिया जाएगा। पेड़ों को मर्ज करें ताकि चाबियाँ L कुछ अर्थों में पेड़ की संरचना में आर की तुलना में पहले दिखाई दें - क्योंकि खोज पेड़ की स्थिति को संतुष्ट होना चाहिए। वह यह है: यदि वृक्ष L में N तत्व थे, और वृक्ष R में, क्रमशः M तत्व, तो वृक्ष के तत्वों के विलय के बाद R स्वतः N से N + M-1 में निहित संख्या प्राप्त कर लेगा। पेड़ की संरचना के अनुसार, मर्ज ऑपरेशन स्वचालित रूप से उन्हें उचित रूप से वितरित करेगा, और जिन प्राथमिकताओं को ध्यान में रखता है वे "अर्ध-संतुलन" का प्रदर्शन करेंगे। इस प्रकार, हमने "सरणी" L के दाईं ओर "सरणी" R को "जिम्मेदार ठहराया"।

सूत्रों के अनुसार, हमें केवल x

कुंजी के बिना एक नया ImplicitTreap

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

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

का अनुक्रम हमेशा संरक्षित होता है।

ऑरेंज तीर मर्ज में पुनरावृत्ति पथ है।

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

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

नया स्प्लिट ऑपरेशन कैसे करें? वह मानती है, पहले की तरह, दो मामले: रूट T बाएं परिणाम L या दाएं R में दिखाई देगा । यह बाईं ओर दिखाई देगा यदि सरणी में इसका सूचकांक x ₀ से कम है, अन्यथा सही में। और सरणी में पेड़ के शीर्ष का सूचकांक क्या है? हम पहले से ही जानते हैं कि दूसरे भाग से उसके साथ कैसे काम करना है: यह पेड़ के शीर्ष पर उपप्रकारों के आकार को संग्रहीत करने के लिए पर्याप्त है। फिर चयन प्रक्रिया आसानी से बहाल हो जाती है।

S _L को बाएं सबट्री का आकार दें ( T.Left.Size

)।

यदि एस _एल +1 ₀ x _{0 है} , तो रूट बाएं परिणाम में होगा। तो, आपको पुन: सही सबट्री काटने की आवश्यकता है। लेकिन x ₀ -S _L -1 द्वारा एक अन्य कुंजी द्वारा कट, क्योंकि S _L +1 तत्व पहले से ही वांछित वाम परिणाम में गिर गया है।

यदि S _L +1> x _{0 है} , तो मूल सही परिणाम में होगा। अब आपको बाएं सबट्री को पुन: काटने की आवश्यकता है। यह मामला काफी सममित नहीं है, जैसा कि पहले था: हमने सबरी को एक ही कुंजी x _{0 के} साथ काट दिया, क्योंकि इस कदम पर, पुनरावर्ती तत्वों को सही परिणाम में विभाजित करते हैं, और बाएं को नहीं।

चित्र एक्स ₀ = 6 में चिपकाए गए उपप्रकारों और विभाजन के साथ एक कार्टेशियन वृक्ष को दर्शाता है।

नई स्प्लिट के लिए स्रोत कोड, एक नई क्लास वर्कपीस के साथ, कुंजी रहित और एक अन्य निजी कंस्ट्रक्टर के साथ है।

मैं कई ऑपरेशनों के बिना अब तक स्प्लिट फिर से देता हूं - पाठक स्वतंत्र रूप से इन लाइनों को पुनर्स्थापित कर सकता है, वे अपने पुराने स्थानों से गायब नहीं हुए हैं। लेकिन हमें उपप्रकार के आकार को याद करने के बारे में नहीं भूलना चाहिए।

 private int y; public double Cost; public ImplicitTreap Left; public ImplicitTreap Right; public int Size = 1; private ImplicitTreap(int y, double cost, ImplicitTreap left = null, ImplicitTreap right = null) { this.y = y; this.Cost = cost; this.Left = left; this.Right = right; } public static int SizeOf(ImplicitTreap treap) { return treap == null ? 0 : treap.Size; } public void Recalc() { Size = SizeOf(Left) + SizeOf(Right) + 1; } //    -  Split public void Split(int x, out ImplicitTreap L, out ImplicitTreap R) { ImplicitTreap newTree = null; int curIndex = SizeOf(Left) + 1; if (curIndex <= x) { if (Right == null) R = null; else Right.Split(x - curIndex, out newTree, out R); L = new ImplicitTreap(y, Cost, Left, newTree); L.Recalc(); } else { if (Left == null) L = null; else Left.Split(x, out L, out newTree); R = new ImplicitTreap(y, Cost, newTree, Right); R.Recalc(); } }

अब जब हमने ऐरर स्प्लिट और मर्ज के लिए लिखा है, जो लॉगरिदमिक समय में काम करते हैं, यह समय है कि उनका उपयोग करें। चलो सरणी के साथ चारों ओर खेलते हैं।

एक सरणी के साथ खेल

डालने

फ़ोकस नंबर 1 - हम ओ (लॉग ₂ एन) के लिए आवश्यक स्थिति में सरणी के अंदर एक तत्व डालें, और हमेशा की तरह ओ (एन) के लिए नहीं।

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

• हमने सरणी T [0 को काट दिया ; एन) सरणियों पर सूचकांक स्थिति द्वारा एल [0; पोस) और आर [पॉज़; एन) ।

• हम सम्मिलित तत्व से एक शीर्ष से एक सरणी-ट्री बनाते हैं।

• बनाए गए सरणी को दाएं से बाएं परिणाम L पर असाइन करें, और उन दोनों को सही परिणाम R।

• T '[0 की एक सरणी मिला ; एन + 1) , जिसमें वांछित तत्व स्थिति स्थिति पर है, और शेष दाहिने हाथ को स्थानांतरित कर दिया गया है।

डालने का स्रोत कोड पूरी तरह से नहीं बदला है।

 public ImplicitTreap Add(int pos, double elemCost) { ImplicitTreap l, r; Split(pos, out l, out r); ImplicitTreap m = new ImplicitTreap(rand.Next(), elemCost); return Merge(Merge(l, m), r); }

निष्कासन

फोकस नंबर 2 - हमने उस स्थिति से एक तत्व को काट दिया जो इस स्थिति में है ।

फिर, प्रक्रिया सामान्य कार्टेशियन पेड़ों के समान है।

• हमने सरणी T [0 को काट दिया ; एन) सरणियों पर सूचकांक स्थिति द्वारा एल [0; पोस) और आर [पॉज़; एन) ।

• सही परिणाम R को इंडेक्स 1 (यूनिट!) द्वारा काटा जाता है। हमें सरणी M [Pos; एक तत्व से Pos + 1) (Pos स्थिति में पहले से खड़ा है), और सरणी R '[Pos + 1; एन) ।

• मर्ज सरण एल और आर '।

स्रोत कोड डाउनलोड करें:

 public ImplicitTreap Remove(int pos) { ImplicitTreap l, m, r; Split(pos, out l, out r); r.Split(1, out m, out r); return Merge(l, r); }

प्रति खंड में कई अनुरोध

फोकस नंबर 3: ओ (लॉग ₂ एन) के लिए, आप सरणी उप-सेगमेंट (सम / अधिकतम / न्यूनतम / उपस्थिति या लेबल की संख्या, आदि) पर सभी एक ही कई प्रश्न भी कर सकते हैं।

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

कॉल को Recalc()

, जो उसके वंशजों में गणना किए गए मापदंडों के आधार पर शीर्ष पर मूल्य के मूल्य को पुनर्गणना करता है।

खंड के लिए अनुरोध [ए; बी) मानक विधि का उपयोग करता है: सरणी से वांछित सेगमेंट को काटें (यह न भूलें कि पहले कट के बाद, सही परिणाम में वांछित सूचकांक कम हो गया है!) और इसके रूट में संग्रहीत पैरामीटर का मान लौटाएं।

स्रोत कोड - एक उदाहरण के रूप में, अधिकतम के लिए।

 public double MaxTreeCost; public static double CostOf(ImplicitTreap treap) { return treap == null ? double.NegativeInfinity : treap.MaxTreeCost; } public void Recalc() { Size = SizeOf(Left) + SizeOf(Right) + 1; MaxTreeCost = Math.Max(Cost, Math.Max(CostOf(Left), CostOf(Right))); } public double MaxCostOn(int A, int B) { ImplicitTreap l, m, r; this.Split(A, out l, out r); r.Split(B - A, out m, out r); return CostOf(m); }

एक सेगमेंट पर कई ऑपरेशन

फोकस नंबर 4: अब O (लॉग ₂ एन) के लिए हम ऐरे के सब-सेगमेंट पर दूसरे भाग से ऑपरेशन करेंगे: एक निरंतर जोड़ना, पेंटिंग, एक एकल मान पर सेट करना, आदि।

मर्ज और स्प्लिट काम करने के साथ, कारटेशियन वृक्ष में आस्थगित गणना का कार्यान्वयन पूरी तरह से अपरिवर्तित है। काम का मूल सिद्धांत एक ही है: किसी भी ऑपरेशन को करने से पहले, वंशजों को “एक वादा धक्का”। यदि आपको ऑपरेशन पूरा होने के बाद पिछले अनुभाग से कई प्रश्नों का समर्थन करने की आवश्यकता है, तो आपको "न्याय बहाल करने" की आवश्यकता है।

एक सेगमेंट पर एक ऑपरेशन करने के लिए, आपको पहले इस सेगमेंट को दो स्प्लिट कॉल के साथ पेड़ से काटने की जरूरत है, और फिर इसे दो मर्इल कॉल के साथ फिर से पेस्ट करें।

आलसी के लिए, मैं नए मर्ज / स्प्लिट कार्यान्वयन (वे 1-2 पंक्तियों के अनुसार भिन्न होते हैं) के साथ-साथ Push

पुश फ़ंक्शन के साथ जोड़ने के लिए पूर्ण स्रोत कोड लाते हैं:

 public double Add; public static void Push(ImplicitTreap treap) { if (treap == null) return; treap.Cost += treap.Add; if (treap.Left != null) treap.Left.Add += treap.Add; if (treap.Right != null) treap.Right.Add += treap.Add; treap.Add = 0; } public void Recalc() { Size = SizeOf(Left) + SizeOf(Right) + 1; } public static ImplicitTreap Merge(ImplicitTreap L, ImplicitTreap R) { // ! Push( L ); Push( R ); if (L == null) return R; if (R == null) return L; ImplicitTreap answer; if (Ly > Ry) { var newR = Merge(L.Right, R); answer = new ImplicitTreap(Ly, L.Cost, L.Left, newR); } else { var newL = Merge(L, R.Left); answer = new ImplicitTreap(Ry, R.Cost, newL, R.Right); } answer.Recalc(); return answer; } public void Split(int x, out ImplicitTreap L, out ImplicitTreap R) { Push(this); // ! ImplicitTreap newTree = null; int curIndex = SizeOf(Left) + 1; if (curIndex <= x) { if (Right == null) R = null; else Right.Split(x - curIndex, out newTree, out R); L = new ImplicitTreap(y, Cost, Left, newTree); L.Recalc(); } else { if (Left == null) L = null; else Left.Split(x, out L, out newTree); R = new ImplicitTreap(y, Cost, newTree, Right); R.Recalc(); } } public ImplicitTreap IncCostOn(int A, int B, double Delta) { ImplicitTreap l, m, r; this.Split(A, out l, out r); r.Split(B - A, out m, out r); m.Add += Delta; return Merge(Merge(l, m), r); }

अनुमत संचालन के बारे में एक छोटा सा विषयांतर:

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

• संबद्धता - किसी भी तत्व a, b, c के लिए हमारे पास (◦ b) = c = a ◦ (b ◦ c) है ।

• एक तटस्थ तत्व का अस्तित्व - सेट में एक तत्व ई ऐसा होता है जो किसी भी तत्व के लिए ए, = ई = ई e ए = ए ।

फिर इस तरह के ऑपरेशन के लिए खंडों के एक पेड़ को लागू करना संभव है, और इसी तरह के कारणों के लिए, एक कार्टेशियन पेड़।

पलटें

फोकस नंबर 5 एक सबसेप्शन फ्लिप है, अर्थात, रिवर्स ऑर्डर में इसके तत्वों का पुनर्व्यवस्था।

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

इसलिए, हम प्रत्येक शीर्ष पर एक बूलियन मान संग्रहीत करेंगे - ओवरटर्न बिट। यह एक आस्थगित वादा होगा "सरणी के इस खंड को भविष्य में तैनात करने की आवश्यकता है।" फिर, इस धारणा पर कि हम इस बिट को Push

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

मान लीजिए कि कुछ शीर्ष टी पर अवज्ञा को उलटने का वादा है। वास्तव में इसे शुरू करने के लिए, बस निम्नलिखित करें:

• वर्तमान शीर्ष पर एक वादा करें:

  T.Reversed = false;

• उनके बाएँ और दाएँ बेटे को स्वैप करें।

  temp = T.Left;
   टी.लिफ्ट = टी। राइट;
   टी। राइट = टेम्प;

• पदावनति का वादा बदलें। कृपया ध्यान दें: सही पर सेट न करें (हम नहीं जानते कि यह बिट अब तक वंशजों के साथ है!), लेकिन इसे बदल दें। इसके लिए ऑपरेशन ^ का उपयोग किया जाता है।

  T.Left.Reversed ^ = true;
   T.Right.Reversed ^ = सच;

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

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

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

 public bool Reversed; public static void Push(ImplicitTreap treap) { if (treap == null) return; //    -   if (!treap.Reversed) return; var temp = treap.Left; treap.Left = treap.Right; treap.Right = temp; treap.Reversed = false; if (treap.Left != null) treap.Left.Reversed ^= true; if (treap.Right != null) treap.Right.Reversed ^= true; } public ImplicitTreap Reverse(int A, int B) { ImplicitTreap l, m, r; this.Split(A, out l, out r); r.Split(B - A, out m, out r); m.Reversed ^= true; return Merge(Merge(l, m), r); }

अब आप पूरी तरह से नए तरीके से क्लासिक साक्षात्कार कार्य को हल कर सकते हैं :)

पाश अर्रे

फोकस # 6: चक्रीय पारी। इस ऑपरेशन का सार, उन लोगों के लिए जो नहीं जानते हैं, आंकड़े में समझाना आसान है।

बेशक, एक चक्रीय शिफ्ट हमेशा O (N) में की जा सकती है, लेकिन एक अंतर्निहित कार्टेशियन ट्री के रूप में सरणी को लागू करके, आप इसे O (लॉग ₂ एन) में शिफ्ट कर सकते हैं। K द्वारा छोड़ी गई शिफ्टिंग की प्रक्रिया ट्राइट है: हमने इंडेक्स K पर पेड़ को काट दिया और इसे रिवर्स ऑर्डर में गोंद कर दिया। दाईं ओर शिफ्ट सममित है, केवल इसे एनके इंडेक्स द्वारा काटने की आवश्यकता है।

 public ImplicitTreap ShiftLeft(int K) { ImplicitTreap l, r; this.Split(K, out l, out r); return Merge(r, l); }

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

सारांश

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

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

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

कार्टेशियन ट्री: भाग 3. इम्प्लांट की द्वारा कार्टिजियन ट्री