UnionFind data structure implemented in Python

Question

This class is used to create sets out of nodes to from a graph-like structure (or grouping since I remove most of the normal graph structure and all child nodes have the same parent).

Is there anything I can do to improve the design of this class? Is the use of static methods here appropriate?

class UnionFind(object):
    '''
    Used to initialize the set and then holds the required functions 
    to operate on them
    '''

    def __init__(self, vertex):
        self.rank = 0
        self.parent = self
        self.vertex = vertex

    @staticmethod
    def find(x):
        if x != x.parent:
            x.parent = UnionFind.find(x.parent)
        return x

    @staticmethod
    def union(x,y):
        xroot = UnionFind.find(x)
        yroot = UnionFind.find(y)

        if xroot == yroot:
            return 
        if xroot.rank > yroot.rank:
            yroot.parent = xroot
        else:
            xroot.parent = yroot
            if xroot.rank == yroot.rank:
                yroot.rank += 1

Answer 1

• find is not a right name. A method find(x) is expected to find objects matching x. find_root seems more appropriate.

  _{I know that Sedgewick & Wayne use find, and they are wrong.}

• find (or find_root) has no reason to be static. x.find_root() is way more natural than UnionFind.find_root(x).

• Python does not eliminate tail recursion. I recommend to rewrite find as

  def find(x):
      while x != x.parent:
          x = x.parent
      return x