Erillisten joukkojen metsä

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 30.11.2019 tarkistetusta versiosta . vahvistus vaatii 1 muokkauksen .

Disjunktijoukkojen metsä on puumainen tietorakenne disjunktijoukkoja varten . (kutsutaan joskus Disjoint Set Systemiksi )

Aseta esitykset

Jokainen joukko esitetään juurtuneena puuna . Epäliittyneessä joukkometsässä jokainen solmu sisältää yhden joukkoelementin ja osoittaa vain sen pääsolmuun. Jokaisen puun juuri sisältää edustajan ja on itsensä vanhempi.

Toiminnot disjunktijoukkojen metsässä suoritetaan seuraavasti:

MAKE_SET - luo puun, jossa on yksi solmu.

FIND_SET - siirrymme ylälinkkejä pitkin puun juureen.

UNIONI - asettaa yhden puun juuren osoittimen toisen puun juureen.

Heuristiikka tehokkuutta varten

Yhdistys arvon mukaan. Heuristiikan ideana on, että kun UNION-operaatio suoritetaan, tuloksena olevan puun korkeus ei mahdollisuuksien mukaan kasva. Tätä varten käytetään kunkin juuren ominaisarvoa , joka on solmun korkeuden yläraja. MAKE_SET-toiminto luo juuren, jonka arvo on 0. UNION-operaatio, jota tässä tapauksessa kutsutaan union by rank, toimii seuraavasti:

Jos juurien arvot ovat erilaiset, alempana oleva juuri osoittaa korkeamman tason juurelle. Juuriarvot eivät muutu.
Jos juurien arvot ovat yhtä suuret, jompikumpi juurista osoittaa toiseen. Toisen juuren osoittaman juuren arvoa korotetaan 1:llä.

Polun pakkaus. FIND_SET-operaation aikana tapahtuva heuristiikka saa jokaisen solmun (joka kohdataan siirtyessään juureen) osoittamaan suoraan juureen. Polun pakkaus ei muuta solmujen rivejä.

Pseudokoodi

Harkitse esimerkkiä epäyhtenäisten joukkojen metsän toteuttamisesta. Taulukon p tallennamme linkin pääsolmuun ja taulukkoon r kärjen arvon.

toimenpide MAKE_SET(x) p[x] = x r[x] = 0 operaatio FIND_SET(x) jos x ≠ p[x] niin p[x] = ETSI_SET(p[x]) paluu p[x] operaatio UNION(x, y) jos r[x] > r[y] sitten p[y] = x muu p[x] = y jos r[x] = r[y] niin r[y] = r[y] + 1

Aukioloajat

Erikseen käytettynä järjestysliitto ja polun pakkaus lisäävät toimintojen tehokkuutta hajanaisten joukkojen metsässä. Itse liitto arvon mukaan antaa ajoajan , jossa on operaatioiden kokonaismäärä ja järjestelmän elementtien lukumäärä. Itse polun pakkaus johtaa pahimpaan mahdolliseen ajoaikaan , jossa on FIND_SET-toimintojen määrä. Molempien heuristioiden soveltaminen antaa pahimman tapauksen ajoajan , missä on käänteinen Ackermann-funktio . Tämä estimaatti on toiminta-ajan alaraja disjunktijoukkojen kanssa, joten disjunktijoukkojen metsä on optimaalinen rakenne disjunktijoukkoille. $O(m~\lg{n})$ $m$ $n$ $O(n + f~\log_{2 + f/n}{n})$ $f$ $O(m\\alfa(n, m))$ $\alpha(n, m)$

Linkit

Tietorakenteen visualisointityökalu

Kirjallisuus

Thomas Kormen ym. Algoritmit: rakentaminen ja analyysi = ALGORITMEIN JOHDANTO. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .