{title}

Back to notes

Disjoint-set data structure

Keywords: union-find, union find, graphs, undirected graph, data structures
Date:
  • 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
          

Backlinks: