Report Number: CS-TR-78-709
Institution: Stanford University, Department of Computer Science
Title: Design and analysis of a data structure for representing
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 , but it is substantially simpler and may be
practical for lists of moderate size.