View source for विसंधित-सेट डेटा संरचना

{{Short description|Data structure for storing non-overlapping sets}}
{{Infobox data structure
|name=Disjoint-set/Union-find Forest
|type=multiway tree
|invented_by=[[Bernard A. Galler]] and [[Michael J. Fischer]]
|invented_year=1964
|
|space_avg   ={{math|O(''n'')}}<ref name="tarjan1975">{{cite journal|last1=Tarjan|first1=Robert Endre|author1-link=Robert E. Tarjan|year=1975|title=Efficiency of a Good But Not Linear Set Union Algorithm|journal=Journal of the ACM|volume=22|issue=2|pages=215&ndash;225|doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free }}</ref>
|space_worst ={{math|O(''n'')}}<ref name="tarjan1975"/>
|search_avg  ={{math|O(''α''(''n''))}}<ref name="tarjan1975"/>
|search_worst={{math|O(''α''(''n''))}}<ref name="tarjan1975"/>
|merge_avg   ={{math|O(''α''(''n''))}}<ref name="tarjan1975"/>
|merge_worst ={{math|O(''α''(''n''))}}<ref name="tarjan1975"/>
}}

[[File:Dsu disjoint sets init.svg|thumb|360px|<code>MakeSet</code> 8 सिंगलटन बनाता है।]]
[[File:Dsu disjoint sets final.svg|thumb|360px|के कुछ संचालन के बाद <code>Union</code>, कुछ उपसमुच्चय एक साथ समूहीकृत किए जाते हैं।]][[कंप्यूटर विज्ञान]] में, असम्बद्ध-[[सबसेट|सबउपसमुच्चय]] [[डेटा संरचना]], जिसे संघ-शोध डेटा संरचना या मर्ज-शोध उपसमुच्चय भी कहा जाता है, डेटा संरचना है जो भिन्न-भिन्न उपसमुच्चय (गैर-ओवरलैपिंग) [[सेट (गणित)|उपसमुच्चय (गणित)]] का संग्रह संग्रहीत करती है। समतुल्य रूप से, यह उपसमुच्चय के विभाजन को असंबद्ध उपसमुच्चय में संग्रहीत करता है। यह नए उपसमुच्चय जोड़ने, मर्ज करने वाले उपसमुच्चय (उन्हें उनके [[संघ (सेट सिद्धांत)|संघ (उपसमुच्चय सिद्धांत)]] द्वारा प्रतिस्थापित करने) एवं उपसमुच्चय के प्रतिनिधि सदस्य का शोधन करने के लिए संचालन प्रदान करता है। अंतिम संक्रिया कुशलतापूर्वक यह यह ज्ञात करने के लिए संभव बनाती है कि क्या कोई दो तत्व भिन्न-भिन्न उपसमुच्चय में हैं।

जबकि असंयुक्त-उपसमुच्चय डेटा संरचनाओं को प्रारम्भ करने की कई प्रविधि हैं, व्यवहार में उन्हें प्रायः विशेष कार्यान्वयन के साथ पहचाना जाता है जिसे असम्बद्ध-उपसमुच्चय वन कहा जाता है। यह विशेष प्रकार का [[वन (ग्राफ सिद्धांत)]] है जो संघों को निष्पादित करता है एवं निकट-निरंतर [[परिशोधित विश्लेषण]] में मिलता है। {{mvar|m}} के लिए  जोड़ का क्रम करने, संघ, या असम्बद्ध-उपसमुच्चय वन पर संचालन  {{mvar|n}} नोड्स को कुल समय की आवश्यकता होती है। {{math|[[Big O notation|''O'']](''m''α(''n''))}}, जहाँ {{math|α(''n'')}} अधिकतम मंद गति से बढ़ने [[व्युत्क्रम एकरमैन समारोह|व्युत्क्रम एकरमैन फंक्शन]] है। विसंधित वन प्रति-कार्रवाई के आधार पर इस प्रदर्शन का उत्तरदायित्व नहीं देते हैं। व्यक्तिगत संघ एवं शोध संचालन स्थिर समय से अधिक समय ले सकते हैं।  {{math|α(''n'')}} समय, किन्तु प्रत्येक संचालन विभिन्न उपसमुच्चय वन को स्वयं को समायोजित करने का कारण बनता है, जिससे क्रमिक संचालन तीव्र हो। असम्बद्ध-उपसमुच्चय वन असम्बद्ध रूप से इष्टतम एवं व्यावहारिक रूप से कुशल दोनों हैं।

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

== इतिहास ==

