Adatszerkezet a diszjunkt szettekhez
A Cyclopedia-tól
A diszjunktáramkörök adatszerkezete támogatja a nem-intersecting dinamikus készletek [math] S = \ [/ math] értékét. Minden készletet egy képviselő azonosít. amely a készlet egy bizonyos eleme. Egyes alkalmazásokban nem számít, hogy a készlet melyik elemét használják képviselőként; a legfontosabb az, hogy amikor a készlet képviselőjét kétszer megkérdezzük, anélkül, hogy a kérések között a beállításokat módosítanánk, ugyanaz az elem visszatérne.
A diszjunktáblák adatstruktúrája a következő műveletek támogatását igényli:
A MAKE_SET (x) létrehoz egy új elemet, amely egy elemből áll (ami ennek megfelelően válik a reprezentatívjává) x. Mivel a készletek diszjunktívak, az x nem tartozik más csoporthoz.
Az UNION (x, y) olyan dinamikus készleteket ötvözi, amelyek x-et és y-t tartalmaznak (amelyeket [math] S_x [/ math] és [math] S_y [/ math] jelölnek egy új készletbe. Feltételezzük, hogy a művelet előtt a jelzett készletek nem metszenek egymással. A kapott készlet képviselője tetszőleges elem [math] S_x \ cup S_y [/ math]. Mivel szükséges, hogy a készletek nem metszenek, az UNION műveletnek el kell pusztítania a [math] S_x [/ math] és [math] S_y [/ math] készleteket.
FIND_SET (x) egy mutatót ad vissza annak a készletnek a képviselőjéhez, amelyben az x elem van.