The PR introduces the following new binary method:
DisjointSet#union(x, y)
Determines the set representatives/roots of the given x and y elements, and if they are distinct, the sets/trees that x and y belong to are merged by updating the parent pointer of the set representative/root with the lower rank to point to the set representative/root with the higher rank. If instead, the representatives/roots have equal ranks, the set representative/root of element x is chosen by default as the parent of the y element representative/root, while its rank is also incremented. Returns the disjoint-set forest itself.
The method uses the union by rank heuristic which enable us to prevent the height growth of a disjoint-set/tree to O(n) levels, by always attaching the shorter tree to the root of the taller tree, thus the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node.
Also, the corresponding TypeScript ambient declarations are included in the PR.
Description
The PR introduces the following new binary method:
DisjointSet#union(x, y)Determines the set representatives/roots of the given
xandyelements, and if they are distinct, the sets/trees thatxandybelong to are merged by updating the parent pointer of the set representative/root with the lower rank to point to the set representative/root with the higher rank. If instead, the representatives/roots have equal ranks, the set representative/root of elementxis chosen by default as the parent of theyelement representative/root, while its rank is also incremented. Returns the disjoint-set forest itself.The method uses the union by rank heuristic which enable us to prevent the height growth of a disjoint-set/tree to
O(n)levels, by always attaching the shorter tree to the root of the taller tree, thus the resulting tree is no taller than the originals unless they were of equal height, in which case the resulting tree is taller by one node.Also, the corresponding TypeScript ambient declarations are included in the PR.