विसंधित-सेट डेटा संरचना: Difference between revisions

Disjoint-set/Union-find Forest
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
Algorithm	Average
Space	O(n)
Search	O(α(n))
Merge	O(α(n))

Revision as of 18:50, 18 May 2023

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

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

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

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

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

इतिहास

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

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

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

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

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

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

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 संचालन, इसलिए रैंकों को संग्रहित करने से ऊंचाई को सही रखने के अतिरिक्त प्रयत्नों से बचा जाता है। स्यूडोकोड में, रैंक द्वारा संघ है।

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, rename variables to ensure that
    // x has rank at least as large as that of y
    if x.rank < y.rank then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // If necessary, increment the rank of x
    if x.rank = y.rank then
        x.rank := x.rank + 1
    end if

end function

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

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

समय जटिलता

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

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

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

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

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

Proof

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

{{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)

संघ शोधें

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

बकेट की कुल संख्या अधिक से अधिक है $log * n$
प्रमाण: जब हम एक बाल्टी से दूसरी बाल्टी में जाते हैं, तो हम शक्ति में एक एवं दो जोड़ देते हैं, यानी अगली बाल्टी $\left[B,2^{B}-1\right]$ होगा $\left[2^{B},2^{2^{B}}-1\right]$
बाल्टी में तत्वों की अधिकतम संख्या $\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 1 = O (m)

.

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

के लिए $T 3$ , मान लीजिए कि हम एक किनारे से गुजर रहे हैं $u$ को $v$ , कहाँ $u$ एवं $v$ बकेट में रैंक है $[B, 2 B - 1]$ एवं $v$ मूल नहीं है (इस ट्रैवर्सिंग के समय, अन्यथा ट्रैवर्सल का हिसाब होगा $T 1$ ). हल करना $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).$

अनुप्रयोग

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

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

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

ध्यान दें कि असंयुक्त-उपसमुच्चय वनों के रूप में नियमित कार्यान्वयन किनारों को विस्थापित करने की अनुमति नहीं देता है, यहां तक कि पथ संपीड़न या रैंक हेयुरिस्टिक के बिना भी चूंकि, आधुनिक कार्यान्वयन उपस्थित हैं जो निरंतर-समय के विलोपन की अनुमति देते हैं।^[17]

शारीर एवं अग्रवाल ने संबंध -उपसमुच्चय के सबसे निकृष्ट स्थिति वाले व्यवहार एवं डेवनपोर्ट-शिनज़ेल अनुक्रम की लंबाई के मध्य संबंध की रिपोर्ट की डेवनपोर्ट-शिनज़ेल अनुक्रम, मिश्रित ज्यामिति से संयोजन संरचना^[18] एल्गोरिथम में यूनियन-फाइंड का उपयोग करता है।

यह भी देखें

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

संदर्भ

