Please use this identifier to cite or link to this item:
doi:10.22028/D291-26146
Title: | Randomized search trees |
Author(s): | Seidel, Raimund Aragon, Cecilia R. |
Language: | English |
Year of Publication: | 1995 |
OPUS Source: | Saarbrücken, 1995 |
DDC notations: | 004 Computer science, internet |
Publikation type: | Report |
Abstract: | 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. |
Link to this record: | urn:nbn:de:bsz:291-scidok-42198 hdl:20.500.11880/26202 http://dx.doi.org/10.22028/D291-26146 |
Series name: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Series volume: | 1995/06 |
Date of registration: | 7-Sep-2011 |
Faculty: | MI - Fakultät für Mathematik und Informatik |
Department: | MI - Informatik |
Collections: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Files for this record:
File | Description | Size | Format | |
---|---|---|---|---|
fb14_1995_06_neu.pdf | 19,49 MB | Adobe PDF | View/Open |
Items in SciDok are protected by copyright, with all rights reserved, unless otherwise indicated.