β-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.



More About This Work

Academic Units
Computer Science
Department of Computer Science, Columbia University
Columbia University Computer Science Technical Reports, CUCS-105-84
Published Here
February 15, 2012