Bitte benutzen Sie diese Referenz, um auf diese Ressource zu verweisen: doi:10.22028/D291-26146
Titel: Randomized search trees
Verfasser: Seidel, Raimund
Aragon, Cecilia R.
Sprache: Englisch
Erscheinungsjahr: 1995
Quelle: Saarbrücken, 1995
DDC-Sachgruppe: 004 Informatik
Dokumentart : Report (Bericht)
Kurzfassung: 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
SciDok-Publikation: 7-Sep-2011
Fakultät: Fakultät 6 - Naturwissenschaftlich-Technische Fakultät I
Fachrichtung: MI - Informatik
Fakultät / Institution:MI - Fakultät für Mathematik und Informatik

Dateien zu dieser Ressource:
Datei Beschreibung GrößeFormat 
fb14_1995_06_neu.pdf19,49 MBAdobe PDFÖffnen/Anzeigen


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt.