Logo des Repositoriums
 
Konferenzbeitrag

Löschungen in zufälligen binären Suchbäumen – Eine Geschichte der Irrungen

Lade...
Vorschaubild

Volltext URI

Dokumententyp

Text/Conference Paper

Zusatzinformation

Datum

2003

Zeitschriftentitel

ISSN der Zeitschrift

Bandtitel

Verlag

Gesellschaft für Informatik e.V.

Zusammenfassung

Die üblichen Annahmen für die average-case Analyse von binären Such- bäumen (BSB) sind zufällige Einfügungen (random insertions) und zufällige Löschungen (random deletions). In einem durch zufällige Einfügungen aufgebauten BSB haben die Zugriffsoperationen eine erwartete Zeitkomplexität von O(log n) und schon die ersten Publikationen über BSB enthalten wesentliche analytische Ergebnisse für solche 'random' BSB. Wenn es allerdings um zufällige Löschungen und um ihre Interaktion mit zufälligen Einfügungen geht, scheint die Analyse um einiges komplizierter zu werden. Das kann man jedenfalls den einschlägigen Publikationen seit 1962 entnehmen, die es berechtigt erscheinen lassen, in diesem Zusammenhang von einer 'Geschichte der Irrungen' zu sprechen. Dieser Beitrag geht etwas näher auf diese Geschichte ein.

Beschreibung

Panny, Wolfgang (2003): Löschungen in zufälligen binären Suchbäumen – Eine Geschichte der Irrungen. Informationswirtschaft: Ein Sektor mit Zukunft. Bonn: Gesellschaft für Informatik e.V.. PISSN: 1617-5468. ISBN: 3-88579-362-8. pp. 75-88. Regular Research Papers. Wien, Österreich. 4.-5. September 2003

Schlagwörter

Zitierform

DOI

Tags