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

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

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

end function

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

function Find(x) is
    root := x
    while root.parent ≠ root do
        root := root.parent
    end while

    while x.parent ≠ root do
        parent := x.parent
        x.parent := root
        x := parent
    end while

    return root

end function

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

function Find(x) is
    while x.parent ≠ x do
        (x, x.parent) := (x.parent, x.parent.parent)
    end while
    return x

end function

पथ जोड़ समान रूप से कार्य करता है, किन्तु केवल प्रत्येक दूसरे जनक सूचक को परिवर्तित करता है।

function Find(x) is
    while x.parent ≠ x do
        x.parent := x.parent.parent
        x := x.parent
    end while
    return x

end function

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

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

कौन सा ग्रंथि माता-पिता बनने का विकल्प वृक्ष पर भविष्य के संचालन की जटिलता के परिणाम हैं। यदि इसे असावधानी से किया जाए तो वृक्ष अत्यधिक ऊंचे हो सकते हैं। उदाप्रत्येकण के लिए, मान लीजिए 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 विलय किए जाते हैं, तो अधिक असंतोष वाला ग्रंथि जनक बन जाता है। यदि दो ग्रंथियों के वंशजों की संख्या समान है, तो कोई भी माता-पिता बन सकता है। दोनों ही स्थितियों में, नए जनक ग्रंथि का आकार उसके वंशजों की नई कुल संख्या पर उपसमुच्चय होता है।

function Union(x, y) is
    // Replace nodes by roots
    x := Find(x)
    y := Find(y)

    if x = y then
        return  // x and y are already in the same set
    end if

    // If necessary, swap variables to ensure that
    // x has at least as many descendants as y
    if x.size < y.size then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // Update the size of x
    x.size := x.size + y.size

end function

आकार को एकत्र करने के लिए आवश्यक बिट्स की संख्या स्पष्ट रूप से एकत्र करने के लिए आवश्यक बिट्स की संख्या 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