↑ ^1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.
↑ Galler, Bernard A.; Fischer, Michael J. (May 1964). "एक बेहतर तुल्यता एल्गोरिथ्म". Communications of the ACM. 7 (5): 301–303. doi:10.1145/364099.364331. S2CID 9034016.. The paper originating disjoint-set forests.
↑ Hopcroft, J. E.; Ullman, J. D. (1973). "मर्जिंग एल्गोरिदम सेट करें". SIAM Journal on Computing. 2 (4): 294–303. doi:10.1137/0202024.
↑ ^4.0 ^4.1 ^4.2 Tarjan, Robert E.; van Leeuwen, Jan (1984). "सेट यूनियन एल्गोरिथम का वर्स्ट-केस विश्लेषण". Journal of the ACM. 31 (2): 245–281. doi:10.1145/62.2160. S2CID 5363073.
↑ ^5.0 ^5.1 Tarjan, Robert Endre (1979). "एल्गोरिद्म का एक वर्ग जिसे असंयुक्त सेट बनाए रखने के लिए गैर-रैखिक समय की आवश्यकता होती है". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.
↑ ^6.0 ^6.1 Fredman, M.; Saks, M. (May 1989). "गतिशील डेटा संरचनाओं की सेल जांच जटिलता". Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345–354. doi:10.1145/73007.73040. ISBN 0897913078. S2CID 13470414. Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.
↑ Galil, Z.; Italiano, G. (1991). "असंयुक्त सेट संघ समस्याओं के लिए डेटा संरचनाएं और एल्गोरिदम।". ACM Computing Surveys. 23 (3): 319–344. doi:10.1145/116873.116878. S2CID 207160759.
↑ Anderson, Richard J.; Woll, Heather (1994). संघ-खोज समस्या के लिए प्रतीक्षा-मुक्त समानांतर एल्गोरिदम. 23rd ACM Symposium on Theory of Computing. pp. 370–380.
↑ Conchon, Sylvain; Filliâtre, Jean-Christophe (October 2007). "A Persistent Union-Find Data Structure". एमएल पर एसीएम सिगप्लान वर्कशॉप. Freiburg, Germany.
↑ 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
↑ ^11.0 ^11.1 ^11.2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "Chapter 21: Data structures for Disjoint Sets". एल्गोरिदम का परिचय (Third ed.). MIT Press. pp. 571–572. ISBN 978-0-262-03384-8.
↑ Raimund Seidel, Micha Sharir. "Top-down analysis of path compression", SIAM J. Comput. 34(3):515–525, 2005
↑ Tarjan, Robert Endre (1975). "एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिथम की दक्षता". Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.
↑ Hopcroft, J. E.; Ullman, J. D. (1973). "मर्जिंग एल्गोरिदम सेट करें". SIAM Journal on Computing. 2 (4): 294–303. doi:10.1137/0202024.
↑ Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.
↑ Knight, Kevin (1989). "Unification: A multidisciplinary survey" (PDF). ACM Computing Surveys. 21: 93–124. doi:10.1145/62029.62030. S2CID 14619034.
↑ Automata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings. Luís. Caires, European Association for Theoretical Computer Science. Berlin: Springer. 2005. ISBN 978-3-540-31691-6. OCLC 262681795.{{cite book}}: CS1 maint: others (link)
↑ Sharir, M.; Agarwal, P. (1995). डेवनपोर्ट-सिनजेल अनुक्रम और उनके ज्यामितीय अनुप्रयोग. Cambridge University Press.

बाप्रत्येकी संबंध

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

[tarjan1975-1] 1.0 ^1.1 ^1.2 ^1.3 ^1.4 ^1.5 Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.

[Galler1964-2] Galler, Bernard A.; Fischer, Michael J. (May 1964). "एक बेहतर तुल्यता एल्गोरिथ्म". Communications of the ACM. 7 (5): 301–303. doi:10.1145/364099.364331. S2CID 9034016.. The paper originating disjoint-set forests.

[Hopcroft1973-3] Hopcroft, J. E.; Ullman, J. D. (1973). "मर्जिंग एल्गोरिदम सेट करें". SIAM Journal on Computing. 2 (4): 294–303. doi:10.1137/0202024.

[Tarjan1984-4] 4.0 ^4.1 ^4.2 Tarjan, Robert E.; van Leeuwen, Jan (1984). "सेट यूनियन एल्गोरिथम का वर्स्ट-केस विश्लेषण". Journal of the ACM. 31 (2): 245–281. doi:10.1145/62.2160. S2CID 5363073.

[Tarjan1979-5] 5.0 ^5.1 Tarjan, Robert Endre (1979). "एल्गोरिद्म का एक वर्ग जिसे असंयुक्त सेट बनाए रखने के लिए गैर-रैखिक समय की आवश्यकता होती है". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.

[Fredman1989-6] 6.0 ^6.1 Fredman, M.; Saks, M. (May 1989). "गतिशील डेटा संरचनाओं की सेल जांच जटिलता". Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing: 345–354. doi:10.1145/73007.73040. ISBN 0897913078. S2CID 13470414. Theorem 5: Any CPROBE(log n) implementation of the set union problem requires Ω(m α(m, n)) time to execute m Find's and n−1 Union's, beginning with n singleton sets.

[Galil1991-7] Galil, Z.; Italiano, G. (1991). "असंयुक्त सेट संघ समस्याओं के लिए डेटा संरचनाएं और एल्गोरिदम।". ACM Computing Surveys. 23 (3): 319–344. doi:10.1145/116873.116878. S2CID 207160759.

[Anderson1994-8] Anderson, Richard J.; Woll, Heather (1994). संघ-खोज समस्या के लिए प्रतीक्षा-मुक्त समानांतर एल्गोरिदम. 23rd ACM Symposium on Theory of Computing. pp. 370–380.

