Summary
In this paper we explore the use of weak B-trees to represent sorted lists. In weak B-trees each node has at least a and at most b sons where 2a≦b. We analyse the worst case cost of sequences of insertions and deletions in weak B-trees. This leads to a new data structure (level-linked weak B-trees) for representing sorted lists when the access pattern exhibits a (time-varying) locality of reference. Our structure is substantially simpler than the one proposed in [7], yet it has many of its properties. Our structure is as simple as the one proposed in [5], but our structure can treat arbitrary sequences of insertions and deletions whilst theirs can only treat non-interacting insertions and deletions. We also show that weak B-trees support concurrent operations in an efficient way.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bayer, R.: Symmetric Binary B-trees: Data structures and maintenance algorithms. Acta Informat. 1, 290–306 (1972)
Bayer, R., McCreight, E.: Organization and maintenance of large ordered indizes. Acta Informat. 1, 173–189 (1972)
Bayer, R., Schkolnik, M.: Concurrency of operations on B-trees. Acta Informat. 9, 1–21 (1977)
Blum, N., Mehlhorn, K.: On the average number of rebalancing steps in weight-balanced trees. Theor. Comput. Sci. 11, 303–320 (1980)
Brown, M.R., Tarjan, R.E.: Design and analysis of a data structure for representing sorted lists. SIAM J. Comput. 9, 594–614 (1980)
Guibas, L.J., Sedgewick, R.: A dichromatic framework for balanced trees. Proc. 19th Annual Symposium on Foundations of Computer Science. Ann Arbor: IEEE Computer Socienty, pp. 8–21 (1978)
Guibas, L., McCreight, E., Plass, M, Roberts, J.: A new representation for linear lists. 9th ACM Symposium on Theory of Computing Boulder, pp. 49–60 (1977)
Huddleston, S.: Robust balancing in B-trees. PhD Dissertation, Computer Science Department, University of Washington, Seattle, 1981
Huddleston, S., Mehlhorn, K.: Robust balancing in B-trees. 5th GI-Conference on Theoretical Informatics 1981, Karlsruhe, LNCS 104, 234–244 (1981)
Maier, D., Salveter, S.C.: Hysterical B-trees. Technical Report 79/007, Dept. of Computer Science, State University of New York at Stony Brook, November 1979
Mehlhorn, K.: Effiziente Algorithmen. Teubner-Verlag, Studienbücher Informatik 1977
Mehlhorn, K.: Sorting presorted files. 4th GI-Conference on Theoretical Computer Science 1979, Aachen, Lecture Notes in Computer Science Vol. 67, pp. 199–212. Berlin-Heidelberg-New York: Springer 1979
Mehlhorn, K.: Searching, sorting and information theory. MFCS 79, Lecture Notes in Computer Science Vol. 74, pp. 131–145. Berlin-Heidelberg-New York: Springer 1981
Willard, D.E.: The super-B-tree algorithm. Harvard Aiken Computation Laboratory Report TR-03-79
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Huddleston, S., Mehlhorn, K. A new data structure for representing sorted lists. Acta Informatica 17, 157–184 (1982). https://doi.org/10.1007/BF00288968
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF00288968