Report Number: CS-TR-78-709
Institution: Stanford University, Department of Computer Science
Title: Design and analysis of a data structure for representing sorted lists
Author: Brown, Mark R.
Author: Tarjan, Robert E.
Date: December 1978
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 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 [1977], but it is substantially simpler and may be practical for lists of moderate size.
http://i.stanford.edu/pub/cstr/reports/cs/tr/78/709/CS-TR-78-709.pdf