Konferenzbeitrag
Löschungen in zufälligen binären Suchbäumen – Eine Geschichte der Irrungen
Lade...
Volltext URI
Dokumententyp
Text/Conference Paper
Zusatzinformation
Datum
2003
Autor:innen
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.