Academic Commons

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.

Subjects

Files

More About This Work

Academic Units
Computer Science
Publisher
Department of Computer Science, Columbia University
Series
Columbia University Computer Science Technical Reports, CUCS-105-84
Published Here
February 15, 2012
Academic Commons provides global access to research and scholarship produced at Columbia University, Barnard College, Teachers College, Union Theological Seminary and Jewish Theological Seminary. Academic Commons is managed by the Columbia University Libraries.