👨🏿‍🍳 🐈 🎅🏻 गतिशील पेड़ 👩🏼‍💼 🈸 ▫️

लेख पढ़ने से पहले, मैं एक आवेग कुंजी ( 2 , 3 , 4 ) द्वारा आवारा पेड़ों ( 1 ) और पेड़ों के बारे में पोस्ट देखने की सलाह देता हूं

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

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

और

क्रमशः। यदि आप नहीं जानते कि एक स्ट्रीम क्या है, और आपने इसे व्याख्यान में नहीं दिया है, तो Cormen में अपने ज्ञान को फिर से भरने के लिए जल्दी करें।

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

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

स्मृति और

समय। लेख पढ़ने के बाद, आप समझेंगे कि गतिशील पेड़ों का उपयोग करके इस समस्या को हल करना कितना आसान और सरल है।

समस्या का बयान

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

कल्पना कीजिए कि हमारे पास पेड़ों का एक सेट है, जिसके साथ युग्मित है

कोने। प्रत्येक पेड़ को जड़ से निलंबित कर दिया जाता है। हम अनुरोधों के निम्नलिखित सेट प्राप्त करते हैं।

make_tree(v) - वर्टेक्स v साथ एक नया पेड़ बनाएं
link(u, v) - एक पेड़ को जड़ के साथ सस्पेंड u पर वर्टेक्स v लिए निलंबित करें।
cut(u, v) - किनारे काट ( u , v )।
find_root(v) - उस वृक्ष की जड़ find_root(v) जहाँ शीर्ष v निहित है।
depth(v) - वर्टेक्स v की गहराई का पता लगाएं।

मैं पास के सभी अनुरोधों को संभालना चाहता हूं

समय।

ध्यान दें कि, यदि कोई cut और depth क्वेरी नहीं थी, तो असंतुष्ट सेट ( 5 , 6 , 7 ) की प्रणाली इस समस्या को हल कर सकती है।

गतिशील वृक्ष अपने भीतर खोज वृक्षों का उपयोग करते हैं। एक दिलचस्प विशेषता यह है कि मनमाने ढंग से संतुलित पेड़ों के साथ वे उपरोक्त सभी अनुरोधों के लिए मूल्यह्रास की प्रक्रिया करते हैं

। चर्म के पेड़ों पर, इन समान अनुरोधों के लिए परिशोधन प्रक्रिया की जाती है

। मेमोरी का उपयोग किया

।

आंतरिक दृश्य

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

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

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

ध्यान दें कि जो भाग विभाजन में भाग नहीं लेते हैं वे हमेशा अपने माता-पिता के साथ पथ के शीर्ष को जोड़ते हैं। प्रत्येक शीर्ष पर हम लिंक को संग्रहीत करेंगे। यदि शीर्ष पथ के शीर्ष पर स्थित है, तो लिंक उसके माता-पिता को इंगित करता है। पेड़ की जड़ में, लिंक None ओर None ।

महत्वपूर्ण कुंजी खोज पेड़

यहां मैं केवल संक्षेप में विचार को रेखांकित करूंगा, और विवरण के लिए कार्टेशियन पेड़ों के बारे में पोस्ट देखूंगा।

निहित कुंजी खोज पेड़ आम पेड़ों के समान हैं, केवल कुंजी का उपयोग उनमें नहीं किया गया है। आप उनमें खोज कर सकते हैं

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

 def find(v, k): if v == None: return None threshold = size(v.left) if k == threshold: return v if k < threshold and v.left != None: return find(v.left, k) if k > threshold and v.right != None: return find(v.right, k - threshold - 1) return None

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

वें तत्व, इसे हटा दें या इच्छित स्थान पर डालें। सभी ऑपरेशन संभव हैं

।

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

।

हमारे कार्य के संबंध में, निहित कुंजी खोज पेड़ हमें एक पथ को दो में कटौती करने, दो को एक में विलय करने और संदर्भित करने की अनुमति देते हैं

