Abstract
A data structure is described which is useful for representing linear lists when the pattern of accesses to a list exhibits a (perhaps time-varying) locality of reference. The structure has many of the properties of the representation proposed by L. J. Guibas et al. , but is substantially simpler and may be practical for lists of moderate size. The analysis of this structure includes a general treatment of the worst-case node splitting caused by consecutive insertions into a 2-3 tree.
Original language | English (US) |
---|---|
Pages | 19-29 |
Number of pages | 11 |
State | Published - 1978 |
Event | Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp - San Diego, CA, USA Duration: May 1 1978 → May 3 1978 |
Other
Other | Conf Rec Annu ACM Symp Theory Comput 10th, Pap Presented at the Symp |
---|---|
City | San Diego, CA, USA |
Period | 5/1/78 → 5/3/78 |
All Science Journal Classification (ASJC) codes
- General Engineering