Maintaining Tree Projections in Amortized $O$(log $n$) Time.

Abstract

The projection of a set of marked nodes in a tree can be represented by a structure tree, that is, a subtree containing the marked nodes and the lowest common ancestors of all pairs of marked nodes. As an application modifies a forest of trees by linking and cutting trees and by marking and unmarking nodes, the structure tree associated with each tree must be updated in order to reflect the current set of marked nodes. Previous algorithms have used $O(n)$ time per operation [Hoover 87] to maintain structure trees. This algorithm makes use of self-adjusting binary trees [Sleator and Tarjan 85] and reduces the running time to amortized $O$(log $n$) per operation.