Euler Tour Trees (ETT) are another dynamic tree structure:
- Store Euler tour of tree in a balanced BST
- Link/cut by splicing tours
- Subtree queries are range queries on tour
Comparison:
| Link-Cut | ETT | |
|---|---|---|
| Path query | Not native | |
| Subtree query | Complex | |
| Implementation | Hard | Medium |
ETT is better for subtree operations.
Link-Cut is better for path operations. Choose based on what queries you need.