SciDok

Eingang zum Volltext in SciDok

Lizenz

Report (Bericht) zugänglich unter
URN: urn:nbn:de:bsz:291-scidok-42198
URL: http://scidok.sulb.uni-saarland.de/volltexte/2011/4219/


Randomized search trees

Seidel, Raimund ; Aragon, Cecilia R.

Quelle: (1995) Saarbr├╝cken, 1995
pdf-Format:
Dokument 1.pdf (19.494 KB)

Bookmark bei Connotea Bookmark bei del.icio.us
Institut: Fachrichtung 6.2 - Informatik
DDC-Sachgruppe: Informatik
Dokumentart: Report (Bericht)
Schriftenreihe: Technischer Bericht / A / Fachbereich Informatik, Universit├Ąt des Saarlandes
Bandnummer: 1995/06
Sprache: Englisch
Erstellungsjahr: 1995
Publikationsdatum: 07.09.2011
Kurzfassung auf Englisch: 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.
Lizenz: Standard-Veröffentlichungsvertrag

Home | Impressum | Über SciDok | Policy | Kontakt | Datenschutzerklärung | English