[Conchon2007-9] Conchon, Sylvain; Filliâtre, Jean-Christophe (October 2007). "A Persistent Union-Find Data Structure". एमएल पर एसीएम सिगप्लान वर्कशॉप. Freiburg, Germany.

[10] 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

[Cormen2009-11] 11.0 ^11.1 ^11.2 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009). "Chapter 21: Data structures for Disjoint Sets". एल्गोरिदम का परिचय (Third ed.). MIT Press. pp. 571–572. ISBN 978-0-262-03384-8.

[12] Raimund Seidel, Micha Sharir. "Top-down analysis of path compression", SIAM J. Comput. 34(3):515–525, 2005

[13] Tarjan, Robert Endre (1975). "एक अच्छे लेकिन रैखिक सेट यूनियन एल्गोरिथम की दक्षता". Journal of the ACM. 22 (2): 215–225. doi:10.1145/321879.321884. hdl:1813/5942. S2CID 11105749.

[14] Hopcroft, J. E.; Ullman, J. D. (1973). "मर्जिंग एल्गोरिदम सेट करें". SIAM Journal on Computing. 2 (4): 294–303. doi:10.1137/0202024.

[15] Robert E. Tarjan and Jan van Leeuwen. Worst-case analysis of set union algorithms. Journal of the ACM, 31(2):245–281, 1984.

[Knight1989-16] Knight, Kevin (1989). "Unification: A multidisciplinary survey" (PDF). ACM Computing Surveys. 21: 93–124. doi:10.1145/62029.62030. S2CID 14619034.

[17] Automata, languages and programming : 32nd international colloquium, ICALP 2005, Lisbon, Portugal, July 11-15, 2005 ; proceedings. Luís. Caires, European Association for Theoretical Computer Science. Berlin: Springer. 2005. ISBN 978-3-540-31691-6. OCLC 262681795.{{cite book}}: CS1 maint: others (link)

[Sharir1995-18] Sharir, M.; Agarwal, P. (1995). डेवनपोर्ट-सिनजेल अनुक्रम और उनके ज्यामितीय अनुप्रयोग. Cambridge University Press.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

@@ Line 187: / Line 187: @@
 प्रमेयिका 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.}}
+{{math proof| प्रमाण करते हैं कि डेटा समुच्चय पर फाइंड और यूनियन संचालन प्रारम्भ होते हैं, यह तथ्य समय के साथ सही रहता है। प्रारंभ में जब प्रत्येक नोड स्वयं के पेड़ की जड़ है, तो यह तुच्छ रूप से सत्य है। एकमात्र मामला जब एक नोड का रैंक बदला जा सकता है, जब [[डिस्जॉइंट-सेट डेटा स्ट्रक्चर#डिसजॉइंट-सेट फॉरेस्ट|यूनियन बाय रैंक]] ऑपरेशन लागू होता है। इस मामले में, छोटे रैंक वाले पेड़ को बड़े रैंक वाले पेड़ से जोड़ा जाएगा, बजाय इसके विपरीत। और खोज ऑपरेशन के दौरान, पथ के साथ देखे गए सभी नोड रूट से जुड़े होंगे, जिसकी रैंक उसके बच्चों से बड़ी है, इसलिए यह ऑपरेशन इस तथ्य को भी नहीं बदलेगा।}}
 <nowiki>{{anchor|min subtree size lemma}लेम्मा 2: एक ग्रंथि </nowiki>{{mvar|u}} जो रैंक के साथ सबवृक्ष का मूल है {{mvar|r}} अर्घ्य से अर्घ्य है <math>2^r</math> ग्रंथि्स।

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

विसंधित-सेट डेटा संरचना: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:50, 18 May 2023

Contents

इतिहास

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

संचालन

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

आकार से संघ

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

समय जटिलता

अनुप्रयोग

यह भी देखें

संदर्भ

बाप्रत्येकी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

विसंधित-सेट डेटा संरचना: Difference between revisions

Revision as of 18:50, 18 May 2023

इतिहास

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

संचालन

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

आकार से संघ

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

समय जटिलता

अनुप्रयोग

यह भी देखें

संदर्भ

बाप्रत्येकी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories