Skog av osammanhängande uppsättningar

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 30 november 2019; verifiering kräver 1 redigering .

Skogen av osammanhängande uppsättningar  är en trädliknande datastruktur för osammanhängande uppsättningar . (kallas ibland Disjoint Set System )

Ställ in representationer

Varje uppsättning representeras som ett rotat träd . I en osammanhängande uppsättningsskog innehåller varje nod ett uppsättningselement och pekar bara på dess överordnade nod. Roten till varje träd innehåller en representant och är föräldern till sig själv.

Operationer på skogen av osammanhängande uppsättningar utförs enligt följande:

MAKE_SET - skapar ett träd med en nod.

FIND_SET - vi flyttar längs föräldralänkarna till trädets rot.

UNION - sätter pekaren för roten av ett träd till roten av ett annat.

Heuristik för effektivitet

Förening efter rang. Idén med heuristiken är att när UNION-operationen utförs, ökar inte höjden på det resulterande trädet, om möjligt. För detta används den karakteristiska rangordningen för varje rot, vilket är den övre gränsen för nodens höjd. MAKE_SET-operationen skapar en rot med rang 0. UNION-operationen, som i det här fallet kallas union för rang, fungerar enligt följande:

Bankompression. Heuristiken under FIND_SET-operationen gör att varje nod (som påträffas när man flyttar upp till roten) pekar direkt mot roten. Vägkomprimering ändrar inte rangen av noder.

Pseudokod

Betrakta ett exempel på att implementera en skog av osammanhängande uppsättningar. I arrayen p kommer vi att lagra en länk till modernoden, och i arrayen r rankningen av vertex.

operation MAKE_SET(x) p[x] = x r[x] = 0 operation FIND_SET(x) om x ≠ p[x] då p[x] = FIND_SET(p[x]) returnera p[x] operation UNION(x, y) om r[x] > r[y] då p[y] = x annan p[x] = y om r[x] = r[y] då r[y] = r[y] + 1

Öppettider

När de tillämpas separat, leder rankunion och bankompression till en ökning av effektiviteten av operationer på en skog av osammanhängande uppsättningar. Förbundet efter rang anger själv körtiden , där  är det totala antalet operationer och  är antalet element i systemet. Vägkomprimering i sig resulterar i värsta fall körtid , där  är antalet FIND_SET-operationer. Att tillämpa båda heuristikerna ger den värsta körtiden , där  är den omvända Ackermann-funktionen . Denna uppskattning är en nedre gräns för drifttiden med osammanhängande uppsättningar, så skogen av osammanhängande uppsättningar är den optimala strukturen för osammanhängande uppsättningar.

Länkar

Litteratur