Disjoint-set data structure

• The disjoint-set data structure is also commonly known as union-find or a merge-find set
• “disjoint-set forest”:
  • represented as a set of N elements where:
    • each element stores an id, a parent pointer, and optional size/rank values
    • the parent pointers of the elements are arranged to form one or more trees (each tree is a “set”)
    • if an element’s parent pointer is null or self-referencing, that element is the root element of a tree/set and represents the entire set
    • single, non-connected elements are considered sets
• union-find data structure:
  • a multiway tree structure composed of elements partitioned into independent subsets, which can be thought of as connected components
  • provides a “MakeSet” operation:
    • initializes a new set by creating a new element with id, rank of 0, and a self-referencing parent pointer (denotes a root element)

      function MakeSet(x)
        if x doesn't exist yet,
          add x to the disjoint-set
          x.parent` := x
          x.rank    := 0
          x.size    := 1
      

  • provides a “Find” operation to determine which set an element belongs to:
    • traverses upwards along the chain of parent pointers until it finds the root element for the set, which is the answer to find
    • path compression:
      • flattens the disjoint-set tree by changing every element’s parent pointer to point to the root element of its set when Find is invoked

        function Find(x)
          if x.parent != x
            x.parent := Find(x.parent)
            return x.parent
        

    • path halving:
      • makes every other node on the path point to its grandparent

        function Find(x)
          while x.parent != x
            x.parent := x.parent.parent
            x := x.parent
            
          return x
        

    • path splitting:
      • makes every node on the path pooint to its grandparent

        function Find(x)
          while x.parent != x
            next := x.parent
            x.parent := next.parent
            x := next
            
          return x
        

  • provides a “Union” operation to connect internal elements into components:
    • used Find to determine the roots of the input elements and check whether they have the same root
      • if roots are not the same, the trees are merged at the root by attaching the root of one tree to the root of the other
    • union by rank:
      • attaches the shorter tree to the root of the taller tree

        function Union(x, y)
          xRoot := Find(x)
          yRoot := Find(y)
          
          if xRoot == yRoot,
            return
          
          if xRoot.rank < yRoot.rank,
            temp := xRoot
            xRoot := yRoot
            yRoot := temp
            
          yRoot.parent := xRoot
          
          if xRoot.rank == yRoot.rank,
            xRoot.rank := xRoot.rank + 1
        

    • union by size:
      • attaches the tree with fewer elements to the root of the tree with more elements

        function Union(x, y)
          xRoot := Find(x)
          yRoot := Find(y)
          
          if xRoot == yRoot,
            return
          
          if xRoot.size < yRoot.size,
            temp := xRoot
            xRoot := yRoot
            yRoot := temp
          
          yRoot.parent := xRoot
          xRoot.size := xRoot.size + yRoot.size