के लिए दूसरा तत्व

।

बेनकाब और उसके दोस्त

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

यदि आपने लिखा है, तो बाकी सब कुछ कमोबेश स्पष्ट दिखता है।

 def link(u, v): u.link = v expose(u)

हमने अभिभावक के लिए लिंक डाल दिया और expose को बनाए रखने के लिए expose किया।

 def cut(u, v): expose(v) u.link = None expose(u)

expose करने की पहली कॉल हमने वर्टिस u और v को अलग-अलग रास्तों में रखी। लिंक को रीसेट करने के लिए स्वतंत्र महसूस करें, और अपरिवर्तनीय बनाए रखने के लिए दूसरा expose चलाएं।

 def find_root(v): expose(v) return leftest(supportRoot(v))

एक्सपोज कॉल expose बाद expose वर्टेक्स v और रूट एक ही रेफरेंस ट्री में लेट जाएगा। यदि पेड़ संतुलित है, तो बस जड़ तक चढ़ो, और फिर नीचे बाईं ओर गाँठ पर जाओ। यह जड़ होगा। मैंने सशर्त रूप से supportRoot को रूट के माध्यम से बढ़ने का संकेत दिया, और सबसे बाईं ओर के तत्व के लिए वंश। एक स्प्ले ट्री के मामले में, supportRoot को supportRoot द्वारा बदल दिया जाता है।

 def depth(v): expose(v) return size(supportRoot(v)) - 1

फिर से, expose , फिर से वर्टेक्स v और रूट एक ही पथ पर। संदर्भ ट्री का आकार इस पथ में नोड्स की संख्या के बराबर है। हम जड़ तक बढ़ते हैं, हम सहायक पेड़ का आकार पाते हैं। किनारों की संख्या प्राप्त करने के लिए एक को घटाएं।

आइए सबसे निकटतम सामान्य पूर्वज ढूंढें।

 def lca(u, v): expose(u) expose(v) return leftest(supportRoot(u)).link

कागज के एक टुकड़े पर ड्रा करें जो होगा और समझ जाएगा कि यह वास्तव में एलकेए है। वैसे, क्या आपने देखा है कि यदि कोने अलग-अलग पेड़ों में हैं, तो प्रक्रिया कोई भी नहीं लौटेगी? क्या यह उसके लिए बहुत अच्छा नहीं है?

expose प्रक्रिया expose इस प्रकार है: हम उस संदर्भ ट्री की जड़ पाते हैं जिसमें वर्तमान नोड निहित है; पथ के शीर्ष पर जाने के लिए हम सबसे बाएं तत्व पर जाते हैं। ये ऑपरेशन संभव हैं

। अगले संदर्भ ट्री के लिंक का पालन करें और इसे पिछले एक के साथ मर्ज करें। हम ऐसा तब तक करेंगे जब तक हम प्रतिनिधित्व वाले पेड़ की जड़ तक नहीं पहुंच जाते।

हम cutout हेल्पर प्रक्रिया का उपयोग करेंगे, जो v के शीर्ष पर रास्ता काटती है और बच्चों को आवश्यक लिंक चिपकाती है।

 def expose(v): cutout(v) v = leftest(supportRoot(v)) while v.link != None: cutout(v.link) merge(supportRoot(v.link), (v - v.link), supportRoot(v)) v.link = None v = leftest(supportRoot(v)) return v

गैर-जड़ वाले पेड़

गतिशील पेड़ों को गैर-रूट तक विस्तारित किया जा सकता है। यह पेड़ों को फिर से उगाने में सक्षम होने के लिए पर्याप्त है। आइए निम्न प्रक्रिया को देखें:

 def revert(v): expose(v) reverse(supportRoot(v))

