This is not Graph, so how it is connected does not matter.
Goal
Structure
Implementation
Quick Find Variant
find and isConnected is very fast while connect is slow.
Quick Union Variant
Defect: When tree is too tall, it may cost lots of time to find.
Weighted(Ranked) Quick Union Variant
Link the smaller below the larger tree by tracking the tree size.
Improvement:
That is: when we link two tree, the depth of the node of tree incorporated will increase one. So what we need to do is incorporate the smaller one, lessening the increase of depth.
Attention: In addition to weight(size), the height can also be rank, but the runtime is almost same and weight is more easy.
Path Compression
The change: find
Summary
