Link/cut tree
From Wikipedia, the free encyclopedia
A link/cut tree is a type of data structure capable of merging (link operation) and splitting (cut operation) data sets in O(log(n)) amortized time, as well as finding which tree an element belongs to in O(log(n)) amortized time.
