1984 Reports

β-trees, γ-systems, and a Theorem on F-heaps

Galil, Zvi; Spencer, Thomas

Recent progress in the design or efficient data structures has been remarkable. This progress is documented in the new book by Tarjan [9]. Even operations manipulating trees can be implemented in amortized time O(log n); i.e. time O(m log n) for m operations. (See [9 Chapter 5]). Recently, attempts have been made to develop data structures that implement some sets of operations in (amortized) time o(log n) or even 0(1) time. Sometimes this is only possible when the number of operations (m) is large enough.