Union find is used to implement an equivalence relation on objects, where the equivalence relation can dynamically be coarsened by "union"ing two equivalence classes together.
All of the operations are effectively (amortized) constant time.
type 'a tis the type of objects, where each object is part of an equivalence class that is associated with a single value of type
val create :
'a -> 'a t
create vreturns a new object in its own equivalence class that has value
val get :
'a t -> 'a
get treturns the value of the class of
val set :
'a t -> 'a -> unit
set t vsets the value of the class of
same_class t1 t2returns true iff
t2are in the same equivalence class.
union t1 t2makes the class of
t1and the class of
t2be the same (if they are already equal, then nothing changes). The value of the combined class is the value of
t2; it is unspecified which. After
union t1 t2, it will always be the case that
same_class t1 t2.