1964 में बर्नार्ड ए. गैलर एवं माइकल जे. फिशर द्वारा संधि भंग-उपसमुच्चय वनों का प्रथम बार वर्णन किया गया था।<ref name="Galler1964">{{cite journal|first1=Bernard A.|last1=Galler|author1-link=Bernard A. Galler|first2=Michael J.|last2=Fischer|author2-link=Michael J. Fischer|title=एक बेहतर तुल्यता एल्गोरिथ्म|journal=[[Communications of the ACM]]|volume=7|issue=5|date=May 1964|pages=301–303|doi=10.1145/364099.364331|s2cid=9034016 |doi-access=free}}. The paper originating disjoint-set forests.</ref> 1973 में, उनकी समय जटिलता को सीमित कर दिया गया था <math>O(\log^{*}(n))</math>, का [[पुनरावृत्त लघुगणक]] <math>n</math>, [[जॉन हॉपक्रॉफ्ट]] एवं [[जेफरी उल्मैन]] द्वारा<ref name="Hopcroft1973">{{cite journal|last1=Hopcroft|first1=J. E.|author1-link=John Hopcroft|last2=Ullman|first2=J. D.|author2-link=Jeffrey Ullman|year=1973|title=मर्जिंग एल्गोरिदम सेट करें|journal=SIAM Journal on Computing|volume=2|issue=4|pages=294&ndash;303|doi=10.1137/0202024}}</ref> 1975 में, [[रॉबर्ट टार्जन]] प्रमाणित करने वाले प्रथम व्यक्ति थे। <math>O(m\alpha(n))</math> एल्गोरिथम की समय जटिलता पर ऊपरी सीमा,<ref name="Tarjan1984">{{cite journal|first1=Robert E.|last1=Tarjan|author1-link=Robert E. Tarjan|first2=Jan|last2=van Leeuwen|author2-link=Jan van Leeuwen|title=सेट यूनियन एल्गोरिथम का वर्स्ट-केस विश्लेषण|journal=Journal of the ACM|volume=31|issue=2|pages=245–281|year=1984|doi= 10.1145/62.2160|s2cid=5363073 |doi-access=free}}</ref> एवं, 1979 में, दिखाया कि यह प्रतिबंधित विषय के लिए निचली सीमा थी।<ref name="Tarjan1979">{{cite journal|first=Robert Endre|last=Tarjan|author-link=Robert E. Tarjan|year=1979|title=एल्गोरिद्म का एक वर्ग जिसे असंयुक्त सेट बनाए रखने के लिए गैर-रैखिक समय की आवश्यकता होती है|journal=Journal of Computer and System Sciences|volume=18|issue=2|pages=110&ndash;127|doi=10.1016/0022-0000(79)90042-4|doi-access=free }}</ref> 1989 में, [[माइकल फ्रेडमैन]] एवं [[माइकल सक्स (गणितज्ञ)]] <math>\Omega(\alpha(n))</math> ने इसे दिखाया। (परिशोधित) शब्दों को किसी भी असम्बद्ध-उपसमुच्चय डेटा संरचना प्रति संचालन द्वारा एक्सेस किया जाना चाहिए,<ref name="Fredman1989">{{cite journal|first1=M.|last1=Fredman|author-link=Michael Fredman|first2=M.|last2=Saks|title=गतिशील डेटा संरचनाओं की सेल जांच जटिलता|journal=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing|pages=345&ndash;354|date=May 1989|doi=10.1145/73007.73040|isbn=0897913078|s2cid=13470414|quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires Ω(''m'' α(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets. |doi-access=free}}</ref> जिससे डेटा संरचना की इष्टतमता प्रमाणित होती है।

1991 में, गैलील एवं इटालियनो ने भिन्न-भिन्न उपसमुच्चयों के लिए डेटा संरचनाओं का सर्वेक्षण प्रकाशित किया।<ref name="Galil1991">{{cite journal|first1=Z.|last1=Galil|first2=G.|last2=Italiano|title=असंयुक्त सेट संघ समस्याओं के लिए डेटा संरचनाएं और एल्गोरिदम।|journal=ACM Computing Surveys|volume=23|issue=3|pages=319&ndash;344|year=1991|doi=10.1145/116873.116878|s2cid=207160759 }}</ref> 1994 में, रिचर्ड जे. एंडरसन एवं हीथर वोल ने यूनियन-फाइंड के समानांतर संस्करण का वर्णन किया जिसे कभी ब्लॉक करने की आवश्यकता नहीं है।<ref name="Anderson1994">{{cite conference|first1=Richard J.|last1=Anderson|first2=Heather|last2=Woll|title=संघ-खोज समस्या के लिए प्रतीक्षा-मुक्त समानांतर एल्गोरिदम|conference=23rd ACM Symposium on Theory of Computing|year=1994|pages=370&ndash;380}}</ref> 2007 में, सिल्वेन कॉनचॉन एवं जीन-क्रिस्टोफ़ फ़िलिआट्रे ने असंयुक्त-उपसमुच्चय वन डेटा संरचना का अर्ध-स्थायी डेटा संरचना संस्करण विकसित किया एवं [[सबूत सहायक|प्रमाण सहायक]] [[Coq]] का उपयोग करके इसकी शुद्धता को औपचारिक रूप दिया।<ref name="Conchon2007">{{cite conference|first1=Sylvain|last1=Conchon|first2=Jean-Christophe|last2=Filliâtre|contribution=A Persistent Union-Find Data Structure|title=एमएल पर एसीएम सिगप्लान वर्कशॉप|location=Freiburg, Germany|date=October 2007|url=https://www.lri.fr/~filliatr/puf/}}</ref> सेमी-पर्सिस्टेंट का अर्थ है कि संरचना के पूर्व संस्करणों को कुशलता से बनाए रखा जाता है, किन्तु डेटा संरचना के पूर्व संस्करणों तक पहुंच पश्चात के संस्करणों को अमान्य कर देती है। उनका सबसे तीव्र कार्यान्वयन गैर-स्थायी एल्गोरिदम के रूप में लगभग उतना ही कुशल प्रदर्शन प्राप्त करता है। वे जटिलता विश्लेषण नहीं करते हैं।

समस्याओं के प्रतिबंधित वर्ग पर उत्तम प्रदर्शन के साथ भिन्न-भिन्न उपसमुच्चय डेटा संरचनाओं के रूपों पर भी विचार किया गया है। गैबो एवं टारजन ने दिखाया कि यदि संभावित संघों को कुछ खास प्रविधियों से प्रतिबंधित किया जाता है, तो वास्तव में रैखिक समय एल्गोरिथम संभव है।<ref>Harold N. Gabow, Robert Endre Tarjan, "A linear-time algorithm for a special case of disjoint set union," Journal of Computer and System Sciences, Volume 30, Issue 2, 1985, pp. 209–221, ISSN 0022-0000, https://doi.org/10.1016/0022-0000(85)90014-5</ref>


== प्रतिनिधित्व ==

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

वन में ग्रंथियो को किसी भी प्रकार से प्रयोग के लिए सुविधाजनक रूप से संग्रहीत किया जा सकता है, किन्तु सामान्य प्रक्रिया उन्हें सरणी में संग्रहीत करना है। इस विषय में, माता-पिता को उनके सरणी सूचकांक द्वारा इंगित किया जा सकता है। प्रत्येक सरणी प्रविष्टि की आवश्यकता होती है, पेरेंट पॉइंटर के लिए स्टोरेज के बिट्स {{math|Θ(log ''n'')}} शेष प्रविष्टि के लिए तुलनात्मक या अर्घ्य मात्रा में संग्रहण की आवश्यकता होती है, इसलिए वन को संग्रहीत करने के लिए आवश्यक बिट्स की संख्या {{math|Θ(''n'' log ''n'')}} है, यदि कोई कार्यान्वयन निश्चित आकार के ग्रंथियो का उपयोग करता है (जिससे वन के अधिकतम आकार को सीमित किया जा सकता है), तो आवश्यक भंडारण रैखिक {{mvar|n}} होता है।

== संचालन ==

डिसजॉइंट-उपसमुच्चय डेटा स्ट्रक्चर्स तीन संचालनों का समर्थन करते हैं, नया उपसमुच्चय बनाना जिसमें नया तत्व होता है; किसी दिए गए तत्व वाले उपसमुच्चय के प्रतिनिधि को शोधन; एवं दो उपसमुच्चयों का विलय करना।

<code>MakeSet</code>  संचालन नए तत्व को नए उपसमुच्चय में जोड़ता है जिसमें केवल नया तत्व होता है, एवं नया उपसमुच्चय डेटा संरचना में जोड़ा जाता है। यदि डेटा संरचना को उपसमुच्चय के विभाजन के रूप में देखा जाता है, तो <code>MakeSet</code> संचालन नए तत्व को जोड़कर उपसमुच्चय को बढ़ाता है, एवं यह नए तत्व को केवल नए तत्व वाले नए उपसमुच्चय में डालकर उपस्थित विभाजन का विस्तार करता है।

असंबद्ध वन में, <code>MakeSet</code> नोड के पैरेंट पॉइंटर एवं नोड के आकार या रैंक को आवाक्षरित करता है। यदि जड़ को नोड द्वारा दर्शाया जाता है जो स्वयं को इंगित करता है, तो निम्नलिखित स्यूडोकोड का उपयोग करके तत्व जोड़ना वर्णित किया जा सकता है।

 '''function''' MakeSet(''x'') '''is'''
     '''if''' ''x'' is not already in the forest '''then'''
         ''x''.parent := ''x''
         ''x''.size := 1     ''// if nodes store size''
         ''x''.rank := 0     ''// if nodes store rank''
     '''end if'''

 '''end function'''

इस संचालन में निरंतर समय जटिलता है। विशेष रूप से, प्रारंभ a असंबद्ध उपसमुच्चय वन के साथ {{mvar|n}} नोड्स की आवश्यकता {{math|''O''(''n'')}} है।

व्यवहार में, <code>MakeSet</code>  संचालन से पूर्व होना चाहिए जो मेमोरी को होल्ड करने के लिए {{math|x}} आवंटित करता है, जब तक स्मृति आवंटन परिशोधित निरंतर-समय का संचालन है, यह उचित [[गतिशील सरणी]] कार्यान्वयन के लिए है, यह यादृच्छिक-उपसमुच्चय वन के स्पर्शोन्मुख प्रदर्शन को परिवर्तित नहीं करता है।

=== उपसमुच्चय प्रतिनिधि शोधन === <code>Find</code> ई> संचालन निर्दिष्ट क्वेरी नोड से पैरेंट पॉइंटर्स की श्रृंखला {{mvar|x}} का अनुसरण करता है, जब तक यह मूल तत्व तक नहीं पहुंच जाता। यह मूल तत्व उस उपसमुच्चय {{mvar|x}} का प्रतिनिधित्व करता है {{mvar|x}} स्वयं <code>Find</code> यह जिस मूल तत्व तक पहुंचता है उसे वापस कर देता है।

<code>Find</code> प्रदर्शन कर रहा है, संचालन वन में सुधार के लिए महत्वपूर्ण अवसर प्रस्तुत करता है। a में समय <code>Find</code> संचालन पैरेंट पॉइंटर्स का पीछा करते हुए <code>Find</code> संचालन व्यय किया जाता है, इसलिए अनुनय वाला पेड़ तीव्रता से आगे बढ़ता है । जब <code>Find</code> निष्पादित किया जाता है, उत्तराधिकार में प्रत्येक पैरेंट पॉइंटर का अनुसरण करने की तुलना में मूल तक पहुंचने की कोई तीव्र प्रक्रिया नहीं होती है। चूंकि, इस शोध के समय देखे गए पैरेंट पॉइंटर्स को मूल के निकट इंगित करने के लिए अद्यतन किया जा सकता है। चूँकि मूल के मार्ग में देखा गया प्रत्येक तत्व उसी उपसमुच्चय का भाग होता है, इससे वन में संग्रहीत उपसमुच्चय परिवर्तित नहीं होते हैं। किन्तु यह भविष्य बनाता है <code>Find</code> संचालन तीव्रता से, न केवल क्वेरी नोड एवं मूल के मध्य के नोड्स के लिए, जबकि उनके वंशजों के लिए भी यह अद्यतन असंबद्ध-उपसमुच्चय वन की परिशोधित प्रदर्शन आश्वाशन का महत्वपूर्ण भाग है।

<code>Find</code> के लिए कई एल्गोरिदम हैं, जो विषम रूप से इष्टतम समय जटिलता प्राप्त करते हैं। एल्गोरिदम का परिवार, जिसे पथ संपीड़न के रूप में जाना जाता है, प्रत्येक नोड को क्वेरी नोड एवं मूल बिंदु से मूल के मध्य बनाता है। पथ संपीड़न को साधारण पुनरावर्तन का उपयोग करके निम्नानुसार कार्यान्वित किया जा सकता है।

 '''function''' Find(''x'') '''is'''
     '''if''' ''x''.parent ≠ ''x'' '''then'''
         ''x''.parent := Find(''x''.parent)
         '''return''' ''x''.parent
     '''else'''
         '''return''' ''x''
     '''end if'''

 '''end function'''
यह कार्यान्वयन दो मार्ग बनाता है, पेड़ के ऊपर एवं पीछे की ओर, क्वेरी नोड से मूल तक पथ को संग्रहीत करने के लिए पर्याप्त स्क्रैच मेमोरी की आवश्यकता होती है (उपरोक्त स्यूडोकोड में, कॉल स्टैक का उपयोग करके पथ को स्पष्ट रूप से दर्शाया गया है)। इसे एक ही दिशा में दोनों पास करके स्मृति की निरंतर मात्रा में घटाया जा सकता है। निरंतर मेमोरी कार्यान्वयन क्वेरी नोड से मूल तक दो बार चलता है, एक बार मूल को शोधने के लिए एवं एक बार पॉइंटर्स को अपडेट करने के लिए:

 फ़ंक्शन Find(''x'') है
     ''जड़'' := ''x''
     जबकि ''मूल''.पैरेंट ≠ ''मूल'' करते हैं
         ''मूल'' := ''मूल''.पैरेंट
     जबकि समाप्त करें
 
     जबकि ''x''.parent ≠ ''root'' करते हैं
         ''अभिभावक'' := ''x''.जनक
         ''x''.parent := ''जड़''
         ''एक्स'' := ''पैरेंट''
     जबकि समाप्त करें
 
     रिटर्न ''मूल''
 अंत फंक्शन

रॉबर्ट ई. टारजन एवं [[जॉन वैन लीउवेन]] ने भी वन-पास विकसित किया <code>Find</code> एल्गोरिदम जो सबसे खराब स्थिति वाली जटिलता को बनाए रखते हैं किन्तु व्यवहार में अधिक कुशल होते हैं।<ref name="Tarjan1984"/>  इन्हें पाथ स्प्लिटिंग एवं पाथ हॉलिंग कहा जाता है। ये दोनों क्वेरी नोड एवं मूल के मध्य के पथ पर नोड्स के पैरेंट पॉइंटर्स को अपडेट करते हैं। पथ विभाजन प्रत्येक पैरेंट पॉइंटर को उस पथ पर एक पॉइंटर द्वारा नोड के दादा-दादी के लिए बदल देता है:

 फ़ंक्शन Find(''x'') है
     जबकि ''x''.parent ≠ ''x'' करते हैं
         (''x'', ''x''.parent) := (''x''.parent, ''x''.parent.parent)
     जबकि समाप्त करें
     रिटर्न ''एक्स''
 अंत फंक्शन

पाथ हॉल्टिंग समान रूप से काम करता है किन्तु केवल हर दूसरे पैरेंट पॉइंटर को बदलता है:

 फ़ंक्शन Find(''x'') है
     जबकि ''x''.parent ≠ ''x'' करते हैं
         ''x''.parent := ''x''.parent.parent
         ''x'' := ''x''.parent
     जबकि समाप्त करें
     रिटर्न ''एक्स''
 अंत फंक्शन

=== दो उपसमुच्चयों का विलय ===

संचालन <code>Union(''x'', ''y'')</code> युक्त उपसमुच्चय को प्रतिस्थापित करता है {{mvar|x}} एवं उपसमुच्चय युक्त {{mvar|y}} उनके संघ के साथ।  <code>Union</code> पहला उपयोग करता है <code>Find</code> युक्त पेड़ों की जड़ों का निर्धारण करने के लिए {{mvar|x}} एवं {{mvar|y}}. यदि जड़ें समान हैं, तो कुछ एवं करने को नहीं है। अन्यथा, दो पेड़ों को मिला देना चाहिए। यह या तो पैरेंट पॉइंटर उपसमुच्चय करके किया जाता है {{mvar|x}} की जड़ {{mvar|y}}'s, या के पैरेंट पॉइंटर को उपसमुच्चय करना {{mvar|y}} की जड़ {{mvar|x}}'एस।

कौन सा नोड माता-पिता बनने का विकल्प पेड़ पर भविष्य के संचालन की जटिलता के परिणाम हैं। अगर इसे लापरवाही से किया जाए तो पेड़ अत्यधिक ऊंचे हो सकते हैं। उदाहरण के लिए, मान लीजिए <code>Union</code> हमेशा पेड़ युक्त बनाया {{mvar|x}} युक्त पेड़ का एक सबपेड़ {{mvar|y}}. एक ऐसे वन से शुरू करें जिसे अभी-अभी तत्वों के साथ आरंभ किया गया है <math>1, 2, 3, \ldots, n,</math> एवं निष्पादित करें <code>{{math|Union(1, 2)}}</code>, <code>{{math|Union(2, 3)}}</code>, ..., <code>{{math|Union(''n'' - 1, ''n'')}}</code>. परिणामी वन में एक ही पेड़ होता है जिसकी जड़ होती है {{mvar|n}}, एवं 1 से पथ {{mvar|n}} पेड़ में हर नोड से होकर गुजरता है। इस वन के लिए, चलाने का समय <code>Find(1)</code> है {{math|''O''(''n'')}}.

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

==== आकार से संघ ====

आकार के संघ के मामले में, एक नोड अपने आकार को संग्रहीत करता है, जो केवल इसके वंशजों की संख्या है (नोड सहित)। जब पेड़ जड़ों के साथ {{mvar|x}} एवं {{mvar|y}} मर्ज किए जाते हैं, तो अधिक डिसेंडेंट वाला नोड पैरेंट बन जाता है। यदि दो नोड्स के वंशजों की संख्या समान है, तो कोई भी माता-पिता बन सकता है। दोनों ही मामलों में, नए पैरेंट नोड का आकार उसके वंशजों की नई कुल संख्या पर उपसमुच्चय होता है।

 फंक्शन Union(''x'', ''y'') है
     '' // नोड्स को जड़ों से बदलें ''
     ''x'' := Find(''x'')
     ''वाई'' := फाइंड(''वाई'')
 
     अगर ''x'' = ''y'' तब
         वापसी '' // x एवं y पहले से ही एक ही उपसमुच्चय में हैं ''
     अगर अंत
 
     ''// यदि आवश्यक हो, तो यह सुनिश्चित करने के लिए चर स्वैप करें ''
     ''// x के कम से कम उतने वंशज हैं जितने y''
     अगर ''x''.size <''y''.size तो
         (''x'', ''y'') := (''y'', ''x'')
     अगर अंत
 
     '' // एक्स को नया मूल बनाएं ''
     ''य''. जनक := ''x''
     '' // x का आकार अपडेट करें ''
     ''एक्स''.साइज := ''एक्स''.साइज + ''वाई''.साइज
 अंत फंक्शन

आकार को स्टोर करने के लिए आवश्यक बिट्स की संख्या स्पष्ट रूप से स्टोर करने के लिए आवश्यक बिट्स की संख्या है {{mvar|n}}. यह वन के आवश्यक भंडारण में एक स्थिर कारक जोड़ता है।

==== रैंक द्वारा संघ ====

रैंक द्वारा संघ के लिए, एक नोड इसे संग्रहीत करता है {{em|rank}}, जो इसकी ऊंचाई के लिए एक ऊपरी सीमा है। जब एक नोड को इनिशियलाइज़ किया जाता है, तो उसकी रैंक शून्य पर उपसमुच्चय हो जाती है। पेड़ों को जड़ों से मिलाने के लिए {{mvar|x}} एवं {{mvar|y}}, पहले उनके रैंकों की तुलना करें। यदि रैंक भिन्न हैं, तो बड़ा रैंक पेड़ माता-पिता बन जाता है, एवं रैंक {{mvar|x}} एवं {{mvar|y}} बदलें नहीं। यदि रैंक समान हैं, तो कोई भी माता-पिता बन सकता है, किन्तु नए माता-पिता की रैंक में एक की वृद्धि होती है। जबकि एक नोड का रैंक स्पष्ट रूप से इसकी ऊंचाई से संबंधित होता है, रैंकों को संग्रहित करना ऊंचाइयों को संग्रहित करने से अधिक कुशल होता है। एक नोड की ऊंचाई एक के समय बदल सकती है <code>Find</code> संचालन, इसलिए रैंकों को संग्रहित करने से ऊंचाई को सही रखने के अतिरिक्त प्रयास से बचा जाता है। स्यूडोकोड में, रैंक द्वारा संघ है:

 फंक्शन Union(''x'', ''y'') है
     '' // नोड्स को जड़ों से बदलें ''
     ''x'' := Find(''x'')
     ''वाई'' := फाइंड(''वाई'')
 
     अगर ''x'' = ''y'' तब
         वापसी '' // x एवं y पहले से ही एक ही उपसमुच्चय में हैं ''
     अगर अंत
 
     ''// यदि आवश्यक हो, तो यह सुनिश्चित करने के लिए चर का नाम बदलें ''
     ''// x का रैंक कम से कम y जितना बड़ा है''
     अगर ''x''.रैंक <''y''.रैंक तब
         (''x'', ''y'') := (''y'', ''x'')
     अगर अंत
 
     '' // एक्स को नया मूल बनाएं ''
     ''य''. जनक := ''x''
     ''// यदि आवश्यक हो, x के रैंक में वृद्धि ''
     अगर ''x''.रैंक = ''y''.रैंक तब
         ''x''.रैंक := ''x''.रैंक + 1
     अगर अंत
 अंत फंक्शन

यह दिखाया जा सकता है कि प्रत्येक नोड में रैंक है <math>\lfloor \log n \rfloor</math> या कम।<ref name="Cormen2009"/>  नतीजतन प्रत्येक रैंक में संग्रहीत किया जा सकता है {{math|''O''(log log ''n'')}} बिट्स एवं सभी रैंकों को स्टोर किया जा सकता है {{math|''O''(''n'' log log ''n'')}} बिट्स। यह रैंकों को वन के आकार का एक विषम रूप से नगण्य भाग बनाता है।

उपरोक्त कार्यान्वयन से यह स्पष्ट है कि नोड का आकार एवं रैंक तब तक मायने नहीं रखता जब तक कि नोड पेड़ की जड़ न हो। एक बार जब एक नोड एक बच्चा बन जाता है, तो इसका आकार एवं रैंक फिर कभी नहीं देखा जाता है।

== समय जटिलता ==

एक असम्बद्ध-उपसमुच्चय वन कार्यान्वयन जिसमें <code>Find</code> पैरेंट पॉइंटर्स को अपडेट नहीं करता है, एवं जिसमें <code>Union</code> पेड़ की ऊंचाई को नियंत्रित करने का प्रयास नहीं करता, ऊंचाई वाले पेड़ हो सकते हैं {{math|''O''(''n'')}}. ऐसी स्थिति में द <code>Find</code> एवं <code>Union</code> संचालन की आवश्यकता है {{math|''O''(''n'')}} समय।

यदि कोई कार्यान्वयन अकेले पथ संपीड़न का उपयोग करता है, तो एक क्रम {{mvar|n}} <code>MakeSet</code> संचालन, उसके बाद तक {{math|''n'' − 1}} <code>Union</code> संचालन एवं {{math|''f''}} <code>Find</code> संचालन, का सबसे खराब समय चल रहा है <math>\Theta(n+f \cdot \left(1 + \log_{2+f/n} n\right))</math>.<ref name="Cormen2009">{{cite book|first1=Thomas H.|last1=Cormen| author1-link=Thomas H. Cormen|first2=Charles E.|last2=Leiserson|author2-link=Charles E. Leiserson|first3=Ronald L.|last3=Rivest| author3-link=Ronald L. Rivest|first4=Clifford|last4=Stein|author4-link=Clifford Stein|title=एल्गोरिदम का परिचय| edition=Third|publisher=MIT Press|chapter=Chapter 21: Data structures for Disjoint Sets|pages=571–572| isbn=978-0-262-03384-8| year=2009|title-link=एल्गोरिदम का परिचय }}</ref>
रैंक द्वारा संघ का उपयोग करना, किन्तु माता-पिता पॉइंटर्स को अपडेट किए बिना <code>Find</code>, का चलने का समय देता है <math>\Theta(m \log n)</math> के लिए {{mvar|m}} किसी भी प्रकार का संचालन, तक {{mvar|n}} जिनमें से हैं <code>MakeSet</code> संचालन।<ref name="Cormen2009"/>

आकार या रैंक द्वारा संघ के साथ पथ संपीड़न, विभाजन, या आधा करने का संयोजन, चलने के समय को कम करता है {{mvar|m}} किसी भी प्रकार का संचालन, तक {{mvar|n}} जिनमें से हैं <code>MakeSet</code> संचालन, करने के लिए <math>\Theta(m\alpha(n))</math>.<ref name="Tarjan1984"/><ref name="Tarjan1979"/>  यह प्रत्येक संचालन का परिशोधन विश्लेषण करता है <math>\Theta(\alpha(n))</math>. यह असम्बद्ध रूप से इष्टतम है, जिसका अर्थ है कि प्रत्येक असम्बद्ध उपसमुच्चय डेटा संरचना का उपयोग करना चाहिए <math>\Omega(\alpha(n))</math> प्रति संचालन परिशोधित समय।<ref name="Fredman1989"/>  यहाँ, फंक्शन <math>\alpha(n)</math> एकरमैन फ़ंक्शन # उलटा है। व्युत्क्रम एकरमैन फ़ंक्शन असाधारण रूप से धीरे-धीरे बढ़ता है, इसलिए यह कारक है {{math|4}} या किसी के लिए कम {{mvar|n}} जो वास्तव में भौतिक ब्रह्मांड में लिखा जा सकता है। यह असंबद्ध-उपसमुच्चय संचालन को व्यावहारिक रूप से परिशोधित स्थिर समय बनाता है।

=== यूनियन-फाइंड === की O(m log* n) समय जटिलता का प्रमाण

एक असम्बद्ध-उपसमुच्चय वन के प्रदर्शन का सटीक विश्लेषण कुछ जटिल है। चूंकि, एक बहुत सरल विश्लेषण है जो यह साबित करता है कि किसी के लिए परिशोधित समय {{mvar|m}} <code>Find</code> या <code>Union</code> एक असम्बद्ध-उपसमुच्चय वन युक्त पर संचालन {{mvar|n}} वस्तुएं हैं {{math|''O''(mlog<sup>*</sup> ''n'')}}, कहाँ {{math|log<sup>*</sup>}} पुनरावृत्त लघुगणक को दर्शाता है।<ref>[[Raimund Seidel]], Micha Sharir. "Top-down analysis of path compression", SIAM J. Comput. 34(3):515–525, 2005</ref><ref>{{cite journal|last1=Tarjan|first1=Robert Endre|year=1975|title=एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिथम की दक्षता|url=http://portal.acm.org/citation.cfm?id=321884|journal=Journal of the ACM|volume=22| issue=2| pages=215–225 | doi=10.1145/321879.321884|hdl=1813/5942|s2cid=11105749|hdl-access=free}}</ref><ref>{{cite journal| last1=Hopcroft|first1=J. E.| last2=Ullman|first2=J. D.|year=1973|title=मर्जिंग एल्गोरिदम सेट करें|journal=SIAM Journal on Computing|volume=2| issue=4| pages=294–303 | doi=10.1137/0202024}}</ref><ref>[[Robert E. Tarjan]] and [[Jan van Leeuwen]]. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.</ref>

{{anchor|increasing rank lemma}}प्रमेयिका 1: जैसे-जैसे डिसजॉइंट-उपसमुच्चय डेटा स्ट्रक्चर#डिसजॉइंट-उपसमुच्चय वन मूल के साथ-साथ पथ का अनुसरण करता है, नोड का रैंक बढ़ता जा रहा है।

{{math proof| claim that as Find and Union operations are applied to the data set, this fact remains true over time. Initially when each node is the root of its own tree, it's trivially true. The only case when the rank of a node might be changed is when the [[Disjoint-set data structure#Disjoint-set forests|Union by Rank]] operation is applied. In this case, a tree with smaller rank will be attached to a tree with greater rank, rather than vice versa. And during the find operation, all nodes visited along the path will be attached to the root, which has larger rank than its children, so this operation won't change this fact either.}}

<nowiki>{{anchor|min subtree size lemma}लेम्मा 2: एक नोड </nowiki>{{mvar|u}} जो रैंक के साथ सबपेड़ का मूल है {{mvar|r}} कम से कम है <math>2^r</math> नोड्स।

{{math proof| Initially when each node is the root of its own tree, it's trivially true. Assume that a node {{mvar|u}} with rank {{mvar|r}} has at least {{math|2<sup>''r''</sup>}} nodes. Then when two trees with rank {{mvar|r}} are merged using the operation [[Disjoint-set data structure#Disjoint-set forests|Union by Rank]], a tree with rank {{math|''r'' + 1}} results, the root of which has at least <math>2^r + 2^r = 2^{r + 1}</math> nodes.}}लेम्मा 3: रैंक के नोड्स की अधिकतम संख्या {{mvar|r}} ज्यादा से ज्यादा है <math>\frac{n}{2^r}.</math>

{{math proof| From [[#min subtree size lemma|lemma 2]], we know that a node {{mvar|u}} which is root of a subtree with rank {{mvar|r}} has at least <math>2^r</math> nodes. We will get the maximum number of nodes of rank {{mvar|r}} when each node with rank {{mvar|r}} is the root of a tree that has exactly <math>2^r</math> nodes. In this case, the number of nodes of rank {{mvar|r}} is <math>\frac{n}{2^r}.</math>}}

सुविधा के लिए, हम यहां बकेट को परिभाषित करते हैं: एक बकेट एक उपसमुच्चय है जिसमें विशेष रैंक वाले वर्टिकल होते हैं।

हम कुछ बकेट बनाते हैं एवं उनके रैंक के अनुसार बाल्टियों में वर्टिकल डालते हैं। यानी, रैंक 0 वाले कोने शून्य बकेट में जाते हैं, रैंक 1 वाले वर्टिकल पहली बकेट में जाते हैं, रैंक 2 एवं 3 वाले वर्टिकल दूसरी बकेट में जाते हैं। अगर {{mvar|B}}-थ बकेट में अंतराल से रैंक वाले वर्टिकल होते हैं <math>\left[r, 2^r - 1\right] = [r, R - 1]</math> तब (B+1)st बकेट में अंतराल से रैंक वाले शीर्ष होंगे <math>\left[R, 2^R - 1\right].</math>
[[File:Proof_of_O(log*n)_Union_Find.jpg|center|frame|का सबूत <math>O(\log^*n)</math> संघ शोधें]]हम बाल्टियों के बारे में दो अवलोकन कर सकते हैं।

# {{anchor|max buckets}}बकेट की कुल संख्या अधिक से अधिक है {{math|log<sup>*</sup>''n''}}
#: प्रमाण: जब हम एक बाल्टी से दूसरी बाल्टी में जाते हैं, तो हम शक्ति में एक एवं दो जोड़ देते हैं, यानी अगली बाल्टी <math>\left[B, 2^B - 1\right]</math> होगा <math>\left[2^B, 2^{2^B} - 1\right]</math>
# {{anchor|max bucket size}}बाल्टी में तत्वों की अधिकतम संख्या <math>\left[B, 2^B - 1\right]</math> अधिक से अधिक है <math>\frac{2n}{2^B}</math>
#: सबूत: बाल्टी में तत्वों की अधिकतम संख्या <math>\left[B, 2^B - 1\right]</math> अधिक से अधिक है <math>\frac{n}{2^B} + \frac{n}{2^{B+1}} + \frac{n}{2^{B+2}} + \cdots + \frac{n}{2^{2^B - 1}} \leq \frac{2n}{2^B}.</math>
होने देना {{mvar|F}} प्रदर्शन किए गए कार्यों की सूची का प्रतिनिधित्व करते हैं, एवं जाने दें

<math display=block>T_1 = \sum_F\text{(link to the root)}</math>
<math display=block>T_2 = \sum_F\text{(number of links traversed where the buckets are different)}</math>
<math display=block>T_3 = \sum_F\text{(number of links traversed where the buckets are the same).}</math>
फिर की कुल लागत {{mvar|m}} पाता है <math>T = T_1 + T_2 + T_3.</math>
चूंकि प्रत्येक शोध संचालन ठीक एक ट्रैवर्सल बनाता है जो मूल की ओर जाता है, हमारे पास है {{math|1=''T''<sub>1</sub> = ''O''(''m'')}}.

इसके अतिरिक्त, ऊपर की सीमा से बाल्टियों की संख्या पर, हमारे पास है {{math|1=''T''<sub>2</sub> = ''O''(''m''log<sup>*</sup>''n'')}}.

के लिए {{mvar|T<sub>3</sub>}}, मान लीजिए कि हम एक किनारे से गुजर रहे हैं {{mvar|u}} को {{mvar|v}}, कहाँ {{mvar|u}} एवं {{mvar|v}} बकेट में रैंक है {{math|[''B'', 2<sup>''B''</sup> − 1]}} एवं {{mvar|v}} मूल नहीं है (इस ट्रैवर्सिंग के समय, अन्यथा ट्रैवर्सल का हिसाब होगा {{mvar|T<sub>1</sub>}}). हल करना {{mvar|u}} एवं अनुक्रम पर विचार करें <math>v_1, v_2, \ldots, v_k</math> कि भूमिका निभाएं {{mvar|v}} विभिन्न शोध कार्यों में। पथ संपीड़न के कारण एवं किनारे को मूल के लिए लेखांकन नहीं करने के कारण, इस अनुक्रम में केवल भिन्न-भिन्न नोड होते हैं एवं #बढ़ती रैंक लेम्मा के कारण हम जानते हैं कि इस क्रम में नोड्स की रैंक सख्ती से बढ़ रही है। बकेट में दोनों नोड्स होने से हम यह निष्कर्ष निकाल सकते हैं कि लंबाई {{mvar|k}} अनुक्रम का (कई बार नोड {{mvar|u}} एक ही बाल्टी में एक भिन्न जड़ से जुड़ा हुआ है) बाल्टियों में रैंकों की अधिकतम संख्या है {{mvar|B}}, यानी ज्यादा से ज्यादा <math>2^B - 1 - B < 2^B.</math>
इसलिए, <math>T_3 \leq \sum_{[B, 2^B - 1]} \sum_u 2^B.</math>
टिप्पणियों से #अधिकतम बाल्टियाँ एवं #अधिकतम बकेट आकार, हम यह निष्कर्ष निकाल सकते हैं <math display="inline">T_3 \leq \sum_{B} 2^B \frac{2n}{2^B} \leq 2 n \log^* n.</math>
इसलिए, <math>T = T_1 + T_2 + T_3 = O(m \log^*n).</math>


== अनुप्रयोग ==

[[File:UnionFindKruskalDemo.gif|250px|thumb|न्यूनतम विस्तृत पेड़ को शोधने के लिए क्रुस्कल के एल्गोरिदम का उपयोग करते समय संघ-शोध के लिए एक डेमो।]]असंयुक्त-उपसमुच्चय डेटा संरचनाएं एक उपसमुच्चय के विभाजन को मॉडल करती हैं, उदाहरण के लिए एक [[अप्रत्यक्ष ग्राफ]] के कनेक्टेड घटक (ग्राफ सिद्धांत) का ट्रैक रखने के लिए। इस मॉडल का उपयोग तब यह निर्धारित करने के लिए किया जा सकता है कि क्या दो कोने एक ही घटक से संबंधित हैं, या क्या उनके मध्य एक किनारा जोड़ने से एक चक्र बन जाएगा। यूनियन-फाइंड एल्गोरिथम का उपयोग [[एकीकरण (कंप्यूटर विज्ञान)]] के उच्च-प्रदर्शन कार्यान्वयन में किया जाता है।<ref name="Knight1989">{{cite journal|last1=Knight|first1=Kevin|year=1989|title=Unification: A multidisciplinary survey|journal=ACM Computing Surveys|pages=93&ndash;124|doi=10.1145/62029.62030|volume=21|s2cid=14619034|url=http://www.isi.edu/natural-language/people/unification-knight.pdf }}</ref>
इस डेटा संरचना का उपयोग [[बूस्ट ग्राफ लाइब्रेरी]] द्वारा इसकी [http://www.boost.org/libs/graph/doc/incremental_components.html इंक्रीमेंटल कनेक्टेड कंपोनेंट्स] कार्यक्षमता को लागू करने के लिए किया जाता है। ग्राफ़ के न्यूनतम विस्तृत पेड़ को शोधने के लिए क्रस्कल के एल्गोरिदम को लागू करने में यह एक महत्वपूर्ण घटक भी है।

ध्यान दें कि असंयुक्त-उपसमुच्चय वनों के रूप में नियमित कार्यान्वयन किनारों को हटाने की अनुमति नहीं देता है, यहां तक कि पथ संपीड़न या रैंक हेयुरिस्टिक के बिना भी। चूंकि, आधुनिक कार्यान्वयन मौजूद हैं जो निरंतर-समय के विलोपन की अनुमति देते हैं।<ref>{{Cite book |url=https://www.worldcat.org/oclc/262681795 |title=Automata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings |date=2005 |publisher=Springer |others=Luís. Caires, European Association for Theoretical Computer Science |isbn=978-3-540-31691-6 |location=Berlin |oclc=262681795}}</ref>{{vague citation|date=May 2023}}

शारीर एवं अग्रवाल ने डिसजॉइंट-उपसमुच्चय के सबसे खराब स्थिति वाले व्यवहार एवं डेवनपोर्ट-शिनज़ेल अनुक्रम की लंबाई के मध्य संबंध की रिपोर्ट की। डेवनपोर्ट-शिनज़ेल अनुक्रम, कम्प्यूटेशनल ज्यामिति से एक संयोजन संरचना।<ref name="Sharir1995">{{cite book|first1=M.|last1=Sharir|first2=P.|last2=Agarwal|title=डेवनपोर्ट-सिनजेल अनुक्रम और उनके ज्यामितीय अनुप्रयोग|title-link= Davenport–Schinzel Sequences and Their Geometric Applications|publisher=Cambridge University Press|year=1995}}</ref>
द होशेन-कोपेलमैन_एल्गोरिदम | होशेन-कोपेलमैन एल्गोरिथम एल्गोरिथम में यूनियन-फाइंड का उपयोग करता है।

== यह भी देखें ==

* {{annotated link|Partition refinement}}, असंयुक्त उपसमुच्चय को बनाए रखने के लिए एक भिन्न डेटा संरचना, ऐसे अपडेट के साथ जो उपसमुच्चय को एक साथ मिलाने के बजाय भिन्न कर देता है
* {{annotated link|Dynamic connectivity}}

== संदर्भ ==

{{reflist|30em}}


== बाहरी संबंध ==

* [https://www.boost.org/doc/libs/1_31_0/libs/disjoint_sets/disjoint_sets.html C++ implementation], part of the [[Boost C++ libraries]]
* [https://github.com/jgrapht/jgrapht/blob/master/jgrapht-core/src/main/java/org/jgrapht/alg/util/UnionFind.java Java implementation], part of [https://jgrapht.org/ JGraphT library]
* [https://the-algorithms.com/algorithm/union-find Javascript implementation]
* [http://code.activestate.com/recipes/215912-union-find-data-structure/ Python implementation]
* [http://www.mathblog.dk/disjoint-set-data-structure/ Visual explanation and C# code]

{{data structures}}
[[Category: खोज एल्गोरिदम]] [[Category: परिशोधित डेटा संरचनाएं]] [[Category: स्यूडोकोड के उदाहरण वाले लेख]] 



[[Category: Machine Translated Page]]
[[Category:Created On 13/05/2023]]