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

Disjoint-set/Union-find Forest
Type	multiway tree
Invented	1964
Invented by	Bernard A. Galler and Michael J. Fischer
Time complexity in big O notation
Algorithm Average Worst case Space O(n) O(n) Search O(α(n)) O(α(n)) Merge O(α(n)) O(α(n))

MakeSet 8 सिंगलटन बनाता है।

के कुछ संचालन के बाद Union, कुछ उपसमुच्चय एक साथ समूहीकृत किए जाते हैं।

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

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

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

इतिहास

1964 में बर्नार्ड ए. गैलर एवं माइकल जे. फिशर द्वारा संधि भंग-उपसमुच्चय वनों का प्रथम बार वर्णन किया गया था। 1973 में, उनकी समय जटिलता को सीमित कर दिया गया था $O(\log ^{*}(n))$, का पुनरावृत्त लघुगणक $n$, जॉन हॉपक्रॉफ्ट एवं जेफरी उल्मैन द्वारा 1975 में, रॉबर्ट टार्जन प्रमाणित करने वाले प्रथम व्यक्ति थे। $O(m\alpha (n))$ एल्गोरिथम की समय जटिलता पर ऊपरी सीमा, एवं, 1979 में, दिखाया कि यह प्रतिबंधित विषय के लिए निचली सीमा थी। 1989 में, माइकल फ्रेडमैन एवं माइकल सक्स (गणितज्ञ) $\Omega (\alpha (n))$ ने इसे दिखाया। (परिशोधित) शब्दों को किसी भी असम्बद्ध-उपसमुच्चय डेटा संरचना प्रति संचालन द्वारा एक्सेस किया जाना चाहिए, जिससे डेटा संरचना की इष्टतमता प्रमाणित होती है।

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

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

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

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

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

संचालन

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

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

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

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 असंबद्ध उपसमुच्चय वन के साथ n नोड्स की आवश्यकता O(n) है।

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

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

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

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

फ़ंक्शन Find(x) है
    अगर x.parent ≠ x तो
        x.parent := Find(x.parent)
        रिटर्न x.parent
    अन्य
        रिटर्न एक्स
    अगर अंत
अंत फंक्शन

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

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

    जबकि x.parent ≠ root करते हैं
        अभिभावक := x.जनक
        x.parent := जड़
        एक्स := पैरेंट
    जबकि समाप्त करें

    रिटर्न मूल
अंत फंक्शन

रॉबर्ट ई. टारजन एवं जॉन वैन लीउवेन ने भी वन-पास विकसित किया Find एल्गोरिदम जो सबसे खराब स्थिति वाली जटिलता को बनाए रखते हैं किन्तु व्यवहार में अधिक कुशल होते हैं। इन्हें पाथ स्प्लिटिंग एवं पाथ हॉलिंग कहा जाता है। ये दोनों क्वेरी नोड एवं मूल के मध्य के पथ पर नोड्स के पैरेंट पॉइंटर्स को अपडेट करते हैं। पथ विभाजन प्रत्येक पैरेंट पॉइंटर को उस पथ पर एक पॉइंटर द्वारा नोड के दादा-दादी के लिए बदल देता है:

फ़ंक्शन 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
    जबकि समाप्त करें
    रिटर्न एक्स
अंत फंक्शन

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

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

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

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

आकार से संघ

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

फंक्शन Union(x, y) है
     // नोड्स को जड़ों से बदलें 
    x := Find(x)
    वाई := फाइंड(वाई)

    अगर x = y तब
        वापसी  // x एवं y पहले से ही एक ही उपसमुच्चय में हैं 
    अगर अंत

    // यदि आवश्यक हो, तो यह सुनिश्चित करने के लिए चर स्वैप करें 
    // x के कम से कम उतने वंशज हैं जितने y
    अगर x.size <y.size तो
        (x, y) := (y, x)
    अगर अंत

     // एक्स को नया मूल बनाएं 
    य. जनक := x
     // x का आकार अपडेट करें 
    एक्स.साइज := एक्स.साइज + वाई.साइज
अंत फंक्शन

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

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

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

फंक्शन 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
    अगर अंत
