data-structures

DisjointSet

Class

class DisjointSet {
  forest: Set<Tree>;  map: Map<string, Tree>;  makeSet(x: string): void;  findSet(x: string | Tree): Tree;  union(x: string | Tree, y: string | Tree): Tree;  merge(x: Tree, y: Tree): Tree;}

Members

forest

Set<Tree>

map

Map<string, Tree>

makeSet

void

Initializes x as a lone node.

@complexityΘ(1) in the worst case

@paramxstring

@returnsvoid

findSet

Tree

@paramxstring | Tree

@returnsTree

union

Tree

Climbs to the roots of the trees containing x and y
and merges parents sets rep[y] , rep[x].

@complexityΘ(height)

@paramxstring | Tree

@paramystring | Tree

@returnsTree

merge

Tree

Merging the tree with the smaller height into the tree with the bigger height

the height of a tree remains O(lg n).

@paramxTree

@paramyTree

@returnsTree