revert(v) प्रक्रिया वर्टेक्स v को वर्तमान रूट से जोड़ती है। ध्यान दें कि यदि वर्टेक्स v रूट था, तो केवल v और रूट के बीच के पथ पर तत्वों का क्रम बदल जाएगा। चूंकि पथ को एक निहित कुंजी द्वारा पेड़ों में संग्रहीत किया जाता है, इसलिए हम खंडों पर विलंबित संचालन ( 4 बार) के माध्यम से यू-टर्न को लागू कर सकते हैं।

किनारों को जोड़ना और हटाना तुच्छ है।

 def link_edge(u, v): revert(u) link(u, v)

 def cut_edge(u, v): revert(v) cut(u, v)

पहले मामले में, revert सुनिश्चित करता है कि u सबट्री की जड़ होगी। दूसरे, वर्टेक्स v , u का जनक होगा।
आप एक ही पेड़ के कोने के बीच की दूरी भी पा सकते हैं।

 def dist(u, v): revert(v) return depth(u)

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

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

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

के विश्लेषण

चलो

। उपरोक्त सभी प्रक्रियाओं के ऑपरेटिंग समय में expose प्रक्रिया और एक स्थिर की एक या दो शुरुआत होती है
संदर्भ पेड़ों पर संचालन की संख्या। रेफरेंस ट्री पर ऑपरेशन किए जाते हैं

।

आइए expose प्रक्रिया का expose । इसे शामिल करने दें

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

हम प्रत्येक वर्टेक्स को उप-आकार के आकार के बराबर वजन देते हैं जिसकी जड़ वह है। माता-पिता से बच्चे के लिए जाने वाली धार को भारी कहा जाता है यदि बच्चे का वजन माता-पिता के वजन से आधे से अधिक है। शेष पसलियों को प्रकाश कहा जाता है।

स्वीकृति। जड़ से किसी भी पत्ती के रास्ते पर प्रकाश पसलियों की संख्या अधिक नहीं होती है

।

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

, तो जड़ से किसी भी पत्ते तक मार्ग के साथ प्रकाश किनारों की संख्या अधिक नहीं होती है

।

पिछले बयान के आधार पर, सभी expose कॉल के लिए expose हम पथ में जोड़ते हैं

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

हम केवल दो मामलों में एक सिक्का ले सकते हैं: क) माता-पिता से expose गया था और उन्होंने हमें काट दिया, बी) अब एक आसन्न बढ़त पथ में निहित है। पहला मामला और नहीं हो सकता

समय। दूसरे मामले में, आसन्न चयनित किनारा हल्का होगा। यह और नहीं हो सकता

समय। पेड़ में काम के अंत में अधिक नहीं रह सकता है

भारी पसलियाँ। तो, कुल भारी पसलियों कोई और अधिक

। इस प्रकार, सभी परिचालन का कुल प्रसंस्करण समय

।

व्यावहारिक परीक्षण

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

अजगर कार्यान्वयन यहाँ पाया जा सकता है ।

जीवन के बारे में ...

यदि आप इस जगह पर पढ़ते हैं, तो मैं आपको बधाई देता हूं। मैं अपने पाठकों की दो श्रेणियों को संदेश देना चाहूंगा।

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

दूसरा प्रोजेक्ट यूलर और ब्रिंगमेस के बीच, ब्रिंगमेस और टॉपकोडर के बीच घूम रहा है। क्या आप गणित की समस्याओं की तलाश कर रहे हैं? सैद्धांतिक कंप्यूटर विज्ञान महान है, और आपको निश्चित रूप से एक जगह और एक कार्य मिलेगा। अनुमानित ( 8 , 9 ), घातांक ( 10 ), पैरामीटरयुक्त ( 11 ) एल्गोरिदम, संचार जटिलता ( 12 ), संरचनात्मक जटिलता ( 13 ) के बारे में पुस्तकों को देखें। यदि आप रुचि रखते हैं, तो सैद्धांतिक कंप्यूटर विज्ञान में अध्ययन करने के लिए आएं।

अपने अवसर को याद मत करो!

गतिशील पेड़