अंत फंक्शन

यह दिखाया जा सकता है कि प्रत्येक नोड में रैंक है $\lfloor \log n\rfloor$ या कम। नतीजतन प्रत्येक रैंक में संग्रहीत किया जा सकता है O(log log n) बिट्स एवं सभी रैंकों को स्टोर किया जा सकता है O(n log log n) बिट्स। यह रैंकों को वन के आकार का एक विषम रूप से नगण्य भाग बनाता है।

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

समय जटिलता

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

यदि कोई कार्यान्वयन अकेले पथ संपीड़न का उपयोग करता है, तो एक क्रम n MakeSet संचालन, उसके बाद तक n − 1 Union संचालन एवं f Find संचालन, का सबसे खराब समय चल रहा है $\Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))$. रैंक द्वारा संघ का उपयोग करना, किन्तु माता-पिता पॉइंटर्स को अपडेट किए बिना Find, का चलने का समय देता है $\Theta (m\log n)$ के लिए m किसी भी प्रकार का संचालन, तक n जिनमें से हैं MakeSet संचालन।

आकार या रैंक द्वारा संघ के साथ पथ संपीड़न, विभाजन, या आधा करने का संयोजन, चलने के समय को कम करता है m किसी भी प्रकार का संचालन, तक n जिनमें से हैं MakeSet संचालन, करने के लिए $\Theta (m\alpha (n))$. यह प्रत्येक संचालन का परिशोधन विश्लेषण करता है $\Theta (\alpha (n))$. यह असम्बद्ध रूप से इष्टतम है, जिसका अर्थ है कि प्रत्येक असम्बद्ध उपसमुच्चय डेटा संरचना का उपयोग करना चाहिए $\Omega (\alpha (n))$ प्रति संचालन परिशोधित समय। यहाँ, फंक्शन $\alpha (n)$ एकरमैन फ़ंक्शन # उलटा है। व्युत्क्रम एकरमैन फ़ंक्शन असाधारण रूप से धीरे-धीरे बढ़ता है, इसलिए यह कारक है 4 या किसी के लिए कम n जो वास्तव में भौतिक ब्रह्मांड में लिखा जा सकता है। यह असंबद्ध-उपसमुच्चय संचालन को व्यावहारिक रूप से परिशोधित स्थिर समय बनाता है।

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

एक असम्बद्ध-उपसमुच्चय वन के प्रदर्शन का सटीक विश्लेषण कुछ जटिल है। चूंकि, एक बहुत सरल विश्लेषण है जो यह साबित करता है कि किसी के लिए परिशोधित समय m Find या Union एक असम्बद्ध-उपसमुच्चय वन युक्त पर संचालन n वस्तुएं हैं O(mlog^* n), कहाँ log^* पुनरावृत्त लघुगणक को दर्शाता है।

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

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 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.

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

Proof

Initially when each node is the root of its own tree, it's trivially true. Assume that a node u with rank r has at least 2^r nodes. Then when two trees with rank r are merged using the operation Union by Rank, a tree with rank r + 1 results, the root of which has at least $2^{r}+2^{r}=2^{r+1}$ nodes.

लेम्मा 3: रैंक के नोड्स की अधिकतम संख्या r ज्यादा से ज्यादा है ${\frac {n}{2^{r}}}.$

Proof

From lemma 2, we know that a node u which is root of a subtree with rank r has at least $2^{r}$ nodes. We will get the maximum number of nodes of rank r when each node with rank r is the root of a tree that has exactly $2^{r}$ nodes. In this case, the number of nodes of rank r is ${\frac {n}{2^{r}}}.$

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

हम कुछ बकेट बनाते हैं एवं उनके रैंक के अनुसार बाल्टियों में वर्टिकल डालते हैं। यानी, रैंक 0 वाले कोने शून्य बकेट में जाते हैं, रैंक 1 वाले वर्टिकल पहली बकेट में जाते हैं, रैंक 2 एवं 3 वाले वर्टिकल दूसरी बकेट में जाते हैं। अगर B-थ बकेट में अंतराल से रैंक वाले वर्टिकल होते हैं $\left[r,2^{r}-1\right]=[r,R-1]$ तब (B+1)st बकेट में अंतराल से रैंक वाले शीर्ष होंगे $\left[R,2^{R}-1\right].$

