Randomized search trees. (English) Zbl 0857.68030

Seidel, R.; Aragon, C. R.

Algorithmica 16, No. 4-5, 464-497 (1996).

Summary: We present a randomized strategy for maintaining balance in dynamically changing search trees that has optimal expected behavior. In particular, in the expected case a search or an update takes logarithmic time, with the update requiring fewer than two rotations. Moreover, the update time remains logarithmic, even if the cost of a rotation is taken to be proportional to the size of the rotated subtree. Finger searches and splits and joins can be performed in optimal expected time also. We show that these results continue to hold even if very little true randomness is available, i.e., if only a logarithmic number of truely random bits are available. Our approach generalizes naturally to weighted trees, where the expected time bounds for accesses and updates again match the worst-case time bounds of the best deterministic methods. We also discuss ways of implementing our randomized strategy so that no explicit balance information is maintained. Our balancing strategy and our algorithms are exceedingly simple and should be fast in practice.

MSC:

68P10	Searching and sorting
68R10	Graph theory (including graph drawing) in computer science
68P05	Data structures

Keywords:

search trees

Software:

Hull; LEDA

References:

[1]	G. M. Adel’son-Velskii and Y. M. Landis, An algorithm for the organization of information,Soviet Math. Dokl,3 (1962), 1259–1262.
[2]	A. Andersson and T. Ottmann, Faster uniquely represented dictionaries,Proc. 32nd FOCS, 1991, pp. 642–649.
[3]	H. Baumgarten, H. Jung, and K. Mehlhorn, Dynamic point location in general subdivision,Proc. 3rd ACM-SIAM Symp. on Discrete Algorithms (SODA), 1992, pp. 250–258. · Zbl 0829.68119
[4]	R. Bayer and E. McCreight, Organization and maintenance of large ordered indices,Act. Inf.,1 (1972), 173–189. · Zbl 0226.68008
[5]	S. W. Bent and J. R. Driscoll, Randomly balanced search trees, Manuscript (1991).
[6]	S. W. Bent, D. D. Sleator, and R. E. Tarjan, Biased search trees,SIAM J. Comput.,14 (1985), 545–568. · Zbl 0568.68045
[7]	R. P. Brent, Fast multiple precision evaluation of elementary functions,J. Assoc. Comput. Mach.,23 (1976), 242–251. · Zbl 0324.65018
[8]	M. Brown, Addendum to ”A Storage Scheme for Height-Balanced Trees,”Inform. Process. Lett.,8 (1979), 154–156.
[9]	K. L. Clarkson, K. Mehlhorn, and R. Seidel, Four results on randomized incremental construction,Comput. Geom. Theory Appl.,3 (1993), 185–212. · Zbl 0781.68112
[10]	L. Devroye, A note on the height of binary search trees,J. Assoc. Comput. Mach.,33 (1986), 489–498. · Zbl 0741.05062
[11]	M. Dietzfelbinger (private communication).
[12]	I. Galperin and R. L. Rivest, Scapegoat trees,Proc. 4th ACM-SIAM Symp. on Discrete Algorithms (SODA), 1993, pp. 165–174. · Zbl 0801.68034
[13]	L. J. Guibas and R. Sedgewick, A dichromatic framework for balanced trees,Proc. 19th FOCS, 1978, pp. 8–21.
[14]	T. Hagerup and C. Rüb, A guided tour of Chernoff bounds,Inform. Process. Lett.,33 (1989/90), 305–308. · Zbl 0702.60021
[15]	K. Hoffman, K. Mehlhorn, P. Rosenstiehl, and R. E. Tarjan, Sorting Jordan sequences in linear time using level linked search trees,Inform. and Control,68 (1986), 170–184. · Zbl 0614.68051
[16]	E. McCreight, Priority search trees,SIAM J. Comput.,14 (1985), 257–276. · Zbl 0564.68050
[17]	K. Mehlhorn,Sorting and Searching, Springer-Verlag, Berlin, 1984. · Zbl 0556.68001
[18]	K. Mehlhorn,Multi-Dimensional Searching and Computational Geometry, Springer-Verlag, Berlin, 1984. · Zbl 0556.68003
[19]	K. Mehlhorn (private communication).
[20]	K. Mehlhorn and S. Näher, Algorithm design and software libraries: recent developments in the LEDA project, inAlgorithms, Software, Architectures, Information Processing 92, Vol. 1, Elsevier, Amsterdam, 1992.
[21]	K. Mehlhorn and S. Näher, LEDA, a platform for combinatorial and geometric computing.Commun. ACM,38 (1995), 95–102.
[22]	K. Mehlhorn and R. Raman (private communication).
[23]	K. Mulmuley,Computational Geometry: An Introduction through Randomized Algorithms, Prentice-Hall, Englewood Cliffs, NJ, 1994. · Zbl 0806.68109
[24]	S. Näher, LEDA User Manual Version 3.0. Tech. Report MPI-I-93-109, Max-Planck-Institut für Informatik, Saarbrücken, 1993.
[25]	J. Nievergelt and E. M. Reingold, Binary search trees of bounded balance,SIAM J. Comput. 2 (1973), 33–43. · Zbl 0262.68012
[26]	W. Pugh, Skip lists: a probabilistic alternative to balanced trees.Commun. ACM,33 (1990), 668–676.
[27]	W. Pugh and T. Teitelbaum, Incremental computation via function caching,Proc. 16th ACM POPL, 1989, pp. 315–328.
[28]	D. D. Sleator (private communication).
[29]	D. D. Sleator and R. E. Tarjan, Self-adjusting binary search trees,J. Assoc. Comput. Mach.,32 (1985), 652–686. · Zbl 0631.68060
[30]	R. E. Tarjan (private communication).
[31]	J. Vuillemin, A unifying look at data structures,Comm. ACM,23 (1980), 229–239. · Zbl 0434.68047