Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen:
doi:10.22028/D291-26146
Titel: | Randomized search trees |
VerfasserIn: | Seidel, Raimund Aragon, Cecilia R. |
Sprache: | Englisch |
Erscheinungsjahr: | 1995 |
Quelle: | Saarbrücken, 1995 |
DDC-Sachgruppe: | 004 Informatik |
Dokumenttyp: | Forschungsbericht (Report zu Forschungsprojekten) |
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 zu diesem Datensatz: | urn:nbn:de:bsz:291-scidok-42198 hdl:20.500.11880/26202 http://dx.doi.org/10.22028/D291-26146 |
Schriftenreihe: | Technischer Bericht / A / Fachbereich Informatik, Universität des Saarlandes |
Band: | 1995/06 |
Datum des Eintrags: | 7-Sep-2011 |
Fakultät: | MI - Fakultät für Mathematik und Informatik |
Fachrichtung: | MI - Informatik |
Sammlung: | SciDok - Der Wissenschaftsserver der Universität des Saarlandes |
Dateien zu diesem Datensatz:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
fb14_1995_06_neu.pdf | 19,49 MB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.