Design and Analysis of a Data Structure for Representing Sorted Lists.
Abstract
In this paper we explore the use of 2-3 trees to represent sorted lists. We analyze the worst-case cost of sequences of insertions and deletions in 2-3 trees under each of the following three assumption: only insertions are performed; only deletions are performed; deletions occur only at the small end of the list and insertions occur only away from the small end. Our analysis leads to a data structure for representing sorted lists when the access pattern exhibits a (perhaps time-varying) locality of reference. This structure has many of the properties of the representation proposed by Guibas, McCreight, Plass, and Roberts, but it is substantially simpler and may be practical for lists of moderate size. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1978
- Accession Number
- ADA068231
Entities
People
- Mark R. Brown
- Robert Tarjan
Organizations
- Stanford University