Abstract
In this paper we show how a slight modification of (a, b)-trees allows us to perform member and neighbor queries in O(log n) time and updates in O(1) worst-case time (once the position of the inserted or deleted key is known). Our data structure is quite natural and much simpler than previous worst-case optimal solutions. It is based on two techniques: 1) bucketing, i.e. storing an ordered list of 2log n keys in each leaf of an (a, b) tree, and 2) lazy splitting, i.e. postponing necessary splits of big nodes until we have time to handle them. It can also be used as a finger tree with O(log* n) worst-case update time.
This work was supported by the ESPRIT II program of the EC under contract No. 3075 (project ALCOM)
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
A. Andersson, T.W. Lai: ”Comparison-efficient and write-optimal searching and sorting” Proc. 2nd ISA 1991, 273–282
P.F. Dietz, R. Raman: ”A constant update time finger search tree” Advances in Computing and Information — ICCI '90, Lecture Notes in Computer Science, Vol. 468, Springer 1990, 100–109 Also as Univ. of Rochester CS Dept. TR 321, December 1989
P.F. Dietz, D.D. Sleator: ”Two algorithms for maintaining order in a list” Proc. 19th ACM STOC 1987, 365–372
J.R. Driscoll, N. Sarnak, D.D. Sleator, R.E. Tarjan: ”Making data structures persistent” Journal of Computer and System Sciences 38 (1989), 86–124
L. Guibas, E. McCreight, M. Plass, J. Roberts: ”A new representation for linear lists” Proc. 9th ACM STOC 1977, 49–60
D. Harel: “Fast updates with a guaranteed time bound per update” Technical Report 154, Dept. of ICS, University of California at Irvine, 1980
D. Harel, G. Lueker: “A data structure with movable fingers and deletions” Technical Report 145, Dept. of ICS, University of Califonia at Irvine, 1979
S. Huddleston, K. Mehlhorn: ”A new data structure for representing sorted lists” Acta Informatica 17 (1982), 157–184
C. Levcopoulos, M.H. Overmars: ”A balanced search tree with O(1) worst-case update time” Acta Informatica 26 (1988), 269–277
K. Mulmuley: ”Randomized multidimensional search trees: Dynamic sampling” Proc. 7th Symposium on Computational Geometry 1991, 121–131
M.H. Overmars: ”A O(1) average time update scheme for balanced search trees” Bull. EATCS 18 (1982), 27–29
M.H. Overmars: ”The design of dynamic data structures” Lecture Notes in Computer Science, Vol. 156, Springer 1983
M.H. Overmars, J. van Leeuwen: ”Worst-case optimal insertion and deletion methods for decomposable searching methods” Information Processing Letters 12 (1981), 168–173
R.E. Tarjan: ”Updating a balanced search tree in O(1) rotations” Information Processing Letters 16 (1983), 253–257
A.K. Tsakalidis: ”AVL-trees for localized search” Information and Control 67 (1985), 173–194
J. van der Erf: ”Een datastructuur met zoektijd O(log n) en constante update-tijd (in Dutch)” Technical Report RUU-CS-87-19, Dept. of Computer Science, University of Utrecht 1987
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fleischer, R. (1993). A simple balanced search tree with O(1) worst-case update time. In: Ng, K.W., Raghavan, P., Balasubramanian, N.V., Chin, F.Y.L. (eds) Algorithms and Computation. ISAAC 1993. Lecture Notes in Computer Science, vol 762. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-57568-5_243
Download citation
DOI: https://doi.org/10.1007/3-540-57568-5_243
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57568-9
Online ISBN: 978-3-540-48233-8
eBook Packages: Springer Book Archive