Transforming static data structures to dynamic structures
James B. Saxe, Jon Louis Bentley · Annual Symposium on Foundations of Computer Science · 1979
In this paper we will investigate transformations that serve as tools in the design of new data structures. Specifically, we study general methods for converting static structures (in which all elements are known before any searches are performed) to dynamic structures (in which the insertion of a new element can be mixed with searches). We will see three classes of such transformations (each based on a different counting scheme for representing the integers) and then use a combinatorial model to show the optimality of many of the transformations. Issues such as online data structures and deletion of elements are also examined. To demonstrate the applicability of these tools, we will study six new data structures that have been developed by applying the transformations.
Cited by 36 works. doi:10.1109/sfcs.1979.47 Open-access PDF
Authors
References
- The Art of Computer Programming
- The Art of Computer Programming
- The Art of Computer Programming
- Multidimensional Searching Problems
- Applications of a planar separator theorem
- Partial-Match Retrieval Algorithms
- Decomposable searching problems
- Efficient worst-case data structures for range searching
- A data structure for manipulating priority queues
- A New Approach to Planar Point Location