  Motivated by the problem of maintaining data structures for a large sets of
points that are evolving over the course of time, we consider the problem of
maintaining a set of labels assigned to the vertices of a tree, where the
locations of these labels change over time. We study the problem in the
evolving data framework, where labels change over time due to the action of an
agent called the evolver. The algorithm can only track these changes by
explicitly probing individual nodes of the tree. This framework captures the
tradeoff between the complexity of maintaining an up-to-date view of the
structure and the quality of results computed with the available view. Our
results allow for both randomized and adversarial evolution of the data,
subject to allowing different speedup factors between the algorithm and the
evolver. We show that in the limit, our algorithm maintains labels to within an
average distance of $O(1)$ of their actual locations. We also present nearly
matching lower bounds.
