BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-78-709
       ENTRY:: June 19, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Design and analysis of a data structure for representing
               sorted lists
        TYPE:: Technical Report
      AUTHOR:: Brown, Mark R.
      AUTHOR:: Tarjan, Robert E.
        DATE:: December 1978
       PAGES:: 50
    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.
       NOTES:: [Adminitrivia V1/Prg/19950619]
         END:: STAN//CS-TR-78-709