Mfset
L'MFSet (Merge-Find Set), altrimenti conosciuto come struttura dati union-find, è una struttura dati derivante dal concetto di partizione, per cui dato un insieme finito di elementi a volte risulta utile partizionarli in insiemi disgiunti. L'algoritmo di Merge-Find è quindi utile per le due operazioni possibili su questa struttura dati:
Ricerca
: determina in quale insieme si trova un particolare elemento, o se due elementi appartengono allo stesso insiemeUnione
: combina o fonde due insiemi in un unico insieme
L'altra operazione su MFSet è Crea
, tramite la quale è possibile dato un insieme crearne la partizione formata solo da singoletti. Con l'utilizzo di questi tre operatori è possibile risolvere molti problemi pratici.
Operazioni
Sintassi
- CREAMFSET (INSIEME) MFSet
- TROVA (ELEMENTO, MFSET) componente
- FONDI (ELEMENTO, ELEMENTO, MFSET) MFSet
Semantica
- CREAMFSET()=
è quindi una famiglia di = || componenti ,..., ciascuno dei quali contiene un solo elemento di tale che = .
- TROVA(
se appartiene ad una componente di allora è l'identificatore della componente cui appartiene.
- FONDI(
se TROVA( è diverso da quindi ed appartengono a componenti distinte di allora è formato da tutte le componenti di che non contengono o , e da una nuova componente data dall'unione delle due componenti contenenti ed .
V · D · M | |
---|---|
Tipi | Collezione · Container |
Astratte | Array associativo (Multimap) · Lista · Pila · Coda (Deque) · Coda di priorità · Set (Multiset · Mfset) |
Array | Bit array · Buffer circolare · Array dinamico · Hash table · Array sparso |
Collegate | Lista di associazioni · Lista concatenata · Skip list · Unrolled linked list · Lista concatenata tramite XOR |
Alberi | B-albero · Albero binario di ricerca (Albero AA · Albero AVL · RB-Albero · Albero binario di ricerca bilanciato · Albero splay) · Heap (Heap binario · Heap binomiale · Heap di Fibonacci) · Albero di Merkle · Albero SPQR · Albero PQ · Albero indicizzato binario |
Grafi | Diagramma binario di decisione · Digrafo aciclico · Automa a stati finiti deterministico aciclico |
Alberi di partizionamento dei dati spaziali | Albero quadramentale · M-tree · R-tree (R* tree · R+ tree) · X-tree |
Lista di strutture dati |