Design and Analysis of a Data Structure for Representing Sorted Lists

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 assumptions: (i) only insertions are performed; (ii) only deletions are performed; (iii) 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 [A new representation for linear lists, Proc. Ninth Annual Symposium on Theory of Computing, Boulder, CO, 1977, pp. 49–60], but it is substantially simpler and may be practical for lists of moderate size.