A Comparative Study of Dynamic Clustering Using Euler Tour Trees and Link-Cut Trees

Abstract

Dynamic clustering is a crucial aspect of data science, enabling real-time updates and efficient 
data organization. Traditional clustering algorithms, such as DBSCAN, struggle with dynamic datasets 
due to their high computational costs. This paper presents a comparative study of two advanced data 
structures—Euler Tour Trees (ETTs) and Link-Cut Trees (LCTs)—for dynamic clustering. We analyze 
their performance in terms of update efficiency, query time, and practical applicability to clustering 
algorithms. Our results demonstrate that while ETTs provide better connectivity maintenance, LCTs 
outperform in path-based queries, making them suitable for different types of dynamic clustering 
applications.