Richard Cole, Ramesh Hariharan

Proceedings of the Tenth Annual ACM-SIAM Symposium on Discrete Algorithms,, 1999, 235-244.

We show how to maintain a data structure on trees which allows for the following operations, all in worst-case constant time.

• Insertion of leaves and internal nodes.
• Deletion of leaves.
• Deletion of internal nodes with only one child.
• Determining the Least Common Ancestor of any two nodes.

postscript of full paper