A diszjunkt szettek rendszere
Általános információk
A disszociált készletek - esetenként egy unió-keresés - egy olyan speciális adatszerkezet, amely információkat tartalmaz egy készletkészletről, amely lehetővé teszi a készletek kombinálását és a kérdés megválaszolását, hogy ezek az elemek ugyanabba a csoportba tartoznak-e.
Kezdetben N különböző elemeket vesznek figyelembe, melyek mindegyike független. Ezután bármelyik két kombináció kombinálható, és mindkét készlet eleme az eredményhalmaz elemévé válik. Nyilvánvaló, hogy az (N-1) fúzióból kiindulási állapotból (N egyelemes készletek) az állapotot megkapjuk, amelyben minden elem egy csoportba kerül. Amint az a folytatásban látható, elegendő egyszerűen kiegészíteni egy diszjunktúra-készlet végrehajtását az új egyelem-készlet hozzáadásával (vagyis egy (N + 1) -es elem hozzáadása, amely egy független készletet alkot).
Bármely készlet egyedileg azonosítható az egyik elemének felhasználásával: a két készlet nem tartalmazhat ugyanazt az elemet definíció szerint (ezt a tényt az adatszerkezet nevében a "disjoint" szó tükrözi). Ezt az elemet a készlet képviselőjének (angol reprezentatív elem) nevezik.
A továbbiakban feltételezzük, hogy a készletek elemei egész számok. A diszjunktáramköröknek a következő műveletekkel kell rendelkezniük:
- a halmaz azon képviselőjének meghatározása, amelyhez az x elem tartozik. Nyilvánvaló, hogy ha az x és y elemek ugyanabba a csoportba tartoznak, akkor meg kell adni a find (x) == find (y) állapotot. Ellenkező esetben meg kell találni (x)! = Find (y);