Postorder Disjoint Set Union is Linear

Abstract

Any instance of the disjoint set union problem of size n, using any union strategy, that does one find per node in postorder has total cost $O(n)$. This special case, when the finds are restricted to occur in postorder, is related to the behavior of such self-adjusting data structures as the splay tree and the pairing heap.