zbMATH — the first resource for mathematics

A data structure for dynamically maintaining rooted trees. (English) Zbl 0882.68104
Summary: The directed topology tree data structure is developed for maintaining binary trees dynamically. Each of a certain set of tree operations is shown to take \(O(\log n)\) time, where \(n\) is the number of vertices in the trees. The directed topology trees are used to implement link-cut trees and dynamic expression trees. The results of experimental comparisons with the dynamic trees of Sleator and Tarjan are presented.

68R10 Graph theory (including graph drawing) in computer science
68P05 Data structures
Full Text: DOI