का सबूत $O(\log ^{*}n)$ संघ शोधें

हम बाल्टियों के बारे में दो अवलोकन कर सकते हैं।

1. बकेट की कुल संख्या अधिक से अधिक है log^*n

   प्रमाण: जब हम एक बाल्टी से दूसरी बाल्टी में जाते हैं, तो हम शक्ति में एक एवं दो जोड़ देते हैं, यानी अगली बाल्टी $\left[B,2^{B}-1\right]$ होगा $\left[2^{B},2^{2^{B}}-1\right]$

2. बाल्टी में तत्वों की अधिकतम संख्या $\left[B,2^{B}-1\right]$ अधिक से अधिक है ${\frac {2n}{2^{B}}}$

   सबूत: बाल्टी में तत्वों की अधिकतम संख्या $\left[B,2^{B}-1\right]$ अधिक से अधिक है ${\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}}}.$

होने देना F प्रदर्शन किए गए कार्यों की सूची का प्रतिनिधित्व करते हैं, एवं जाने दें

$$T_{1}=\sum _{F}{\text{(link to the root)}}$$

$$T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}$$

$$T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}$$

फिर की कुल लागत m पाता है $T=T_{1}+T_{2}+T_{3}.$ चूंकि प्रत्येक शोध संचालन ठीक एक ट्रैवर्सल बनाता है जो मूल की ओर जाता है, हमारे पास है T₁ = O(m).

इसके अतिरिक्त, ऊपर की सीमा से बाल्टियों की संख्या पर, हमारे पास है T₂ = O(mlog^*n).

के लिए T₃, मान लीजिए कि हम एक किनारे से गुजर रहे हैं u को v, कहाँ u एवं v बकेट में रैंक है [B, 2^B − 1] एवं v मूल नहीं है (इस ट्रैवर्सिंग के समय, अन्यथा ट्रैवर्सल का हिसाब होगा T₁). हल करना u एवं अनुक्रम पर विचार करें $v_{1},v_{2},\ldots ,v_{k}$ कि भूमिका निभाएं v विभिन्न शोध कार्यों में। पथ संपीड़न के कारण एवं किनारे को मूल के लिए लेखांकन नहीं करने के कारण, इस अनुक्रम में केवल भिन्न-भिन्न नोड होते हैं एवं #बढ़ती रैंक लेम्मा के कारण हम जानते हैं कि इस क्रम में नोड्स की रैंक सख्ती से बढ़ रही है। बकेट में दोनों नोड्स होने से हम यह निष्कर्ष निकाल सकते हैं कि लंबाई k अनुक्रम का (कई बार नोड u एक ही बाल्टी में एक भिन्न जड़ से जुड़ा हुआ है) बाल्टियों में रैंकों की अधिकतम संख्या है B, यानी ज्यादा से ज्यादा $2^{B}-1-B<2^{B}.$ इसलिए, $T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.$ टिप्पणियों से #अधिकतम बाल्टियाँ एवं #अधिकतम बकेट आकार, हम यह निष्कर्ष निकाल सकते हैं ${\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$ इसलिए, $T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).$

अनुप्रयोग

न्यूनतम विस्तृत पेड़ को शोधने के लिए क्रुस्कल के एल्गोरिदम का उपयोग करते समय संघ-शोध के लिए एक डेमो।

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

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

ध्यान दें कि असंयुक्त-उपसमुच्चय वनों के रूप में नियमित कार्यान्वयन किनारों को हटाने की अनुमति नहीं देता है, यहां तक ​​कि पथ संपीड़न या रैंक हेयुरिस्टिक के बिना भी। चूंकि, आधुनिक कार्यान्वयन मौजूद हैं जो निरंतर-समय के विलोपन की अनुमति देते हैं।Template:Vague citation

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

यह भी देखें

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

बाहरी संबंध

• C++ implementation, part of the Boost C++ libraries
• Java implementation, part of JGraphT library
• Javascript implementation
• Python implementation
• Visual explanation and C# code